Basic Calculator II: Stack-Based Operator Precedence

May 14, 20265 min read

leetcodeproblemmediumstacksmathstrings

Basic Calculator II is LeetCode 227, rated Medium. You are given a string containing an arithmetic expression with +, -, *, and / (no parentheses), and you need to evaluate it following standard operator precedence. Multiplication and division bind tighter than addition and subtraction, so 3+2*2 equals 7, not 10. The key challenge is respecting that precedence in a single left-to-right pass.

For * and /, compute immediately by popping the last value. For + and -, push the value with its sign. At the end, sum the stack.

The approach: track the previous operator

The core insight is that you do not need two passes or a tree to handle precedence. You just need to delay low-precedence operations.

Here is the strategy. Walk through the string character by character, building up the current number. When you hit an operator (or reach the end of the string), you look at the previous operator to decide what to do with the number you just finished reading:

If the previous operator was +, push the number onto the stack.
If the previous operator was -, push the negated number onto the stack.
If the previous operator was *, pop the top of the stack, multiply it by the current number, and push the result.
If the previous operator was /, pop the top of the stack, divide it by the current number (truncating toward zero), and push the result.

At the very end, sum everything remaining on the stack. That sum is your answer.

Why does this work? Addition and subtraction values just accumulate on the stack because they cannot be resolved until you know whether a higher-precedence operator follows. Multiplication and division, on the other hand, grab the most recent value and compute immediately. By the time you sum the stack, all the * and / operations have already been folded in.

Practice this pattern

The solution

def calculate(s: str) -> int:
    stack = []
    num = 0
    prev_op = "+"

    for i, ch in enumerate(s):
        if ch.isdigit():
            num = num * 10 + int(ch)
        if (not ch.isdigit() and ch != " ") or i == len(s) - 1:
            if prev_op == "+":
                stack.append(num)
            elif prev_op == "-":
                stack.append(-num)
            elif prev_op == "*":
                stack.append(stack.pop() * num)
            else:
                stack.append(int(stack.pop() / num))
            prev_op = ch
            num = 0

    return sum(stack)

Build multi-digit numbers. As you scan, num = num * 10 + int(ch) accumulates digits into a full integer. This handles numbers like 42 or 100.
Two conditions trigger processing. You process the accumulated number when you encounter a non-space, non-digit character (an operator), or when you reach the last character in the string. Both conditions can be true at the same time if the string ends with a digit.
Previous operator decides the action. The variable prev_op starts as "+" so the very first number gets pushed as a positive value. After processing, prev_op updates to the current operator.
Multiplication and division pop immediately. When prev_op is * or /, you pop the top value, combine it with the current number, and push the result back. This resolves high-precedence operations on the spot.
Division truncates toward zero. int(stack.pop() / num) handles truncation correctly for negative values. Python's // floors toward negative infinity, which would give wrong results for cases like -7 / 2.
Sum the stack. After the loop, every remaining stack entry is a term from an addition or subtraction chain. Summing them gives the final answer.

Step-by-step walkthrough

Step 1: Read "3", prev_op is "+" (default). Push +3.

Stack: [3]. The default prev_op is +, so we push the first number.

Step 2: Read "+". Update prev_op to "+".

Stack: [3]. We just store the operator and move on.

Step 3: Read "5", prev_op is "+". Push +5.

Stack: [3, 5]. Addition means push the value for later.

Step 4: Read "/". Update prev_op to "/".

Stack: [3, 5]. Division is high precedence, so the next number triggers an immediate computation.

Step 5: Read "2", prev_op is "/". Pop 5, compute 5/2=2. Push 2.

Stack: [3, 2]. Division applied immediately: int(5/2) = 2.

Step 6: Read "*". Update prev_op to "*".

Stack: [3, 2]. Multiplication is high precedence, so next number triggers computation.

Step 7: Read "2", prev_op is "*". Pop 2, compute 2*2=4. Push 4.

Stack: [3, 4]. Multiplication applied immediately: 2 * 2 = 4.

Step 8: Read "-". Update prev_op to "-".

Stack: [3, 4]. Subtraction means we will push the negative of the next number.

Step 9: Read "1", prev_op is "-". Push -1.

Stack: [3, 4, -1]. Subtraction pushes the negated value.

Step 10: End of expression. Sum the stack: 3 + 4 + (-1) = 6.

Final answer: 6. Sum all values remaining on the stack.

Drill this with spaced repetition

Complexity analysis

Metric	Value	Why
Time	O(n)	Single pass through the string, each character handled once
Space	O(n)	Stack can hold up to n/2 entries in the worst case (all additions)

Building blocks

These reusable techniques from Basic Calculator II show up across many problems:

Delayed evaluation with a previous-operator variable. Instead of processing an operator when you first see it, you wait until you have the next number. This lets you decide the right action based on context. The same pattern works for any expression parser.
Stack as a pending-operations buffer. Low-precedence terms sit on the stack while high-precedence operations resolve immediately. This is the same idea behind converting infix to postfix notation, just done inline.
Digit accumulation. The num = num * 10 + int(ch) pattern for building multi-digit numbers from a character stream appears in string-to-integer conversion, number parsing, and many calculator problems.

Edge cases

Single number. "42" has no operators. The default prev_op of "+" pushes 42, and sum([42]) returns 42.
Spaces everywhere. " 3 + 5 / 2 " is valid input. The code skips spaces and only triggers processing on operators or end-of-string.
Division truncation with negatives. "14-3/2" should give 13, not 12. int(3/2) is 1, and 14 - 1 = 13. Using // would give 1 here too, but for cases like "-7/2" the distinction matters.
All same-precedence operators. "1+2+3+4" pushes every number and sums at the end. No * or / means the stack just collects terms.
Chained multiplication and division. "6/3*2" processes left to right: 6/3=2, then 2*2=4. Each high-precedence op pops and pushes immediately, preserving left-to-right evaluation.
Large numbers. "1000000*1000000" works fine since Python handles arbitrary-precision integers.

Watch out for integer division truncation toward zero. Python's // operator truncates toward negative infinity, so int(-3 / 2) gives -1 while -3 // 2 gives -2. Always use int(a / b) when the problem says "truncate toward zero."

From understanding to recall

Basic Calculator II is a great example of a problem where the concept is simple but the implementation has subtle details. Which condition triggers processing? What does prev_op start as? Do you push num or -num for subtraction? These small choices determine correctness, and they are easy to forget under pressure.

Spaced repetition fixes that. You write the solution from scratch at increasing intervals, and each repetition reinforces the digit accumulation loop, the four-way operator branch, and the truncation-toward-zero trick. After a few cycles, the whole solution flows out of your fingers automatically.

Build recall with CodeBricks