AQA 7517 · Paper 1 · 4.3.3

Reverse Polish
Notation (RPN)

Postfix notation · Stack evaluation · Section 4.3 Algorithms

WHAT YOU'LL LEARN

Infix vs postfix · Converting to RPN · Stack evaluation · Benefits of RPN

AQA SPEC LINK

4.3.3 — Reverse Polish notation

Notation Types

Infix, Prefix & Postfix

INFIX (standard maths — what we normally write)

(3 + 4) × 2

Operator between operands. Needs brackets for precedence.

PREFIX (Polish Notation)

× + 3 4 2

POSTFIX (Reverse Polish Notation — used by computers)

3 4 + 2 ×

Why RPN?

Why Computers Use RPN

No brackets needed — precedence is built into the operand order

Evaluatable by a stack — simple linear pass through the expression

Efficient for compilers — code generators produce RPN intermediately

HP calculators used RPN historically (Hewlett-Packard reverse Polish calculators)

Stack Evaluation

Evaluating RPN with a Stack

Rule: Read left to right. If operand → push to stack. If operator → pop two values, apply operator, push result.

EXAMPLE: evaluate 3 4 + 2 ×

Token	Action	Stack
3	Push 3	[3]
4	Push 4	[3, 4]
+	Pop 4,3 → 3+4=7 → push	[7]
2	Push 2	[7, 2]
×	Pop 2,7 → 7×2=14 → push	[14]

Final result: 14 ✓ (same as (3+4)×2)

More Examples

RPN Stack Evaluation Examples

INFIX: 5 + 3 × 2 = 11 (× first due to precedence)

RPN: 5 3 2 × +

INFIX: (5 + 3) × 2 = 16 (brackets first)

RPN: 5 3 + 2 ×

INFIX: 8 − 3 + 2 = 7

RPN: 8 3 − 2 +

Infix to RPN

Converting Infix to RPN

The shunting-yard algorithm (Dijkstra) converts infix to RPN using a stack for operators:

If operand (number/variable) → output immediately

If operator → pop and output operators with higher/equal precedence, then push this one

If ( → push; if ) → pop until matching (

At end: pop and output remaining operators

Shunting Yard

Shunting Yard Example

Convert: 3 + 4 × 2 to RPN. Precedence: × before +

Token	Output	Op Stack
3	3	[]
+	3	[+]
4	3 4	[+]
×	3 4	[+, ×]
2	3 4 2	[+, ×]
end	3 4 2 × +	[]

Link to Trees

RPN and Expression Trees

An arithmetic expression can be stored as a binary tree. Post-order traversal of that tree gives the RPN form. Pre-order gives prefix. In-order gives infix (with brackets).

×
 /  \
+   2
/ \
3  4

Post-order → 3 4 + 2 × = RPN

AQA Exam Style

Practice Question

AQA 7517 — Paper 1 Style

(a) Convert the following infix expression to Reverse Polish Notation: (6 + 2) × (5 − 3) [2]
(b) Using a stack, evaluate the RPN expression: 7 2 3 × − [3]

[5 marks]

2 marks

(a) 6 2 + 5 3 − ×

3 marks

(b) Push 7 [7] → Push 2 [7,2] → Push 3 [7,2,3] → ×: pop 3,2 → 6, push [7,6] → −: pop 6,7 → 7−6=1, push [1] → Result: 1

Summary

Key Points to Remember

Infix: (3 + 4) × 2 · RPN (postfix): 3 4 + 2 ×

Evaluation rule: operand → push; operator → pop two, apply, push result

RPN needs no brackets — precedence built into order

Shunting-yard algorithm converts infix to RPN

Post-order traversal of expression tree = RPN

🎉 Lesson complete — move to the quiz!