Basic Calculator II
Problem
Given a string s representing a valid arithmetic expression containing non-negative integers and the operators +, -, *, and /, return the result of evaluating the expression. The integer division should truncate toward zero.
- 1 ≤ s.length ≤ 3 * 10⁵
- s consists of integers and operators '+', '-', '*', '/'
- s is a valid expression
- All intermediate results fit in a 32-bit integer
Example
s = "3+2*2"7The expression evaluates as follows: first, multiplication has higher precedence, so 2*2 = 4. Then addition: 3 + 4 = 7. The algorithm processes the string left to right, accumulating numbers and applying operators respecting precedence by using a stack. When it encounters '*', it multiplies the top of the stack by the current number. When it encounters '+', it pushes the number onto the stack. At the end, summing the stack yields the final result.
Approach
Straightforward Solution
A naive approach would parse the expression and evaluate strictly left to right, ignoring precedence, which yields incorrect results. Alternatively, converting to postfix notation and then evaluating is possible but requires extra parsing steps and data structures.
Core Observation
Arithmetic expressions without parentheses but with operators of different precedence require careful ordering of operations. Multiplication and division must be evaluated before addition and subtraction to respect operator precedence.
Path to Optimal
PreviewThe key insight is to process the expression in one pass using a stack to handle precedence. Addition and subtraction push numbers onto the stack, while multiplication and division immediately combine with the top of the stack…
Full step-by-step walkthrough on Pro →
Optimal Approach
PreviewIterate through the string, building numbers digit by digit…
Full step-by-step walkthrough on Pro →
Want the full reasoning chain?
Unlock the complete walkthrough, line-by-line analysis, and recall drill.
Unlock ProTime
O(n)
The algorithm iterates through the input string once, performing constant-time operations per character, resulting in linear time complexity.
Space
O(n)
In the worst case, the stack can hold all numbers if the expression contains only additions and subtractions, requiring linear auxiliary space proportional to the input size.
Pattern Spotlight
Stack (Operator Precedence Handling)
Use a stack to defer addition and subtraction by pushing numbers, but immediately compute multiplication and division by combining with the top of the stack, enabling a single-pass evaluation that respects operator precedence without explicit parsing or recursion.
Solution
| 1 | class Solution: |
| 2 | def calculate(self, s: str) -> int: |
| 3 | stack = [] |
| 4 | num = 0 |
| 5 | op = "+" |
| 6 | |
| 7 | for i, c in enumerate(s): |
| 8 | |
| 9 | if c.isdigit(): |
| 10 | num = num * 10 + int(c) |
| 11 | |
| 12 | if c in "+-*/" or i == len(s) - 1: |
| 13 | |
| 14 | if op == "+": |
| 15 | stack.append(num) |
| 16 | |
| 17 | elif op == "-": |
| 18 | stack.append(-num) |
| 19 | |
| 20 | elif op == "*": |
| 21 | stack.append(stack.pop() * num) |
| 22 | |
| 23 | elif op == "/": |
| 24 | stack.append(int(stack.pop() / num)) |
| 25 | |
| 26 | op = c |
| 27 | num = 0 |
| 28 | |
| 29 | return sum(stack) |
Step-by-Step Solution
Initialize Stack and State Variables for Expression Evaluation
| 3 | stack = [] |
| 4 | num = 0 |
| 5 | op = "+" |
Objective
To prepare data structures and variables to track the current number, the last operator, and the stack for deferred operations.
Key Insight
The stack holds intermediate results, allowing deferred addition and subtraction. The variable 'num' accumulates multi-digit numbers as the string is parsed. The variable 'op' stores the last operator encountered, initializing to '+' to handle the first number correctly. This setup enables a clean single-pass evaluation respecting operator precedence.
Interview Quick-Check
Core Logic
Initializing 'op' to '+' ensures the first number is pushed onto the stack correctly without special casing.
State & Boundaries
Tracking 'num' as a running number allows parsing multi-digit integers from consecutive digits.
Common Pitfalls & Bugs
Forgetting to reset 'num' after processing a number leads to incorrect accumulation of digits.
Parse Expression and Apply Operators with Precedence Using Stack
To iterate through the expression, build numbers, and apply the previous operator to the stack when an operator or the end of the string is reached.
Sum Stack to Compute Final Result
To aggregate all deferred addition and subtraction results stored in the stack to produce the final evaluated value.
2 more steps with full analysis available on Pro.
Line Analysis
This solution has 2 Critical lines interviewers watch for.
elif op == "*":If the previous operator was '*', pop the top of the stack and multiply it by the current number, then push the result.
Multiplication has higher precedence and must be computed immediately with the most recent number, ensuring correct order of operations.
elif op == "/":If the previous operator was '/', pop the top of the stack and divide it by the current number, truncating toward zero, then push the result.
Division must be computed immediately with the top of the stack to respect precedence, and truncation toward zero matches problem requirements, which differs from floor division.
Full line-by-line criticality + rationale for all 18 lines available on Pro.
Test Your Understanding
Why does the algorithm use a stack and immediately compute multiplication and division but defer addition and subtraction?
See the answer with Pro.
Related Problems
Monotonic Stack pattern
Don't just read it. Drill it.
Reconstruct Basic Calculator II from memory until it sticks. AlgoDrill blanks out key lines and makes you fill them back in, step by step.
Unlock the Basic Calculator II drill