Expression Evaluation

What is this?

When you work out a sum like 2 + 3 * 4, you can't finish 2 + ... until you've handled 3 * 4 first — so you set the addition aside and come back to it. A stack is the perfect scratch pad for that: it holds the pieces of a calculation you can't finish yet, like a pile of sticky notes, and hands them back the moment the missing number arrives. This is exactly how calculators and programming languages add up expressions.

flowchart TD A["Read the next token"] --> B["A number"] A --> C["An operator"] B --> D["Push it on the stack"] C --> E["Pop the operands and combine"] E --> F["Push the result back"]

💡 Fun fact: Old HP calculators made you type sums "backwards" as 3 4 + instead of 3 + 4. That postfix style needs no parentheses at all, and it is exactly how a stack-based machine evaluates math under the hood.

🔓 The 2 problems in this chapter are free. Sign in with Google or Microsoft to start solving.

Core idea: Evaluating an expression is a stack story. The stack holds operands waiting for an operator, or a paused sub-expression waiting for its ). Whenever you can't finish a computation yet, you push the unfinished part; when the missing piece arrives, you pop and combine.

Why a stack is the natural fit

Arithmetic has deferred work baked in: you can't apply + until you have both operands, and a ( means "set this aside, I'll come back after the matching )." A stack is precisely the structure for "set aside the most recent unfinished thing and resume it later" — which is also why a CPU-less virtual machine evaluates code with an operand stack.

This chapter teaches the two canonical forms:

Flowchart: expression evaluation splits into infix with parentheses (Basic Calculator) and postfix RPN (Evaluate RPN)

The two problems

Basic Calculator — infix with parentheses

Scan left to right keeping a running result, the current_number, and the current sign. A ( pauses the current computation — push (result, sign) onto the stack and start fresh inside the parentheses. A ) finishes the inner value, then pops the saved context and folds it back in.

Basic Calculator stack pausing and resuming around parentheses in "1 + (2 - (3))"

A ( doesn't start a new problem — it pauses your current one. The stack is a hand-rolled call stack. → O(n) time, O(n) space.

Evaluate Reverse Polish Notation — postfix, the stack machine

In postfix the operator follows its operands, so no parentheses or precedence rules are needed. Push every number; on an operator, pop the top two, apply, push the result. The last value left is the answer.

Evaluate RPN operand stack machine processing ["4","1","+","3","*"] to 15

Mind the order: the first value popped is the right operand (matters for - and /), and division truncates toward zero. This loop is a miniature bytecode interpreter. → O(n) time, O(n) space.

The cross-cutting skill: what's on the stack?

Problem	Stack holds	Pop trigger
Basic Calculator	paused `(result, sign)` contexts	a `)` resumes the outer expression
Evaluate RPN	operands awaiting an operator	an operator consumes two operands

Both are "defer until you can combine." Infix defers around parentheses; postfix defers operands until their operator shows up. Name what the stack is holding and the code follows.

Common pitfalls

Operand order for - and /: b = pop(); a = pop(); a - b.
Truncation toward zero for division of negatives — in Python use int(a / b), not a // b.
Multi-digit numbers and spaces in the infix scanner — accumulate digits, skip blanks.
Sign handling around ( and leading/unary minus in the calculator.

📓 Draw it yourself

Pause & resume. For Basic Calculator, draw the stack each time you hit ( (push the saved result+sign) and ) (pop and fold back). Watch the outer computation freeze and thaw.
The RPN machine. Draw the operand stack as you scan ["5","1","2","+","*"]; circle the two operands an operator pops and the single result it pushes.

Snap photos and embed them with the /host-diagrams skill.

Complexity at a glance

Problem	Time	Space
Basic Calculator	O(n)	O(n)
Evaluate RPN	O(n)	O(n)

Key takeaways

The stack holds deferred work — paused sub-expressions (infix) or pending operands (postfix).
Parentheses = push/restore context; a ( pauses, a ) resumes — a hand-built call stack.
Postfix needs no precedence or parentheses — which is exactly why VMs and calculators use it.
Watch operand order and integer truncation — the two most common bugs here.
Why this chapter matters: it's the foundation of compilers, interpreters, and stack machines — the clearest place where "stack = deferred computation" pays off.

Order: Basic Calculator (infix + parens) → Evaluate RPN (the stack machine).

Foundations