Reverse Polish (Postfix) Notation

AQA 4.3.3 — Reverse Polish Notation

Retrieval: the previous two lessons used an explicit stack to control traversal order. This lesson applies the exact same stack mechanism to a different problem entirely: evaluating a mathematical expression.

Key vocabulary

• Infix notation — the everyday form, where an operator sits between its operands (3 + 4).
• Postfix (Reverse Polish) notation — operators come after their operands (3 4 +).
• Operand — a value an operator acts on.

Understand — why postfix removes ambiguity entirely

Infix notation needs precedence rules (* before +) and brackets to stay unambiguous — 3 + 4 * 2 only means "add 4×2 to 3" because of a rule learned separately from the symbols themselves. Postfix needs neither: 3 4 2 * + places each operator exactly where it should be applied, with no external rule required to interpret it correctly.

See it — converting infix to postfix

3 + 4 * 2 (infix) becomes 3 4 2 * + (postfix) — the multiplication, which must happen first, has its operator placed immediately after its own two operands (4 and 2); addition, happening last, has its operator placed last, after its own two operands (3 and the result of 4 2 *).

See it — evaluating postfix with a stack

def evaluate_postfix(tokens):
    stack = []
    for token in tokens:
        if token in ("+", "-", "*"):
            b = stack.pop()
            a = stack.pop()
            if token == "+":
                stack.append(a + b)
            elif token == "-":
                stack.append(a - b)
            elif token == "*":
                stack.append(a * b)
        else:
            stack.append(int(token))
    return stack.pop()

Trace it — evaluating 5 1 2 + 4 * +

Result: 17.

Reason about correctness — why the stack-based algorithm always works

Postfix notation is defined so that, reading left to right, every operator is only ever encountered after both of its operands have already appeared. This guarantees that the moment an operator is reached, its two operands are already sitting on top of the stack — pushed there by the tokens just processed, with nothing else in between belonging to a different part of the expression. Because each operation replaces its two operands with a single result (also pushed onto the stack), the stack's top always represents "the fully-evaluated value of everything processed so far that hasn't yet been consumed by a later operator" — which is exactly why the single value left on the stack at the very end is the whole expression's correct result.

Debug it — diagnose, explain, fix, test, justify (incorrect stack behaviour)

def evaluate_postfix(tokens):
    stack = []
    for token in tokens:
        if token in ("+", "-", "*"):
            a = stack.pop()
            b = stack.pop()
            if token == "+":
                stack.append(a + b)
            elif token == "-":
                stack.append(a - b)
            elif token == "*":
                stack.append(a * b)
        else:
            stack.append(int(token))
    return stack.pop()

print(evaluate_postfix("3 4 -".split()))

This runs without error and prints 1 — but the mathematically correct result of 3 4 - (meaning 3 - 4) is -1.

1. Diagnose: for a non-commutative operator like -, does it matter which of the two popped values is treated as a and which as b?
2. Explain: in postfix, which operand was pushed first — the one that should come first in the operation, or second?
3. Fix: correct the order the two popped values are assigned to a and b.
4. Test: confirm evaluate_postfix("3 4 -".split()) now correctly returns -1.
5. Justify: explain why this bug would go completely unnoticed for commutative operators like + and *, but silently produces wrong answers for - and /.

(The first value popped is the SECOND operand pushed (LIFO), so it must be assigned to b, and the second value popped is the FIRST operand (a) - the working version's a = stack.pop() then b = stack.pop() gets this right; this broken version swaps them. This is invisible for + and * because a+b == b+a and ab == ba regardless of order - the bug only produces a visibly wrong, silently plausible answer for non-commutative operations.)

Common mistake

Assuming operator precedence still applies to postfix the way it does to infix. Postfix has no precedence rules at all - the position of each operator in the token sequence is the entire instruction for when it applies, which is precisely why it needs no brackets and no precedence table.

Analyse — complexity

Evaluating a postfix expression of n tokens takes O(n) — each token is processed exactly once, with a constant amount of stack work (at most one push and up to two pops) per token.

Check your understanding

Evaluate the postfix expression 8 3 2 - 4 * + by hand, showing the stack's contents after each step. (3 marks)

(8: [8]. 3: [8,3]. 2: [8,3,2]. -: pop 2, pop 3, push 3-2=1 -> [8,1]. 4: [8,1,4]. : pop 4, pop 1, push 14=4 -> [8,4]. +: pop 4, pop 8, push 8+4=12 -> [12]. Result: 12.)

Challenge

Convert the infix expression (6 + 2) * 3 - 4 into postfix notation, then evaluate your postfix version by hand and confirm it matches the infix expression's own value.

Looking ahead: the next lesson steps back from implementation to compare and select between every searching strategy covered so far — Linear Search, Binary Search, and Sequence 12's Binary Search Tree search.