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).

Evaluate Reverse Polish Notation

Core idea: Walk the tokens once — push numbers onto a stack, and when you hit an operator, pop the two operands waiting for it, combine them, and push the answer back.

Problem, rephrased

You're building the "compute" engine for a tiny pocket calculator. Instead of typing (3 + 4) × 2 with parentheses, the user enters keystrokes in postfix order: they punch in both numbers first, then the operation that joins them. So 3 + 4 is keyed as 3 4 +, and (3 + 4) × 2 becomes 3 4 + 2 *.

You receive those keystrokes as a list of string tokens. Each token is either:

an integer (possibly negative, e.g. "7", "-200"), or
one of four operators: "+", "-", "*", "/".

Evaluate the whole expression and return the final integer.

What is postfix (Reverse Polish Notation)?

In ordinary infix notation the operator sits between its operands (a + b), which forces us to invent precedence rules and parentheses to say what binds first. In postfix the operator comes right after the two values it acts on. There is no ambiguity and there are no parentheses — the position of each operator already tells you exactly which two values it consumes.

Infix:   ( 3 + 4 ) * 2
Postfix:   3   4 +   2 *

Inputs and outputs

`tokens`	Reads as	Output
`["3","4","+","2","*"]`	`(3 + 4) * 2`	`14`
`["5"]`	`5`	`5`
`["6","-8","/"]`	`6 / (-8)`	`0`
`["2","1","+","3","*"]`	`(2 + 1) * 3`	`9`

One rule to burn in now: division truncates toward zero, not toward negative infinity. So -7 / 2 is -3, not -4.

Sign in to continue reading

The rest of this lesson is available with a free account. Signing in with Google or Microsoft is free.

Foundations