Skip to content
Hari KharelStudy

Expression evaluation

intermediateCommon atStripeAnthropicGoogleMetaRead firstParsing and tokenizingStacksBinary treesPractise in the Sandbox →

Infix text hides the order of operations; precedence (* before +) and associativity (8 - 3 - 2 groups to the left) recover it. Either convert to postfix with Dijkstra’s shunting-yard (an operator stack plus an output queue) and evaluate that with a value stack, or parse into a syntax tree and evaluate it bottom-up. Every approach is O(n) time and O(n) space.

The idea in plain words

Section titled “The idea in plain words”

3 + 4 * 2 is 11, not 14. You know that because of a rule learned at school, not because of the order the symbols appear in. A program has to rebuild that hidden order.

There are two classic ways to write an expression so the order is explicit:

  • Postfix (Reverse Polish notation, RPN): operators come after their operands. 3 + 4 * 2 becomes 3 4 2 * +. Read left to right with a stack: push numbers; an operator pops two, computes, pushes the result. No parentheses, no precedence rules.
  • A syntax tree (AST): each operator is a node whose children are its operands. The tightest-binding operators sit deepest, so evaluating children first gives the right order.

Getting from infix to either form needs two rules:

  • Precedence: which operator binds tighter. * and / beat + and -; ^ beats both.
  • Associativity: how to group operators of the same precedence. Most are left-associative: 8 - 3 - 2 is (8 - 3) - 2 = 3. Exponent is usually right-associative: 2 ^ 3 ^ 2 is 2 ^ (3 ^ 2) = 512.

The shunting-yard algorithm, published by Edsger Dijkstra in 1961, is named after a railway yard: numbers run straight through to the output track, while operators wait on a side track (a stack) until it’s their turn.

See it

Section titled “See it”

Edit the expression or pick a preset and step through. Phase 1 builds the postfix output; phase 2 evaluates it; the last frame shows the syntax tree the same postfix describes. Untick ^ is right-associative and run 2 ^ 3 ^ 2 again to see the answer change from 512 to 64.

Shunting-yard: infix → postfix → value
step through
input tokens
3
+
4
*
(
2
-
1
)
^
2
^
1
output queue (postfix)
(empty)
(empty)
operator stack
phase1: to postfix
reading–
current token / just pushednumber to outputoperator popped to outputalready read
Read tokens left to right. Numbers go straight to the output queue. Operators wait on a stack until we know nothing tighter-binding comes next.
1 / 32

When to reach for it

Section titled “When to reach for it”
The problem says… Why this fits
“evaluate an arithmetic / boolean / filter expression given as a string” You need precedence and grouping, which split can’t give you.
operators of different strength, or parentheses Precedence and parentheses are exactly what the operator stack (or grammar levels) handle.
“the same expression is evaluated many times with different variables” Parse once into a tree or postfix list, then evaluate it cheaply for each environment.
“print / simplify / differentiate the expression” You need the structure, not just the value: build the tree.
input already in postfix (stack machines, calculators, bytecode) Skip the parse and run the value-stack loop directly.

How it works

Section titled “How it works”

Shunting-yard: infix to postfix

