A2 · Practice questions · Reverse Polish notation

Push, pop, apply.

Six original Cambridge-style questions on Reverse Polish notation, with stack traces and mark-scheme solutions.

Original questions All questions on this page are original work, written in the Cambridge AS & A Level style. They are not from past papers. They test the same concepts and skills the syllabus rewards.

Keep these straight

Operands push, operators pop.

RPN: operator after its two operands; operands stay in the same order as in infix.
Converting: brackets first, then * and /, then + and −; equal precedence left to right.
Evaluating: push operands; on an operator pop right, pop left, push left op right.
Show the stack after every token: that is where the marks are.

Explain

[2 marks]

Explain why compilers convert arithmetic expressions into Reverse Polish notation.

RPN needs no brackets or precedence rules, so the order of operations is unambiguous. ✓
It can be evaluated left to right in one pass using a stack, which is simple to implement in machine code. ✓

Trace

[4 marks]

Evaluate the RPN expression 4 2 3 + * 6 2 / −, showing the contents of the stack after each token is processed.

4: [4]; 2: [4, 2]; 3: [4, 2, 3]. ✓
+: [4, 5]; *: [20]. ✓
6: [20, 6]; 2: [20, 6, 2]; /: [20, 3]. ✓
−: [17]. The result is 17. ✓

Convert

[2 marks]

Convert the infix expression A * (B + C) / D into Reverse Polish notation.

B + C is done first: B C +. ✓
A B C + * D /. ✓

Convert

[3 marks]

Convert (A + B * C) / (D − E) into RPN, then evaluate it when A = 2, B = 3, C = 4, D = 9 and E = 2.

Inside the first bracket, * before +: A B C * +. Second bracket: D E −. ✓
RPN: A B C * + D E − /. ✓
Evaluation: 3 * 4 = 12, 2 + 12 = 14, 9 − 2 = 7, 14 / 7 = 2. ✓

Convert

[2 marks]

Convert the RPN expression 8 2 5 * + 1 3 2 * + 4 − / into infix and state its value.

(8 + 2 * 5) / (1 + 3 * 2 − 4). ✓
Value: 18 / 3 = 6. ✓

Analysis

[3 marks]

An array of 3 elements is used as the stack to evaluate 8 2 5 * + 1 3 2 * + 4 − /. Explain, with reference to the stack contents, why this array is not large enough.

After 8 2 5 * + the stack holds 18; then 1, 3 and 2 are pushed. ✓
The stack then holds 18, 1, 3, 2: four values at once. ✓
The fourth push would cause a stack overflow, so the array needs at least 4 elements. ✓

Mark this once you have attempted all six and checked your working. It records a Practiced badge on the topic and adds a one-time bonus. Revealing the solutions alone does not count.