Coding Interview PatternsBasic Calculator II
MediumStacks
Basic Calculator II
Explanation & Solution
Description
Given a string s which represents an expression, evaluate this expression and return its value.
The integer division should truncate toward zero.
You may assume that the given expression is always valid. All intermediate results will be in the range of [-2^31, 2^31 - 1].
Note: You are not allowed to use any built-in function which evaluates strings as mathematical expressions, such as eval().
Input: s = "3+2*2"
Output: 7
Constraints
1 <= s.length <= 3 * 10^5sconsists of integers and operators ('+','-','*','/') separated by some number of spacessrepresents a valid expression- All the integers in the expression are non-negative and in the range
[0, 2^31 - 1] - The answer is guaranteed to fit in a 32-bit integer
Approach
Stacks pattern
1. Deferred Evaluation with Previous Operator
- Track the previous operator (
prevOp) instead of the current one - Build multi-digit numbers as you scan
2. Process When Encountering an Operator (or end of string)
- Based on
prevOp: '+': Pushnumonto the stack'-': Push-numonto the stack'*': Pop the top, multiply bynum, push the result'/': Pop the top, divide bynum(truncate toward zero), push the result- Reset
num = 0and updateprevOp
3. Handle Operator Precedence
*and/are evaluated immediately by modifying the top of the stack+and-are deferred by pushing values onto the stack- This naturally handles precedence without parentheses
4. Sum the Stack
- After processing all characters, sum all values in the stack for the final result
Key Insight
- By deferring
+and-and immediately resolving*and/, the stack handles operator precedence elegantly - Time: O(n), Space: O(n)
Visualization
Input:
[3, +, 2, *, 2]
—
Press ▶ or use ← → to step through
Left (L)Right (R)ConvergedDone
4 steps