Expression evaluation

39 s · title card, the worked example step by step, then a recap. The captions carry the explanation; there is no narration. Download the MP4.

01The intuition

Start with what you would do by hand

Work out 3 + 2 × 2 − 1. The school rule is that multiplication comes first: 2 × 2 = 4, then 3 + 4 − 1 = 6. Reading left to right you cannot add 3 + 2 the moment you see the plus, because the next operator might be a × that binds the 2 more tightly.

By hand you scan for the highest-precedence operator, apply it, rewrite, and scan again. Each scan is the whole expression, so that is O(n²) for n tokens. The question is how to decide, at each operator, what can be computed now and what must wait, in a single left-to-right pass.

Build the structure, one piece at a time

Piece one: an operand stack holding numbers that are waiting for a low-precedence operator (+ or −) to combine them. The final answer will be the sum of everything on the stack.

Piece two: remember the last operator seen. When a complete number arrives, act on the last operator:

• + : push the number.
• − : push the negated number. Subtraction becomes "add a negative", so the end is a plain sum.
• × or ÷ : these bind tighter than anything waiting on the stack, so apply them now to the top: pop it, combine with the new number, push the result.

Start with the last operator set to +. For 3 + 2 × 2 − 1:

Multi-digit numbers are accumulated digit by digit until a non-digit arrives. Parentheses add the nested-context idea from the previous pattern: push the stack and the last operator at "(", evaluate the inside, and treat its result as a number at ")". Reverse Polish notation (2 1 + 3 ×) removes precedence entirely: numbers push, an operator pops two and pushes the result.

Why it is correct

The invariant: the stack holds a list of terms whose sum equals the value of the expression read so far, where every × and ÷ has already been applied. A + pushes a new term; a − pushes a negative term, which is the same as subtracting; a × or ÷ modifies the most recent term, which is correct because × and ÷ apply to the number immediately before them and that number is exactly the top term, having not yet been added to anything. Precedence is honoured because the only thing a term can still be combined with is a × or ÷ that immediately follows it; by the time a + or − arrives, the term is final. The sum at the end is therefore the expression's value:

3 + 2 × 2 − 1 = (+3) + (+2 × 2) + (−1)

Why it is fast

Each token causes O(1) stack work: at most one pop and one push. So the pass is O(n) time and the stack holds at most one term per + or −, O(n) space, against O(n²) for repeated scanning. Integer division needs care with negatives: truncate toward zero, which in most languages means using the language's integer division on the absolute values and restoring the sign.

How to recognise it in an interview

Cues: "evaluate the expression", "calculator", "+, −, ×, ÷ with or without parentheses", "reverse Polish notation", "insert operators between digits to reach a target" (where the same last-term trick lets you undo a term when a × follows it). Say: "I will keep a stack of terms, push on + and −, apply × and ÷ immediately to the top, and sum the stack at the end."

Basic Calculator II is the example. Evaluate Reverse Polish Notation is the no-precedence version. Expression Add Operators is a backtracking search that uses the same "previous term" bookkeeping so that a × can be applied to the last term without recomputing.

02The idea in one line

Numbers to an operand stack; operators apply by precedence (or use RPN).

Reach for it when: Calculators, RPN, infix with +−×÷ and parentheses.

Cost: O(n) time.

03The walk-through, step by step

The video works one example: Basic Calculator II on '3+2*2-1'. These are its captions in order, so you can follow without the video or check a step you missed.

1. Push numbers; × and ÷ apply immediately to the top, + and − push a signed value
2. read digit 3: num = 3
3. pending '+': push 3, then remember '+'
4. read digit 2: num = 2
5. pending '+': push 2, then remember '×'
6. read digit 2: num = 2
7. pending '×': 2 × 2 = 4 replaces the top, then remember '-'
8. read digit 1: num = 1
9. pending '-': push -1
10. Sum the stack: 3 + 4 + -1 = 6
11. One pass, precedence handled by applying × ÷ eagerly: O(n)

04Asked at Google

6 Google-tagged LeetCode problems use this pattern. Frequency is LeetCode's Google-tag score (higher means reported more often); "last 6 months" marks problems reported in the most recent window of the export.

05Related patterns

Other patterns in Stack: Matching with a stack, Nested structure via stack, Auxiliary-min stack, Collision simulation.