Algorithm

Basic Calculator II

Stacks & Queues Pattern

Basic Calculator II

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^3^1, 2^3^1 - 1]. Note: You are not allowed to use any built-in function which evaluates strings as mathematical expressions.

CONSTRAINTS
  • 1 <= s.length <= 3 * 10⁵
  • s consists of integers and operators (+, -, *, /) separated by optional spaces
  • The answer is guaranteed to fit in a 32-bit integer
EXAMPLE 1
Input: s = "3+2*2"
Output: 7
Encounter *: pop 2, compute 2*2=4, push 4. Stack=[3,4]. Sum=7.
EXAMPLE 2
Input: s = " 3/2 "
Output: 1
3/2 truncated toward zero = 1. Sum=1.
EXAMPLE 3
Input: s = " 3+5 / 2 "
Output: 5
5/2=2 (truncated). Stack=[3,2]. Sum=5.
Can the expression contain spaces?
Yes. Skip all whitespace characters while parsing. Apply the action only when you hit an operator or reach the end of the string.
Can numbers be multi-digit?
Yes. Build the number digit-by-digit: currentNum = currentNum * 10 + int(digit). Flush it when you hit an operator or end-of-string.

If you see the expression 3 + 2, your brain wants to add them immediately to get 5. But if the next part of the string is * 10, that addition would be a mistake! In math, multiplication and division always take priority. The 2 must stay attached to the 10, leaving the 3 to wait.

This is why we use a Stack. It acts like a Holding Shelf for numbers that haven't been added yet. When we see 3 + 2, we put the 3 on the shelf first. The 2 then joins it on the shelf, waiting to be added. But if we then see * 10, that multiplication operator is impatient—it snatches the 2 right back off the shelf, multiplies it by 10, and puts the new result (20) back on the shelf. The 3 stays on the shelf the whole time, waiting for the final additions to happen at the very end.

The Waiting Room

- Low Priority (+, -): These are patient. We Push the number onto the Stack. If it was a minus, we push it as a negative number (e.g., -5). Now they wait.
- High Priority (*, /): These are impatient! They refuse to wait in the Stack. We Pop the most recent number from the Stack, perform the multiplication or division immediately, and then push the result back into the Stack.
- The Final Audit: Once we reach the end of the string, the Waiting Room (Stack) only contains numbers that have been fully resolved. We just add them all up to get the final answer.

Code Blueprint
text
stack = []
current_num = 0
last_op = '+'

FOR each character (+ end of string):
    IF char is Digit:
        current_num = (current_num * 10) + digit
    
    IF char is Operator OR End of String:
        IF last_op is '+':  stack.PUSH(current_num)
        IF last_op is '-':  stack.PUSH(-current_num)
        IF last_op is '*':  stack.PUSH(stack.POP() * current_num)
        IF last_op is '/':  stack.PUSH(stack.POP() / current_num)
        
        last_op = current_char
        current_num = 0

RETURN SUM(stack)
Worked Example:3+5/2
0
3
Top
Scan '3': It is a number. prev_op is '+', so we push +3 onto the stack. Stack = [3].
0
3
1
5
Top
Scan '+': Update prev_op = '+'. Scan '5': Number. prev_op is '+', so push +5. Stack = [3, 5].
0
3
1
2
Top
Scan '/': Update prev_op = '/'. Scan '2': Number. Since prev_op is '/', pop top element (5), divide by 2 (5 / 2 = 2), and push result 2. Stack = [3, 2].
0
3
1
2
End of string reached. Sum all numbers on stack: 3 + 2 = 5. Return 5.
Interactive Strategy Visualization
PARSING ENGINE INSIGHT

Evaluating Infix with Operator Precedence

Input expression tape
3
+
2
*
4
Calculation Stack
Empty
Parser State
CURRENT CONTEXT
Active Num0
Last Sign+
Processing Logic

Start with '+' as default sign and 0 as current number.

Lazy Evaluation Strategy

Evaluate * and / greedily on the stack top; postpone + and - until the end.

O(N) One Pass · O(N) Stack of Pending Terms