A-Level · Data Structures

Shunting Yard infix → postfix

Converting 4 × (2 × 4³ + 5) to postfix, one token at a time. Watch when a token is pushed onto the operator stack versus when it's popped into the output queue — the rules that decide are precedence, associativity, and brackets.

Token stream

Operator stack

Top of stack is highlighted. A ( blocks any operator below it from being popped.

Output queue

Reading left to right, this is the postfix expression as it's built.

Ready. Reading 4 × (2 × 4^3 + 5) left to right.
Postfix so far: —
1 step/s
Step 0 / 12

Keyboard: ← → to step  ·  Space to play/pause  ·  R to reset

About this resource · A-Level

How the shunting yard algorithm works

Reverse Polish notation (RPN, or postfix) writes operators after their operands, so 3 + 4 becomes 3 4 +. It needs no brackets and can be evaluated easily with a stack, which is why it's used by interpreters, compilers and some calculators.

Dijkstra's shunting yard algorithm converts ordinary infix expressions into RPN. Operands go straight to the output queue. Operators wait on a stack and are popped to the output according to precedence, associativity and brackets. An opening bracket blocks anything beneath it until the matching closing bracket arrives.

This trace converts 4 × (2 × 4³ + 5) one token at a time. Watch which operators are pushed and when they're popped, and notice how the higher-precedence power operator is handled compared with multiplication and addition.

Exam tips

Specification

Reverse Polish notation, AQA 7517; useful stack practice for all A-Level boards.

Related resources

Browse all free Computer Science resources →

Want one-to-one help with this topic? I'm Damian Biasone, a qualified Computer Science teacher with 20 years' experience, tutoring GCSE and A-Level students online.

AQA A-Level (7517) tuitionOCR A-Level (H446) tuition