Basic Calculator II
Basic Calculator II: evaluate a string expression s containing non-negative integers and the operators +, -, *, / (integer division truncates toward zero). No parentheses.
- 1 <= s.length <= 3 * 10⁵
- s consists of integers and operators ('+', '-', '*', '/') separated by some number of spaces.
- s represents a valid expression.
- All the integers in the expression are non-negative integers in the range [0, 2³¹ - 1].
- The answer is guaranteed to fit in a 32-bit integer.
Intuition
Basic calculator ii evaluates an expression with +, -, *, and / but no parentheses. That trade is the whole character of the problem: the nesting from Basic Calculator is gone, and operator precedence arrives in its place.
Multiplication and division bind tighter than addition and subtraction, so 2 + 3 * 4 is 14, not 20. A left-to-right accumulation gives the wrong answer.
A stack resolves this cleanly by deferring the low-precedence work:
- Push values for + and -, but for * and / pop the previous value, combine immediately, and push the result back.
High-precedence operations are applied as soon as both operands are known; low-precedence ones are left on the stack. Summing the stack at the end performs all the additions in one step, and because subtraction was stored as a negative value, no sign tracking is needed at that point.
The implementation detail that makes this work is holding the previous operator, not the current one. When a number finishes, the operator that applies to it is the one seen before it — so the operator is recorded and acted upon one number later.
Division truncates toward zero, which differs from floor division for negative results. In Python, -3 // 2 is -2 while the problem wants -1, so int(a / b) or an explicit truncation is required.
As in the previous problem, the last number must be processed after the loop, since no trailing operator triggers it.
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
Before reading on: price up what the direct approach costs here, then ask what unresolved thing you are holding, and what event finally resolves it. Aim for O(n) time and O(n) space.
Recognise the precedence problem
* and / bind tighter than + and -, so 2 + 3 * 4 is 14. Left-to-right accumulation is wrong, and this is the only real difficulty here.
Defer the low-precedence work
Push values for + and - onto a stack rather than combining them. Leaving additions pending is what allows a later * to bind to the correct operand.
Apply high precedence immediately
For * or /, pop the previous value, combine with the current number, and push the result. Both operands are known at that moment, so nothing needs deferring.
Track the previous operator
When a number finishes, the operator governing it is the one seen before it. Record the operator and act on it one number later — mixing this up misapplies every operation.
Store subtraction as a negative
Push -num for - rather than tracking signs separately. The final sum then handles addition and subtraction uniformly with no extra state.
Truncate division toward zero
Division truncates toward zero, not floor. In Python -3 // 2 gives -2 but the answer must be -1, so use int(a / b) or truncate explicitly.
Process the last number and sum
Handle the final number after the loop, since no trailing operator triggers it. Summing the stack then completes every deferred addition at once.
Cost of the scan
Each character is read once and each value pushed and popped at most once, giving O(n) time and O(n) space for the stack.
Solution & live demo
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.
** and / 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.