Stacks for Expressions

algorithmintermediateTime O(n)Space O(n)

A stack remembers what is still pending in the order it must be resolved: the most recent thing first. That is exactly what nested brackets need, since the last opened bracket is the first one that must close. Postfix notation removes the need for brackets altogether, because every operator arrives right after the two values it applies to, so a value stack is all the evaluator needs. Converting infix to postfix, or evaluating infix directly, is the same idea with operators waiting on a stack until something of lower precedence arrives and forces them out.

Evaluate "(3+4)*2-8/4" in one pass with two stacks. Numbers go on the value stack. An operator first reduces any operator on the stack with precedence at least its own (pop two values, apply, push the result), then waits. Brackets fence the operator stack.

Check your understanding

The player pauses before each decision in this run and asks what happens next. Here are all 11, with their answers.

Next is '('. What happens?
- Push it
- Reduce first, then push
- Reduce back to the bracket
Answer: Push it. Nothing on the stack outranks it, so it simply waits.
Next is '3', top operator is '('. What happens?
- Push it
- Reduce first, then push
- Reduce back to the bracket
Answer: Push it. Nothing on the stack outranks it, so it simply waits.
Next is '+', top operator is '('. What happens?
- Push it
- Reduce first, then push
- Reduce back to the bracket
Answer: Push it. Nothing on the stack outranks it, so it simply waits.
Next is '4', top operator is '+'. What happens?
- Push it
- Reduce first, then push
- Reduce back to the bracket
Answer: Push it. Nothing on the stack outranks it, so it simply waits.
Next is ')', top operator is '+'. What happens?
- Push it
- Reduce first, then push
- Reduce back to the bracket
Answer: Reduce back to the bracket. A closing bracket finishes everything since its opener.
Next is '*'. What happens?
- Push it
- Reduce first, then push
- Reduce back to the bracket
Answer: Push it. Nothing on the stack outranks it, so it simply waits.
Next is '2', top operator is '*'. What happens?
- Push it
- Reduce first, then push
- Reduce back to the bracket
Answer: Push it. Nothing on the stack outranks it, so it simply waits.
Next is '-', top operator is '*'. What happens?
- Push it
- Reduce first, then push
- Reduce back to the bracket
Answer: Reduce first, then push. An operator of equal or higher precedence must be applied first.
Next is '8', top operator is '-'. What happens?
- Push it
- Reduce first, then push
- Reduce back to the bracket
Answer: Push it. Nothing on the stack outranks it, so it simply waits.
Next is '/', top operator is '-'. What happens?
- Push it
- Reduce first, then push
- Reduce back to the bracket
Answer: Push it. Nothing on the stack outranks it, so it simply waits.
Next is '4', top operator is '/'. What happens?
- Push it
- Reduce first, then push
- Reduce back to the bracket
Answer: Push it. Nothing on the stack outranks it, so it simply waits.

How it runs, step by step

