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
The 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. This approach respects precedence without explicit conversion to postfix notation.
Optimal Approach
Iterate through the string, building numbers digit by digit. When an operator or the end of the string is reached, apply the previous operator to the current number and the stack: '+' pushes the number, '-' pushes its negation, '*' and '/' pop the top of the stack and push the product or quotient. Finally, sum all values in the stack to get the result.
Time
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
| 7 | for i, c in enumerate(s): |
| 9 | if c.isdigit(): |
| 10 | num = num * 10 + int(c) |
| 12 | if c in "+-*/" or i == len(s) - 1: |
| 14 | if op == "+": |
| 15 | stack.append(num) |
| 17 | elif op == "-": |
| 18 | stack.append(-num) |
| 20 | elif op == "*": |
| 21 | stack.append(stack.pop() * num) |
| 23 | elif op == "/": |
| 24 | stack.append(int(stack.pop() / num)) |
| 26 | op = c |
| 27 | num = 0 |
Objective
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.
Key Insight
By applying the previous operator when a new operator or the string end is encountered, the algorithm ensures that multiplication and division are computed immediately with the top of the stack, while addition and subtraction push positive or negative numbers. This approach respects operator precedence without complex parsing or recursion.
Interview Quick-Check
Core Logic
The algorithm applies the previous operator to the current number and the stack, enabling immediate evaluation of '*' and '/' and deferral of '+' and '-' via stack pushes.
State & Boundaries
The condition 'c in "+-*/" or i == len(s) - 1' ensures the last number is processed even if the string ends without an operator.
Common Pitfalls & Bugs
Using int(stack.pop() / num) truncates division toward zero, matching problem requirements; using floor division would be incorrect for negative numbers.
Complexity
Each character is processed once, and stack operations are O(1), maintaining O(n) time complexity.
Sum Stack to Compute Final Result
| 29 | return sum(stack) |
Objective
To aggregate all deferred addition and subtraction results stored in the stack to produce the final evaluated value.
Key Insight
After all operators have been processed, the stack contains positive and negative integers representing the expression with multiplication and division already applied. Summing the stack yields the correct final result efficiently.
Interview Quick-Check
Core Logic
Summing the stack combines all deferred additions and subtractions, completing the evaluation.
Complexity
Summing the stack is O(n) in the worst case, but since each element corresponds to a number in the expression, this is efficient and linear.
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.
stack = []Initialize an empty stack to store intermediate results.
The stack is essential for deferring addition and subtraction while immediately computing multiplication and division, enabling correct operator precedence handling.
op = "+"Initialize 'op' to '+' to handle the first number correctly.
Setting 'op' to '+' ensures the first parsed number is pushed onto the stack as a positive number without special casing the first iteration.
if c in "+-*/" or i == len(s) - 1:Check if the current character is an operator or the last character in the string.
This condition triggers processing of the accumulated number with the previous operator, ensuring all numbers are handled, including the last one.
return sum(stack)Return the sum of all numbers in the stack as the final result.
Summing the stack combines all deferred additions and subtractions, yielding the correctly evaluated expression result after all precedence operations have been applied.
num = 0Initialize 'num' to accumulate multi-digit numbers.
Accumulating digits into 'num' allows parsing numbers that span multiple characters, which is necessary for correct evaluation.
num = num * 10 + int(c)Update 'num' by shifting previous digits and adding the new digit.
This line builds the current number by multiplying the existing 'num' by 10 and adding the integer value of the current digit, enabling parsing of numbers with multiple digits.
if op == "+":If the previous operator was '+', push the current number onto the stack.
Addition defers computation by pushing the number, allowing later summation after all higher precedence operations are resolved.
elif op == "-":If the previous operator was '-', push the negation of the current number onto the stack.
Subtraction is handled by pushing the negative of the number, effectively converting subtraction into addition of a negative number for later summation.
stack.append(stack.pop() * num)Push the product of the popped number and current number onto the stack.
This updates the stack with the multiplication result, integrating it into the deferred addition/subtraction framework.
stack.append(int(stack.pop() / num))Push the truncated division result onto the stack.
This updates the stack with the division result, maintaining the correct evaluation order.
if c.isdigit():Check if the current character is a digit.
Identifying digits is necessary to accumulate multi-digit numbers correctly.
stack.append(num)Push the current number onto the stack for addition.
Storing the number preserves it for final summation, deferring addition until all operators are processed.
stack.append(-num)Push the negated number onto the stack for subtraction.
This preserves the subtraction operation for final summation by representing it as addition of a negative number.
op = cUpdate the operator to the current character.
Storing the current operator prepares for processing the next number with the correct operation.
num = 0Reset 'num' to zero to start accumulating the next number.
Resetting 'num' is necessary to correctly parse the next multi-digit number without carrying over previous digits.
for i, c in enumerate(s):Iterate through each character and its index in the input string.
Processing each character sequentially allows building numbers and detecting operators in a single pass.
Test Your Understanding
Why does the algorithm use a stack and immediately compute multiplication and division but defer addition and subtraction?
Because multiplication and division have higher precedence, they must be computed immediately with the most recent number, while addition and subtraction can be deferred by pushing numbers onto the stack and summed at the end, ensuring correct order of operations.
Related Problems
Stacks 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