The shape of the lesson
By the end of the lesson, learners can
- Why Reverse Polish?: Infix expressions are easy for people but awkward for a translator: it has to look ahead, apply precedence (* and / before + and −) and match brackets.
- Evaluating with a stack: Every RPN expression is evaluated with the same rule.
- Infix to RPN and back: To convert infix to RPN by hand, apply the precedence rules (brackets first, then * and /, then + and −, equal precedence left to right) and write each operation as left operand, right operand, operator, working from the innermost operation outwards.
- 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.
One picture every idea returns to
In infix notation the operator is written between its operands (A + B). In Reverse Polish notation (RPN), also called postfix, the operator is written after its operands (A B +). RPN needs no brackets and no precedence rules: the order of the tokens fixes the order of the operations. It is evaluated left to right using a stack: push each operand; for each operator, pop two values, apply the operator and push the result. Compilers and interpreters convert expressions to RPN because this simple, unambiguous process is easy to turn into machine code.
Forty-five minutes, phase by phase
| Time | Phase | What happens in the room | Grouping |
|---|---|---|---|
| 0 to 5 min | Hook: predict | Open with the question in the title, Operators go last.. We write 3 + 4 with the operator in the middle, and need brackets and precedence rules to make longer expressions unambiguous. Put the figure on the board: it is the one picture every idea in the lesson returns to. | Whole class, then pairs |
| 5 to 13 min | Teach and check: Why Reverse Polish? | Infix expressions are easy for people but awkward for a translator: it has to look ahead, apply precedence (* and / before + and −) and match brackets. | Whole class, then pairs |
| 13 to 21 min | Teach and check: Evaluating with a stack | Every RPN expression is evaluated with the same rule. Project tab 1 of the lab (Push and pop on a stack) and let a student drive it while the class predicts. Model the worked example Show the stack contents on the board, one line at a time. | Pairs |
| 21 to 30 min | Teach and check: Infix to RPN and back | To convert infix to RPN by hand, apply the precedence rules (brackets first, then * and /, then + and −, equal precedence left to right) and write each operation as left operand, right operand, operator, working from the innermost operation outwards. Model the worked example Convert to RPN on the board, one line at a time. Your turn: Convert A * (B + C) / D to RPN. | Rally Coach |
| 30 to 36 min | Check | The four Stage 1 questions from the student lesson, answered on mini whiteboards or by show of fingers. Re-teach the one most get wrong. | Individual, then whole class |
| 36 to 43 min | Plenary | The exam-style questions from Stage 2, one at a time: thirty seconds alone, then a random call. The feedback lines in the key give the examiner's wording. | Individual, random call |
| 43 to 45 min | Exit and homework | Set the worksheet below (6 questions, 16 marks). Learners self-assess against the objectives before they leave. | Individual |
Protect the parts that carry the learning
The sequence carries about fifty minutes of material, so the lab is driven by one student while the class predicts rather than explored freely. Times are a guide.
Protected: the check at 30 minutes. It is the only individual read on whether the key idea landed, and it is not cut.
Cut first if the build overruns: the last check in Infix to RPN and back, never the check or the plenary.
In a 60 minute block: run worksheet questions 1 to 3 in class as a Rally Coach set and model both the hardest worked example and its check live.
Rally Coach
Pairs share one worksheet. One partner solves the first question aloud while the other coaches, checking each line and offering a prompt rather than the answer; they swap roles for the next question.
The full structure, with its variations and the other twelve, is on the cooperative-learning page.
What to head off, and how
| Trap learners fall into | Teaching move that pre-empts it |
|---|---|
| A − B − C means (A − B) − C, so its RPN is A B − C −. | Writing A B C − − calculates A − (B − C), which gives a different answer. |
| With − and /, order matters. | The first value popped is the right-hand operand. For 11 4 − the answer is 11 − 4 = 7, not 4 − 11. |
Reverse Polish notation: worksheet
6 questions, 16 marks. Written in the style of the papers; no past paper question is reproduced.
Explain why compilers convert arithmetic expressions into Reverse Polish notation.
Evaluate the RPN expression 4 2 3 + * 6 2 / −, showing the contents of the stack after each token is processed.
Convert the infix expression A * (B + C) / D into Reverse Polish notation.
Convert (A + B * C) / (D − E) into RPN, then evaluate it when A = 2, B = 3, C = 4, D = 9 and E = 2.
Convert the RPN expression 8 2 5 * + 1 3 2 * + 4 − / into infix and state its value.
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.
Answer key and marking notes
- 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.
- 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.
- B + C is done first: B C +.
- A B C + * D /.
- 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.
- (8 + 2 * 5) / (1 + 3 * 2 − 4).
- Value: 18 / 3 = 6.
- 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.
6 multiple-choice questions on this lesson
From the topic question bank. Assign them in the app for a marked score in your gradebook, or run the topic as a class game.
What is the Reverse Polish form of (A + B) * C − D?
- AA B + C * D −
- BA B C * + D −
- CA B + C D − *
- D+ A B * C − D
What is the value of the RPN expression 6 2 3 + * 4 −?
- A26
- B−26
- C11
- D6
The RPN expression 9 3 1 + 2 * − is evaluated with a stack. What does the stack hold (bottom to top) immediately after the * has been processed?
- A9, 8
- B9, 4, 2
- C8
- D9, 6
Why do compilers convert arithmetic expressions into Reverse Polish notation?
- AIt needs no brackets or precedence rules and can be evaluated left to right in one pass with a stack
- BIt always uses fewer tokens than infix, so the object code is smaller
- CIt stores the operands in reverse order, so they can be popped from a queue
- DIt lets the processor evaluate the multiplications and additions at the same time
Which infix expression is equivalent to the RPN expression A B C − D * +?
- AA + (B − C) * D
- B(A + B − C) * D
- CA + B − C * D
- D(A + (B − C)) * D
Which RPN expression is equivalent to (P + Q) / (R − S) * T, and what is its value when P = 7, Q = 5, R = 6, S = 2 and T = 3?
- AP Q + R S − / T *, value 9
- BP Q + R S − T * /, value 1
- CP Q R S − / T * +, value 10.75
- DP Q + R S − / T *, value 1
Quiz key
The bracket gives A B + first; that result is multiplied by C (A B + C *); finally D is subtracted: A B + C * D −. A B C * + is the form of A + B * C, ignoring the bracket. A B + C D − * computes (A + B) * (C − D), doing the subtraction before the multiplication. + A B * C − D puts operators in front of their operands, which is not RPN.
Push 6, 2, 3; + gives 2 + 3 = 5 (stack 6, 5); * gives 30; push 4; − pops 4 then 30 and pushes 30 − 4 = 26. −26 calculates 4 − 30, taking the operands in the wrong order. 11 reads the tokens as infix from left to right, 6 * 2 + 3 − 4. 6 applies the subtraction inside the bracket, 6 * (2 + 3 − 4).
9: [9]; 3: [9, 3]; 1: [9, 3, 1]; +: [9, 4]; 2: [9, 4, 2]; *: [9, 8]. The final − then gives 1. 9, 4, 2 is the stack just before the *. 8 forgets that 9 is still waiting underneath. 9, 6 multiplies 3 by 2 without first adding the 1.
In RPN the token order alone fixes the order of the operations, so the translator needs no look-ahead, brackets or precedence, and a simple stack-based routine evaluates it in a single pass. RPN does not change the number of operands or operators; it just drops brackets. The operands stay in the same order as in infix and a stack, not a queue, is used. Operations are still carried out one at a time.
Push A, B, C; − gives (B − C); push D; * gives (B − C) * D; + gives A + (B − C) * D. The brackets around B − C are needed, because otherwise * would act on C alone. (A + B − C) * D and (A + (B − C)) * D both multiply the whole sum by D, but in the RPN the * is applied before the +. A + B − C * D multiplies only C by D.
The brackets give P Q + and R S −; then the division, then the multiplication by T: P Q + R S − / T *. Evaluating: 12, then 4, 12 / 4 = 3, 3 * 3 = 9. P Q + R S − T * / divides by (R − S) * T, giving 12 / 12 = 1. P Q R S − / T * + ignores the first bracket and gives 7 + 5 / 4 * 3 = 10.75. The last option has the right RPN but evaluates it as if the * were done before the /.
What to project
The student lesson embeds these tabs. Open them full screen on the projector; every slider has a drag handle on the stage.
Slides for this lesson
A projectable deck for every pack is on the way. Until then, present the student lesson full screen: its sections, figure and lab tabs follow the same order as the plan above.