Evaluate "(3+4)*2-8/4" in one pass with two stacks. Numbers go on the value stack. An operator first reduces any operator on the stack with precedence at least its own (pop two values, apply, push the result), then waits. Brackets fence the operator stack.
Infix evaluation with a value stack and an operator stack.
'('. An opening bracket fences the operator stack.
Character (. Values empty, operators (.
'3'. A number: push it on the values.
Character 3. Values 3, operators (.
'+'. Nothing to reduce, so it waits on the operator stack.
Character +. Values 3, operators (+.
'4'. A number: push it on the values.
Character 4. Values 3 4, operators (+.
')'. A closing bracket reduces back to its opener: 3 + 4 = 7. The '(' is discarded.
Character ). Values 7, operators empty.
'*'. Nothing to reduce, so it waits on the operator stack.
Character *. Values 7, operators *.
'2'. A number: push it on the values.
Character 2. Values 7 2, operators *.
'-'. The stack outranks it, so reduce first: 7 * 2 = 14. Then '-' waits.
Character -. Values 14, operators -.
'8'. A number: push it on the values.
Character 8. Values 14 8, operators -.
'/'. '-' binds looser, so it waits and '/' goes on top.
Character /. Values 14 8, operators -/.
'4'. A number: push it on the values.
Character 4. Values 14 8 4, operators -/.
The end of input reduces what is left: 8 / 4 = 2, 14 - 2 = 12. Result 12. Each token is pushed and popped at most once: O(n).
Result 12.

Write it yourself

Define isBalanced(expression) and return true when every bracket closes in the right order. It runs in your browser against this lesson's own 2 examples.

1// Push an opening bracket, and a closing one must match what comes off the top. Anything left over at the end is unclosed.2function isBalanced(expression) {3  4  return false;5}6

Ln 1, Col 16 linesTab indents; Escape then Tab leaves the editor. Ctrl-Enter runs, Cmd-Enter on a Mac.

Remember

Brackets: push openers, and a closer must match the top of the stack. Balanced means the stack ends empty.
Postfix: push numbers; an operator pops two (the lower one is the left operand) and pushes the result.
Infix: an operator flushes everything on the stack with precedence at least its own, then waits; brackets fence the stack.

Topics covered

Where this is used

Document formatsPDF page content and PostScript

A PDF page is drawn by a stream of postfix operators, so 1 0 0 1 72 720 cm pushes six numbers and then names the operator that consumes them. Every operator takes a fixed count of operands that are already on the stack, so the renderer needs no precedence table and no lookahead, and it can draw while the stream is still arriving. PostScript, the older format PDF's drawing model grew out of, takes the same design all the way to a programming language, with the operand stack exposed to the program itself.

RuntimesJVM bytecode and WebAssembly

Both are stack machines, so a + b compiles to iload_1, iload_2, iadd, which is postfix. The compiler produces that order by walking the expression tree in post-order, the same rearrangement the infix-to-postfix pass does here, and a stack interpreter can then run it with exactly the postfix loop above, though production engines compile it down to registers instead. Both formats are checked before they run: the JVM verifier and the WebAssembly validator work out the stack's types at every instruction, so each pop is proved in advance to find the operand types it expects.

CompilersBracket errors in the CPython tokenizer

CPython's tokenizer keeps a stack of open brackets together with the line and column where each was opened. That is what lets Python 3.10 and later say which opener a mismatched closer belongs to, instead of pointing vaguely at the end of the file. The same stack decides whether a newline ends a statement: while it is non-empty you are inside brackets, so the line just continues, which is why a list literal can span many lines with no backslashes.

HardwareRPN calculators and Forth

The HP-35 and the HP-12C have no equals key and no brackets: you push operands with ENTER and each operator pops what it needs. On a machine with a few hundred bytes of memory, a value stack plus a pop-per-operator rule is far less hardware than an infix parser carrying a precedence table and a bracket stack. Forth, and the Open Firmware boot environments built on it, made the same trade to stay small enough to live in ROM.

Why it works this way

Why a stack and not a counter

With one kind of bracket a counter is enough: add one for an opener, subtract one for a closer, and it goes negative exactly when a closer arrives too early. With three kinds it fails, because ([)] and ([]) keep the same count at every step and both end at zero. What has to be remembered is not how many brackets are open but which one is innermost, and only the stack holds that.

Why the flush test is >= and not >

That comparison is where associativity lives. In 8/4/2 the second slash arrives while the first is still on the stack at equal precedence, so >= flushes it and you get (8/4)/2 = 1, which is what left-associative division means. Change it to > and the first slash waits its turn, producing 8/(4/2) = 4, while every expression with a single operator still comes out right. Right-associative operators such as exponentiation are the exception and need > for exactly this reason.

The two pops come off in reverse

Taking b before a is not a stylistic choice: the stack hands back the right operand first, because it was pushed last. Swap those two lines and + and * keep giving correct answers while - and / quietly stop, so 5 3 - evaluates to -2 instead of 2. It is a bug that passes half of any test set you throw at it.

Postfix only drops brackets if every operator has a fixed arity

Postfix reads unambiguously because seeing an operator tells you exactly how many values to pop. Unary minus breaks that rule: in 3 - -4 the same character means two different things, and once both are written as a bare - in the output nothing can tell them apart. Real converters give unary minus its own token and decide which one it is from position: a minus that follows another operator or an opening bracket, or that starts the expression, is the unary one.

Shunting yard algorithmWikipedia
Reverse Polish notationWikipedia
Expression parsingcp-algorithms
The Structure of the Java Virtual MachineJava Virtual Machine Specification · docs.oracle.com
Operator-precedence parserWikipedia