Given a string s representing an expression, evaluate it and return the result. Integer division truncates toward zero. You may assume the expression is always valid.
Example 1
Input: s = "3+2*2"Output:7
Example 2
Input: s = " 3/2 "Output:1
Constraints
• 1 ≤ s.length ≤ 3 × 10⁵• s consists of integers, '+', '-', '*', '/', and spaces• Expression is valid• All intermediate results fit in 32-bit signed int
02
Section Two · Approach 1
Why Not Two Full Passes?
A naive idea is to tokenize the whole expression, then run one pass for *//, then another for +/-. That works, but the classic interview solution is cleaner: do everything in one left-to-right pass with a stack.
Observation:
Only * and / need immediate evaluation because they have higher precedence.
+ and - can be deferred by pushing signed numbers onto the stack.
03
Section Three · Approach
Single Pass + Stack — O(n)
Scan the string and build the current number digit by digit. Keep track of the previous operator. When you hit a new operator or the end of the string, apply the previous operator to the current number:
+ → push num
- → push -num
* → pop top, multiply, push result
/ → pop top, divide with truncation toward zero, push result
At the end, sum the stack. That works because all multiplication and division have already been collapsed into single values.
💡 Mental model: Think of the stack as a ledger of signed terms waiting to be added at the end. Addition and subtraction just append a new term. Multiplication and division don’t create a new term — they modify the most recent term because precedence says they bind tighter.
Why this is elegant:
You never need to build an expression tree or explicitly compare precedence between all operators.
The previous operator tells you exactly what to do with the current number.
04
Section Four · Trace
Visual Walkthrough
Trace "3+2*2":
Basic Calculator II — stack of signed terms
05
Section Five · Implementation
Code — Java & Python
Java — Single pass stack evaluation
import java.util.Stack;
classSolution {
publicintcalculate(String s) {
Stack<Integer> stack = newStack<>();
int num = 0;
char op = '+';
for (int i = 0; i < s.length(); i++) {
char c = s.charAt(i);
if (Character.isDigit(c)) {
num = num * 10 + (c - '0');
}
if ((!Character.isDigit(c) && c != ' ') || i == s.length() - 1) {
switch (op) {
case'+': stack.push(num); break;
case'-': stack.push(-num); break;
case'*': stack.push(stack.pop() * num); break;
case'/': stack.push(stack.pop() / num); break;
}
op = c;
num = 0;
}
}
int ans = 0;
while (!stack.isEmpty()) ans += stack.pop();
return ans;
}
}
Python — Single pass stack evaluation
classSolution:
defcalculate(self, s: str) -> int:
stack = []
num = 0
op = '+'for i, c in enumerate(s):
if c.isdigit():
num = num * 10 + int(c)
if ((not c.isdigit() and c != ' ') or i == len(s) - 1):
if op == '+':
stack.append(num)
elif op == '-':
stack.append(-num)
elif op == '*':
stack.append(stack.pop() * num)
else:
stack.append(int(stack.pop() / num)) # truncate toward 0
op = c
num = 0return sum(stack)
06
Section Six · Analysis
Complexity Analysis
Approach
Time
Space
Why
Single-pass stack
O(n)
O(n)
Each character is processed once; stack stores deferred signed terms.
07
Section Seven · Edge Cases
Edge Cases & Pitfalls
Case
Input
Why It Matters
Spaces
" 3/2 "
Must ignore spaces while still triggering evaluation at operators/end.
Multi-digit numbers
"14-3/2"
Build numbers digit by digit; do not treat each digit separately.
Precedence
"3+2*2"
* must apply before final addition.
Truncation toward zero
"0-3/2"
Result is -1, not -2. Python must use int(a / b).
⚠ Common Mistake: Updating the current operator too early. You must first apply the previous operator to the number you just finished reading, then store the new operator for the next number. Mixing up this order causes every term to be processed with the wrong operator.
