Reverse Polish Notation and Parsing

Reverse Polish Notation (RPN), also called postfix notation, writes an arithmetic expression with each operator placed after its operands — so 3 + 4 becomes 3 4 +. Its great virtue is that it needs no brackets and no precedence rules: the order of the tokens alone fixes the meaning unambiguously. This is not a mathematical curiosity. It is exactly how a computer evaluates expressions internally, because RPN can be evaluated in a single left-to-right pass using nothing more than a stack. RPN therefore ties together three big strands of the course — expression trees, the stack data structure, and the code-generation stage of a compiler.

---

Spec Mapping

This lesson sits within AQA A-Level Computer Science (7517), principally in the fundamentals of algorithms / translation area around section 4.3.3 (with the supporting stack and tree concepts from 4.2.4 and 4.2.7). You are expected to understand Reverse Polish (postfix) notation, to convert between infix and RPN (and to recognise prefix/Polish notation), to evaluate an RPN expression using a stack with a clear stack-state trace, and to explain why RPN needs no brackets or precedence rules. You should also be able to relate RPN to the use of a stack in expression evaluation and to the code-generation stage of compilation. The treatment below is descriptive, not a verbatim quotation of the specification.

---

Three Notations for the Same Expression

Notation	Other name	Operator position	3 + 4 × 2 written as
Infix	—	between operands	3 + 4 × 2
Prefix	Polish notation	before operands	+ 3 × 4 2
Postfix	Reverse Polish (RPN)	after operands	3 4 2 × +

Infix is what we learn at school, but it is awkward for machines because it is ambiguous without extra rules. To read 3 + 4 × 2 correctly you must know two conventions:

• Precedence: × binds more tightly than +, so the answer is 11, not 14.
• Brackets: to override precedence you need parentheses — (3 + 4) × 2 is a different value (14).

Prefix (Polish notation, after the Polish logician Jan Łukasiewicz) and postfix (its reverse) both remove this ambiguity entirely. The position of each operator relative to its operands fixes the order of evaluation, so neither brackets nor a precedence table is ever required. At A-Level the postfix form is the one used for stack evaluation.

---

Why RPN Needs No Brackets or Precedence

The key insight is that in postfix, an operator always acts on the two most recent results to its left. There is no choice to make and nothing to look ahead for, so there is nothing for precedence rules or brackets to disambiguate. Compare the two infix expressions that need brackets to tell them apart:

Infix	RPN	Value
3 + 4 × 2	3 4 2 × +	11
(3 + 4) × 2	3 4 + 2 ×	14

The two RPN forms are simply different orderings of the same tokens — 3 4 2 × + versus 3 4 + 2 × — and that ordering alone encodes which operation happens first. No parentheses appear in either, and yet there is no ambiguity. This is precisely why RPN is so convenient for machines.

---

Converting Infix to RPN

Method 1: via a parse / expression tree