Section titled “Shunting-yard: infix to postfix”
  1. Read tokens left to right. A number goes straight to the output queue.
  2. An operator o: while the top of the operator stack is an operator that binds tighter than o, or equally tight with o left-associative, pop it to the output. Then push o.
  3. ( is pushed as a wall. ) pops operators to the output until the matching (, then discards both.
  4. At the end, pop every remaining operator to the output. A leftover ( means unbalanced parentheses.

The pop rule in step 2 is the whole algorithm. It says: an operator that is already waiting and must be applied first leaves now. “Equal and left-associative” makes 8 - 3 - 2 apply the first - first. Leaving out the equal case would build 8 - (3 - 2).

Evaluating postfix

Section titled “Evaluating postfix”

The postfix list is a tiny program for a stack machine. This is the second phase of the visualization:

eval_rpn.py
import operator
from collections.abc import Callable


OPS: dict[str, Callable[[float, float], float]] = {
    "+": operator.add, "-": operator.sub, "*": operator.mul,
    "/": operator.truediv, "^": operator.pow,
}




def eval_rpn(tokens: list[str]) -> float:
    """Evaluate postfix (Reverse Polish) notation, e.g. ["3", "4", "+", "2", "*"] -> 14."""
    stack: list[float] = []
    for tok in tokens:
        if tok in OPS:
            if len(stack) < 2:                    # 2. an operator needs two operands
                raise ValueError(f"not enough operands for {tok!r}")
            right = stack.pop()                   # 3. pop RIGHT first: the stack reverses order
            left = stack.pop()
            stack.append(OPS[tok](left, right))   # 4. the result is an operand for later ops
        else:
            stack.append(float(tok))              # 1. operands wait on the stack
    if len(stack) != 1:                           # 5. exactly one value must remain
        raise ValueError(f"malformed expression: {len(stack)} values left")
    return stack[0]




if __name__ == "__main__":
    assert eval_rpn(["3", "4", "+", "2", "*"]) == 14        # (3 + 4) * 2
    assert eval_rpn(["10", "4", "-"]) == 6                  # order matters: 10 - 4
    assert eval_rpn(["2", "3", "2", "^", "^"]) == 512       # 2 ^ (3 ^ 2)
    for bad in (["1", "+"], ["1", "2"], []):
        try:
            eval_rpn(bad)
            raise AssertionError(f"expected ValueError for {bad}")
        except ValueError:
            pass
    print("ok")

Note step 3: the right operand comes off the stack first. Popping in the wrong order makes 10 4 - evaluate to -6.

Grammar levels: the recursive-descent way

Section titled “Grammar levels: the recursive-descent way”

The other common approach writes precedence into the grammar itself, one rule per level, loosest first:

expr   := term   ( ('+' | '-') term )*
term   := factor ( ('*' | '/') factor )*
factor := number | '(' expr ')'

Each rule becomes a function, as in recursive descent. expr can only combine terms, and a term has already swallowed every * it could, so * ends up deeper in the tree than +. The ( … )* loop builds left-associative chains: it folds each new operand onto the result so far. A right-associative operator calls its own rule recursively for the right side instead of looping.

Evaluating a syntax tree

Section titled “Evaluating a syntax tree”

Whichever parser you use, a tree is the most flexible result. Evaluation is a post-order walk: children first, then the node’s operator. The same precedence table also tells a printer where parentheses are needed:

evaluate and show.py
from dataclasses import dataclass


PREC = {"+": 1, "-": 1, "*": 2, "/": 2, "^": 3}
RIGHT_ASSOC = {"^"}




@dataclass(frozen=True)
class Num:
    value: float




@dataclass(frozen=True)
class Bin:
    op: str
    left: "Node"
    right: "Node"




Node = Num | Bin




def evaluate(n: Node) -> float:
    match n:                                   # 1. a leaf is its own value
        case Num(v):
            return v
        case Bin(op, l, r):                    # 2. evaluate children first (post-order)...
            a, b = evaluate(l), evaluate(r)
            match op:                          # ...then apply this node's operator
                case "+": return a + b
                case "-": return a - b
                case "*": return a * b
                case "/": return a / b         # raises ZeroDivisionError on b == 0
                case "^": return a ** b
    raise ValueError(f"unknown node {n!r}")




def show(n: Node) -> str:
    """Print with the fewest parentheses that keep the same tree."""
    if isinstance(n, Num):
        return f"{n.value:g}"


    def side(child: Node, is_right: bool) -> str:
        s = show(child)
        if isinstance(child, Bin):
            lower = PREC[child.op] < PREC[n.op]                    # 3. looser child needs parens
            same_wrong_side = PREC[child.op] == PREC[n.op] and (   # 4. equal precedence: parens
                is_right != (n.op in RIGHT_ASSOC))                 #    on the side assoc. won't group
            if lower or same_wrong_side:
                return f"({s})"
        return s


    return f"{side(n.left, False)} {n.op} {side(n.right, True)}"




if __name__ == "__main__":
    t = Bin("*", Bin("+", Num(1), Num(2)), Num(4))
    assert evaluate(t) == 12 and show(t) == "(1 + 2) * 4"
    assert show(Bin("-", Num(8), Bin("-", Num(3), Num(2)))) == "8 - (3 - 2)"
    assert show(Bin("-", Bin("-", Num(8), Num(3)), Num(2))) == "8 - 3 - 2"
    assert show(Bin("^", Num(2), Bin("^", Num(3), Num(2)))) == "2 ^ 3 ^ 2"
    assert evaluate(Bin("^", Bin("^", Num(2), Num(3)), Num(2))) == 64
    print("ok")

Steps 3 and 4 are the mirror image of the shunting-yard pop rule. A child needs parentheses when it binds looser than its parent, or equally tight on the side associativity doesn’t group: 8 - (3 - 2) needs them, 8 - 3 - 2 doesn’t.

What it costs

Section titled “What it costs”
Time Extra space
Shunting-yard (infix → postfix) O(n): each token is pushed and popped at most once O(n) operator stack + output
Evaluate postfix O(n) O(n) value stack
Recursive descent / Pratt → tree O(n) O(n) tree, O(depth) call stack
Evaluate a tree O(n) nodes O(depth) recursion

The while loop inside shunting-yard looks quadratic but isn’t: an operator is popped at most once, so the total number of pops across the whole run is at most the number of operators. That’s the same amortized argument as in the sliding window page.

Parse-once matters when the same formula runs many times (a spreadsheet, a pricing rule, a query filter): parsing is O(n) once, and each evaluation is a single O(n) walk with no string work.

Variations you’ll meet

Section titled “Variations you’ll meet”
  • Unary minus. - means negation when it appears where an operand is expected: at the start, after (, or after another operator. The tokenizer or parser must look at the previous token to tell. Give it its own symbol (say neg) with higher precedence than the binary operators, and decide where it sits relative to ^: in maths, -2 ^ 2 is -4.
  • Pratt parsing (top-down operator precedence, Vaughan Pratt 1973). Each token type gets a binding power and two optional handlers: one for when it starts an expression (prefix: numbers, (, unary -) and one for when it follows one (infix: +, *). A single loop “keeps eating operators whose binding power is above my minimum”. It handles prefix, infix, postfix and mixfix operators in one small function and is what many real compilers use. Precedence climbing is the same idea, described differently.
  • Variables and environments. A name evaluates to a lookup in a map passed to evaluate. Decide what a missing name does: throw, return a sentinel, or report it as a validation error before evaluating.
  • Functions and commas. max(a, b) adds a function token and an argument separator. In shunting-yard, a function name is pushed like (; a comma pops to the nearest (.
  • Short-circuit operators. a && b must not evaluate b when a is false. Postfix evaluates everything, so either compile to jumps or evaluate a tree, where the node decides which child to visit.
  • Integer semantics. For / on integers, languages disagree on negative values. Python’s -7 // 2 is -4 (floor). C#’s -7 / 2 is -3 (truncation toward zero). In JavaScript, -7 / 2 is -3.5, so you pick Math.trunc or Math.floor yourself. Read the spec, then test a negative case.

Pitfalls

Section titled “Pitfalls”
  • Pop order. The right operand is popped first. Swapping them only shows up on -, /, ^, so test those.
  • The tie rule. Pop on equal precedence for left-associative operators, not for right-associative ones. 8 - 3 - 2 = 3 and 2 ^ 3 ^ 2 = 512 are the two tests that catch both mistakes.
  • Unary vs binary minus. 3 - -2, -(4), 2 * -3 and --4 all need the “operand expected here” check.
  • Unbalanced parentheses. A ) with no ( on the stack, or a ( left at the end, is an error. So is an empty ().
  • Two numbers or two operators in a row (1 2 +, 1 + * 2) when the input is infix. Track whether you expect an operand or an operator.
  • Division by zero and overflow. Decide whether to throw, return an error value, or (with floats) allow Infinity.
  • eval(). Python’s eval, JavaScript’s eval/Function and similar run arbitrary code. Never use them on user input, and in an interview they skip the point of the question.

In the interview

Section titled “In the interview”
  • Clarify the grammar: which operators, which precedence, which associativity, unary minus, parentheses, whitespace, number formats (decimals? leading zeros?), variables.
  • Clarify semantics: integer or float, division rounding, overflow, division by zero, what a malformed expression returns.
  • Name the approach before coding: “I’ll tokenize, then use a precedence-climbing parser to a tree” or “shunting-yard to postfix, then a value stack”. Mention the other one and why you didn’t pick it.
  • Test the tie cases out loud: 1 - 2 - 3, 2 ^ 3 ^ 2, 2 * (3 + 4), a lone number, deep nesting.
  • Expect follow-ups that reward a tree: add variables, add functions, evaluate many times, print the expression back, add new operators without rewriting the parser.

Check yourself

Section titled “Check yourself”
Check yourself
pick one
In shunting-yard, you pop an operator from the stack only when it binds strictly tighter than the incoming one (never on ties). What does 8 - 3 - 2 evaluate to?
Check yourself
pick one
Evaluating the postfix list 20 5 / with a value stack, you pop a, then b, and push a / b. What do you get?
Check yourself
pick one
A filter expression is evaluated against a million rows, each with different variable values. What should you build?

Practice on your own

Section titled “Practice on your own”

Classic exercises, not gym questions:

  • Evaluate a postfix (RPN) expression given as a list of tokens, with integer division that truncates toward zero.
  • Convert infix to prefix (Polish) notation, and evaluate prefix with a stack, scanning from the right.
  • Evaluate a boolean expression with !, &, | and parentheses, such as !(t & f) | f.
  • Print an expression tree with the minimum number of parentheses (extend the sample above with unary minus).
  • Symbolic differentiation: given a tree over x, +, * and ^ with integer exponents, build the derivative’s tree and simplify 0 * e and 1 * e.

Go deeper

Section titled “Go deeper”
Section titled “Related”
Parsing and tokenizingThe tokenizer and recursive descent this page builds on.
StacksThe operator stack and the value stack.
Binary treesPost-order traversal is tree evaluation.
RecursionGrammar rules that call each other.