Reverse Polish Notation

Mathematical expressions can be written in three equivalent forms:

Notation	Form	Example	Meaning
Infix	operator between operands	3 + 4	the familiar form
Prefix (Polish)	operator before operands	+ 3 4	operator first
Postfix (RPN)	operator after operands	3 4 +	operator last

Reverse Polish Notation (RPN) — also called postfix notation — places operators after their operands.

More complex examples:

Infix	RPN
3 + 4	3 4 +
5 - 3	5 3 -
3 + 4 * 2	3 4 2 * +
(3 + 4) * 2	3 4 + 2 *

Notice that RPN requires no brackets — the order of operations is unambiguous from the position of operators. This is why compilers and calculators use it internally.

RPN expressions are evaluated using a stack:

1. Read the expression left to right
2. If the token is an operand (number): push it onto the stack
3. If the token is an operator (+, -, *, /): pop two operands, apply the operator, push the result
4. When the expression ends, the single remaining stack value is the result

Worked example — evaluate 3 4 2 * +:

Token	Action	Stack
3	Push	[3]
4	Push	[3, 4]
2	Push	[3, 4, 2]
*	Pop 2 and 4; compute 4 × 2 = 8; push 8	[3, 8]
+	Pop 8 and 3; compute 3 + 8 = 11; push 11	[11]

Result: 11 (matches infix 3 + 4 * 2 = 3 + 8 = 11).

Note the pop order: the first pop gives the right operand, the second pop gives the left operand. For - and / this matters: 5 3 - means 5 − 3 = 2, not 3 − 5.

Evaluate 6 2 / 3 4 * +:

Token	Action	Stack
6	Push	[6]
2	Push	[6, 2]
/	Pop 2 and 6; compute 6 ÷ 2 = 3; push 3	[3]
3	Push	[3, 3]
4	Push	[3, 3, 4]
*	Pop 4 and 3; compute 3 × 4 = 12; push 12	[3, 12]
+	Pop 12 and 3; compute 3 + 12 = 15; push 15	[15]

Result: 15 (matches infix 6 / 2 + 3 * 4 = 3 + 12 = 15).

The pseudocode for an RPN evaluator:

FUNCTION evalRPN(tokens)
    stack ← empty stack
    FOR each token IN tokens
        IF token is a number THEN
            stack.push(token)
        ELSE
            right ← stack.pop()
            left  ← stack.pop()
            IF token = "+" THEN stack.push(left + right)
            ELSE IF token = "-" THEN stack.push(left - right)
            ELSE IF token = "*" THEN stack.push(left * right)
            ELSE IF token = "/" THEN stack.push(left / right)
            ENDIF
        ENDIF
    NEXT
    RETURN stack.pop()
ENDFUNCTION

One way to convert infix to RPN is to build a binary expression tree then do a post-order traversal (left, right, node).

Example — convert 3 + 4 * 2 to RPN:

Build the expression tree (respecting operator precedence; * binds tighter than +):

Post-order traversal (left → right → node):

1. Visit left of +: output 3
2. Visit right of + (the * subtree):
   • Visit left of *: output 4
   • Visit right of *: output 2
   • Visit node *: output *
3. Visit node +: output +

Result: 3 4 2 * + ✓

For (3 + 4) * 2, the tree changes because + is now the lower node:

Post-order: 3 4 + 2 * — the brackets are encoded in the tree structure, not in the RPN.

The Shunting-Yard algorithm (Dijkstra, 1961) converts infix to RPN directly using a stack and an output queue, without building a full expression tree.

AQA requires awareness of the algorithm — you need to know it exists and what it does, not implement it step by step.

Key rules (simplified):

• Numbers go directly to output
• Operators are pushed onto a stack, popped to output when a lower-precedence operator arrives or when ) is reached
• Brackets control the order: ( is pushed; ) triggers popping until ( is found

This is used internally in compilers to generate code for arithmetic expressions — the compiler converts infix source code to RPN (or equivalent bytecode) for efficient stack-based evaluation.

RPN is not just an academic curiosity — it is used in real systems:

• Compilers: convert infix arithmetic to stack-based bytecode (e.g. Java's JVM uses a stack-based instruction set)
• Calculators: Hewlett-Packard's RPN calculators (HP-12C still in use by financial professionals)
• PostScript: the page-description language (used by printers) is an RPN-based stack language

The connection to computer science concepts:

• Evaluation uses a stack (see stacks and queues)
• Conversion uses tree traversal (post-order on a binary expression tree)
• Operator precedence is implicit in tree structure, not in bracket syntax

1. Wrong pop order for subtraction and division

When evaluating - or /, the first pop gives the right operand and the second pop gives the left operand. 5 3 - means 5 − 3 = 2, not 3 − 5 = −2. Getting this backwards loses the mark.

2. Leaving multiple values on the stack

A valid RPN expression always evaluates to exactly one remaining value. If your trace ends with more than one value on the stack, the expression is malformed or you missed an operator.

3. Forgetting that brackets disappear in RPN

RPN contains no brackets. Operator precedence and grouping are encoded in the order of operands and operators. (3 + 4) * 2 becomes 3 4 + 2 *, not 3 + 4 * 2.

4. Confusing pre-order and post-order traversal

Converting infix to RPN requires post-order (left, right, node). Pre-order (node, left, right) gives prefix/Polish notation. Using the wrong traversal produces the wrong output.