1. Build the expression tree for the infix expression (operators are internal nodes, operands are leaves; the tree's shape already encodes precedence and brackets — see the Context-Free Languages and BNF lesson).
2. Perform a post-order traversal (visit left subtree, then right subtree, then the node).

For 3 + 4 × 2 the tree is:

flowchart TB
    P(("+")) --> N3(("3"))
    P --> M(("×"))
    M --> N4(("4"))
    M --> N2(("2"))

Post-order traversal visits 3, then the × subtree (4, 2, ×), then the root +, giving 3 4 2 × +. (For interest: a pre-order traversal of the same tree — node, left, right — gives the prefix form + 3 × 4 2, and an in-order traversal recovers the original infix. The three notations are just the three traversal orders of one tree.)

Method 2: Dijkstra's shunting-yard algorithm

This converts infix directly to postfix using a stack of operators:

1. Read tokens left to right.
2. A number → output it immediately.
3. An operator → while the operator on top of the stack has equal or greater precedence, pop it to the output; then push the current operator.
4. A ( → push it onto the stack.
5. A ) → pop operators to the output until the matching ( is found; discard both brackets.
6. At the end → pop every remaining operator to the output.

Trace: converting (3 + 4) × 2

Token	Action	Output so far	Operator stack
(	push		(
3	output	3	(
+	push	3	( +
4	output	3 4	( +
)	pop to output until (	3 4 +	(empty)
×	push	3 4 +	×
2	output	3 4 + 2	×
end	pop all	3 4 + 2 ×	(empty)

Result: 3 4 + 2 ×, which evaluates to 14 — the brackets in the infix have been "absorbed" into the ordering, and disappear from the output.

A Fuller Trace: 3 + 4 × 2 − 1 (mixed precedence, no brackets)

The previous trace had brackets but only one of each operator. This one shows the precedence-popping rule (step 3) doing real work. Recall × has higher precedence than + and −, and +/− are equal precedence (left-associative, so we pop on equal precedence):

Token	Action	Output so far	Operator stack
3	output	3	(empty)
+	stack empty, push	3	+
4	output	3 4	+
×	× outranks + on top, so push	3 4	+ ×
2	output	3 4 2	+ ×
−	× ≥ − → pop ×; then + ≥ − → pop +; then push −	3 4 2 × +	−
1	output	3 4 2 × + 1	−
end	pop all	3 4 2 × + 1 −	(empty)

Result: 3 4 2 × + 1 −. The key moment is the − token: because × and the earlier + both have precedence greater-than-or-equal-to −, both are popped to the output before − is pushed. This is exactly how the algorithm enforces "do the × first, then the +, then the −" without any brackets. Evaluating the result confirms it: 3 + (4 × 2) − 1 = 3 + 8 − 1 = 10.

---

Evaluating RPN Using a Stack

This is the heart of the topic and the part most likely to be examined. The evaluation rule is wonderfully short:

1. A number → push it onto the stack.
2. An operator → pop the top two values, apply the operator, and push the single result back.

When the input is exhausted, the one value left on the stack is the answer. Here it is as pseudocode:

FUNCTION evaluateRPN(tokens)
    stack ← new empty Stack
    FOR EACH token IN tokens
        IF token is a number THEN
            stack.push(token)
        ELSE                              # token is an operator
            right ← stack.pop()           # FIRST popped = right operand
            left  ← stack.pop()           # SECOND popped = left operand
            result ← apply(token, left, right)
            stack.push(result)
        ENDIF
    ENDFOR
    RETURN stack.pop()                    # the single remaining value
ENDFUNCTION

The line that catches people out is the operand order: because a stack is last-in, first-out, the first value you pop is the right-hand operand and the second is the left-hand one. This is irrelevant for commutative operators (+, ×) but critical for − and ÷.

Trace: evaluating 3 4 2 × +

Token	Action	Stack (top on right)
3	push	[3]
4	push	[3, 4]
2	push	[3, 4, 2]
×	pop 2 (right) and 4 (left); 4 × 2 = 8; push	[3, 8]
+	pop 8 (right) and 3 (left); 3 + 8 = 11; push	[11]

Result: 11 (matching infix 3 + 4 × 2).

Trace: evaluating 5 1 2 + 4 × + 3 −

Token	Action	Stack (top on right)
5	push	[5]
1	push	[5, 1]
2	push	[5, 1, 2]
+	pop 2, 1; 1 + 2 = 3; push	[5, 3]
4	push	[5, 3, 4]
×	pop 4, 3; 3 × 4 = 12; push	[5, 12]
+	pop 12, 5; 5 + 12 = 17; push	[17]
3	push	[17, 3]
−	pop 3 (right), 17 (left); 17 − 3 = 14; push	[14]

Result: 14. Equivalent infix: 5 + (1 + 2) × 4 − 3 = 14. ✓ Note the final −: had we subtracted in the popped order (3 − 17) we would have got −14, which is wrong — the second value popped is always the left operand.

---

Why RPN Is Used in Computing

Advantage	Explanation
No ambiguity	Token order alone fixes meaning — no brackets, no precedence table
Trivial to evaluate	One stack and a single left-to-right pass; no look-ahead, no backtracking
Maps to the CPU	Stack-based virtual machines (e.g. the JVM) execute postfix-style bytecode directly
Used by compilers	Expression trees are flattened to postfix for intermediate code generation
Used by calculators	Hewlett-Packard scientific calculators used RPN entry for decades
Efficient	Evaluation is linear in the number of tokens, $O(n)$O(n)

---

Prefix (Polish) Notation by Comparison

Prefix notation — operator before operands — is the mirror image of postfix and is occasionally examined alongside it, so it is worth seeing how the three forms relate on one expression. Take (3 + 4) × 2:

Notation	Form	How it is read
Infix	(3 + 4) × 2	operator between operands; brackets needed
Prefix	× + 3 4 2	operator first: "multiply (the sum of 3 and 4) by 2"
Postfix (RPN)	3 4 + 2 ×	operator last

Prefix is evaluated with a stack too, but the input is processed right to left (or equivalently with a recursive rule: read an operator, then evaluate its two following sub-expressions). For × + 3 4 2, scanning right to left: push 2, push 4, push 3; the + pops 3 and 4 giving 7; the × pops 7 and 2 giving 14. The crucial point for exam purposes is that prefix and postfix are reverses in operator position and correspond to pre-order and post-order traversals of the same expression tree, while infix is the in-order traversal. All three encode identical structure; they differ only in where the operator sits relative to its operands. Postfix is the form chosen for machine evaluation because it can be processed in a single natural left-to-right pass.

---

Detecting Malformed Expressions

A subtle but assessable point is what happens when an RPN expression is invalid. The stack-evaluation algorithm doubles as a validity check:

• Too few operands. If an operator is encountered but the stack holds fewer than two values, the expression is malformed. For example 3 + × tries to pop two operands for + when only one number has been pushed — an error.
• Too many operands. If, after processing every token, more than one value remains on the stack, there were not enough operators to combine them. For example 3 4 5 + ends with [3, 9] — two values left, so it is malformed.
• A well-formed expression ends with exactly one value on the stack, which is the result.

This gives a neat rule: an RPN expression over binary operators is valid precisely when, reading left to right, the running count of "numbers pushed minus operands consumed" never goes below the two an operator needs, and finishes at exactly one. Real calculators and compilers use exactly this check to reject ill-formed input, which is why understanding the stack discipline matters beyond merely getting the arithmetic right.

---

Connection to Parsing and Compilers

RPN is not an isolated trick — it is one stage in the pipeline a compiler uses to turn source code into something executable. The stages line up neatly with the other Theory-of-Computation topics: