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.

Read 3+22 left to right and your instinct is to add 3+2=5 right away. That's a trap: the 2 that follows means the second 2 actually belongs to the multiplication, not the addition. Multiplication and division bind tighter than + and -, so a number isn't safe to add until you're sure no or / is about to claim it. That means you must be able to reach back for the most recent* number and revise it.

Reaching the most recent item first is what a stack is for. A stack is a pile touched only from the top: push puts a value on top, pop takes the top one off, last-in-first-out. Keep the terms that are ready to be summed on a stack; when a * or / arrives, pop the top term, combine it with the current number, and push the result back.

Track the number you're currently building, and the operator that came just before it (pretend the expression starts with a +). You apply that pending operator only when you reach the next operator (or the end of the string) — because only then is the number complete.
- + → the previous number stands on its own; push it.
- - → push its negative (subtracting is just adding a negative number).
- → the previous number must combine now*: pop the top of the stack, multiply by the current number, push the result back.
- / → same, but divide.

Why this respects precedence: by the time you sum the stack, every and / has already been folded into a single value sitting on top, so a plain addition of the leftovers is automatically correct. The 3 waits untouched at the bottom while 22 collapses into 4 above it.

python
def calculate(s):
    stack = []
    num = 0
    prev_op = '+'                 # pretend the expression opens with a +
    for i, ch in enumerate(s):
        if ch.isdigit():
            num = num * 10 + int(ch)
        # an operator, OR the last char: time to resolve prev_op
        if ch in '+-*/' or i == len(s) - 1:
            if   prev_op == '+': stack.append(num)
            elif prev_op == '-': stack.append(-num)
            elif prev_op == '*': stack.append(stack.pop() * num)
            else:                stack.append(int(stack.pop() / num))  # truncate
            prev_op = ch
            num = 0
    return sum(stack)
Crucial Noteyou resolve the previous operator when you meet the current one — the operator tells you what to do with the number that came before it. That's also why the two if checks aren't an if/elif: the last character is a digit and the trigger to flush the final term, so both must run for it. Spaces need no special case — a space is neither a digit nor an operator, so it's skipped, and multi-digit numbers keep accumulating across them. Use int(a / b) (not //) so division truncates toward zero: // rounds toward negative infinity and would give the wrong sign on negative results.
Worked Example:3+5/2
- 3 → num=3 · + → resolve prev +: push 3 → [3]; prev_op=+, num=0
- 5 → num=5 · / → resolve prev +: push 5 → [3, 5]; prev_op=/, num=0
- 2 → num=2, and it's the last char → resolve prev /: pop 5, int(5/2)=2, push → [3, 2]
- Sum [3, 2] = 5

A stack lets the tight-binding operators (, /) grab the newest number immediately while the loose ones (+, -) sit and wait to be summed at the end. Operator precedence is really just a question of who gets first claim on the most recent number.*

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