Basic Calculator II
Evaluate a string expression s containing non-negative integers and the operators +, -, *, / (integer division truncates toward zero). No parentheses.
Intuition
The challenge is operator precedence: and / bind tighter than + and -. A stack solves this elegantly. Walk through the expression, and for each number, look at the previous operator. If it was + or -, push the number (with sign) onto the stack — it cannot be evaluated yet because a or / might follow. If the previous operator was * or /, pop the top of the stack, apply the operation, and push the result back. After processing all tokens, the stack contains only terms to be summed.
When an expression has two precedence levels and no parentheses, a single stack suffices: defer low-precedence operations by pushing, and execute high-precedence operations immediately by popping. This pattern generalises to more precedence levels by using multiple stacks or a shunting-yard approach, but for +/- vs *// a single stack is enough.
Approach
Track the previous operator and build multi-digit numbers
Initialize prev_op = '+'. Walk through the string. Accumulate consecutive digits into num. When you hit an operator (or the end of the string), the number is complete and you process it based on prev_op.
Push for `+`/`-`, evaluate immediately for `*`/`/`
If prev_op is +, push num. If -, push -num. If , pop the top, multiply by num, push the product. If /, pop the top, divide by num (truncating toward zero), push the quotient. Then update prev_op to the current operator and reset num. This respects precedence because and / consume their operands immediately, while + and - defer.
Sum the stack for the final answer
After the loop, the stack holds all the additive terms. Sum them. Time is O(n) for the single pass, space is O(n) for the stack (which holds at most one entry per additive term in the expression).
Solution
Common pitfalls
Processing the number on the current operator instead of the previous one
if ch == '*':
stack.append(stack.pop() * num)if prev_op == '*':
stack.append(stack.pop() * num)The current operator tells you what to do with the next number, not the current one. The current number was preceded by prev_op. Confusing the two misapplies every operation.
Using Python's // for truncation toward zero on negative dividends
stack.append(stack.pop() // num)
stack.append(int(stack.pop() / num))
Python's // floors toward negative infinity: -7 // 2 = -4. The problem wants truncation toward zero: -7 / 2 = -3. Using int(a / b) truncates correctly. For this specific problem all inputs are non-negative, but the stack can hold negative values from subtraction.
Forgetting to process the last number after the loop ends
for ch in s:
if ch.isdigit():
num = num * 10 + int(ch)
else:
# process num
...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:
# process num
...The last number has no trailing operator. Without the i == len(s) - 1 check, the final number is never processed and the result is wrong.
Edge cases
The initial prev_op = '+' means the first number is pushed as a positive value, which is correct.
7 / -3Python's // rounds toward negative infinity, not toward zero. Use int(a / b) to truncate toward zero. However, all numbers in this problem are non-negative, so // works correctly here.
/ operations, e.g. 2 3 / 2Each or / pops and pushes immediately, so the operations chain correctly: push 2, then 2 3 = 6, then 6 / 2 = 3.