Skip to topic
    ← Back to course topics

    Reverse Polish – infix transformations — AQA A-Level Computer Science

    Reverse Polish Notation (RPN), or postfix notation, places operators after their operands, completely eliminating the need for brackets and operator precedence rules during computer execution. Transforming between infix and RPN is a fundamental AQA A-Level Computer Science skill evaluated using stack-based algorithms and expression trees.

    Reverse Polish – infix transformations explained

    Reverse Polish notation (RPN) places each operator after its operands, so evaluation order is fixed by position and brackets are unnecessary for sub-expressions.

    Read the full explanation

    Crucially, RPN order reflects actual evaluation order, including any precedence or parentheses from the infix form, not simply the precedence hierarchy. Example: (3 + 4) × 5 becomes 3 4 + 5 ×, where the lower-precedence + appears first because the brackets force it to be evaluated first. Compare 3 + 4 × 5, which becomes 3 4 5 × +, where multiplication is evaluated before addition without brackets. A stack evaluates each RPN expression left to right: push operands, and on an operator pop two values, apply the operator and push the result.

    Your focus

    1. Eliminates need for brackets in sub- expressions.

    Which command word is this?

    Translate the given expression directly from one notation to another. Working out is recommended to safeguard against transcription errors.

    Reverse Polish – infix transformations exam tips

    Topic Overview

    Infix notation places operators between operands (such as A + B), mirroring human arithmetic conventions. However, infix syntax relies heavily on operator precedence hierarchies (BIDMAS) and parentheses, making it inefficient and computationally complex for computer processors and compilers to parse directly.

    Reverse Polish Notation (RPN) solves this by placing operators immediately after their corresponding operands (such as A B +). RPN is unambiguous, inherently requires zero parentheses, and can be evaluated sequentially in a single pass using a standard Last-In, First-Out (LIFO) stack data structure, making it vital in compiler design and virtual machine architectures.

    Key Concepts
    • →Operator Precedence Elimination: RPN avoids ambiguity without requiring brackets or precedence conventions because operator order explicitly dictates execution order.
    • →Stack-Based Evaluation: Operands are pushed to a LIFO stack; encountered operators pop the required number of operands, execute the calculation, and push the result back.
    • →Non-Commutative Operations: When evaluating '-' or '/', the first value popped is the divisor/subtrahend (right operand), and the second value popped is the dividend/minuend (left operand).
    • →Binary Tree Traversal: An expression tree traversed using post-order traversal (Left, Right, Root) yields RPN; traversing in-order (Left, Root, Right) yields standard infix.
    Marking Points
    • Explains that RPN places operators after their operands so evaluation order is fixed by position, not brackets
    • Gives a worked example converting an infix expression with brackets, e.g. (3 + 4) × 5 to 3 4 + 5 ×, with no brackets
    • States that RPN order reflects actual evaluation order, including parentheses overriding precedence, not simply operator precedence
    • Evaluates an RPN expression with a stack: push operands, pop two on an operator, apply and push the result
    • Recognises that the RPN form contains no brackets even when the infix form required them
    Examiner Tips
    • 💡Check that each candidate option keeps operators after their operands and contains no brackets
    • 💡Convert infix to RPN by applying precedence and parentheses first, then write the result in postfix order without brackets
    • 💡Evaluate a candidate RPN expression with a stack to confirm it matches the original infix result
    • 💡In conversion questions, show bracketed stages or draw an expression tree to secure partial method marks even if a clerical slip occurs.
    • 💡When drawing stack states, clearly label which end represents the top of the stack and show each push/pop step individually.
    • 💡Remember that unary operators (like negative signs) operate on only one operand, whereas standard binary operators (+, -, *, /) always pop exactly two.
    Common Mistakes
    • Claims a higher-precedence operator always appears earlier in RPN; (3+4)×5 gives 3 4 + 5 ×, so a bracketed lower-precedence + appears first
    • Places the operator before its operands, which is prefix notation, not RPN
    • Believes brackets are removed by ignoring precedence; precedence and parentheses still govern the conversion and are reflected in the RPN ordering
    • Reversing Operand Order: Students frequently assume operands also change their relative order. Operands always retain their exact left-to-right sequence; only operator positions change.
    • Stack Pop Direction: During division or subtraction evaluation, students often divide the first popped value by the second, reversing dividend and divisor and yielding incorrect answers.
    • Assuming RPN Requires Precedence Rules: Students often try to apply BIDMAS during RPN evaluation; RPN expressions are read purely linearly from left to right.
    Revision Plan
    1. 1Day 1: Master the definitions of infix, postfix (RPN), and prefix notation, focusing on why computers prefer postfix for parsing.
    2. 2Day 2: Practice manual conversion of mathematical expressions from infix to RPN using full parenthesisation and expression trees.
    3. 3Day 3: Practice stack-trace evaluation tables for RPN expressions containing arithmetic and boolean logic operators.
    4. 4Day 4: Implement or trace Dijkstra's Shunting-yard algorithm to understand programmatic conversion between infix and RPN.
    5. 5Day 5: Complete timed past-paper exam questions covering RPN transformations and stack evaluations under AQA conditions.
    Exam Question Types
    • 📋Direct Conversion: Transforming an infix expression with mixed operator precedence into RPN or vice-versa (2-4 marks).
    • 📋Stack Trace Evaluation: Tabulating the state of a stack step-by-step as an RPN string is evaluated (3-5 marks).
    • 📋Tree Traversal Links: Constructing an expression tree from an infix statement and stating the traversal method required to produce postfix (3-4 marks).
    • 📋Conceptual / Advantages: Explaining why RPN is used in interpreters, compilers, and stack architectures over infix (2-3 marks).
    Command Word Expectations (AQA)
    Convert

    Translate the given expression directly from one notation to another. Working out is recommended to safeguard against transcription errors.

    Show

    Provide an explicit step-by-step trace (e.g., table of stack states or intermediate parenthesised expressions) rather than solely the final answer.

    Explain

    Give clear technical reasons why RPN is advantageous for machine evaluation, citing stacks, bracket elimination, or linear parsing.

    How Students Lose Marks (Examiner Pitfalls)
    Pitfall: Failing to maintain operand order during non-commutative operations like division or subtraction.
    ❌ Weak Answer (Loses Marks):Converting 'a - b' to 'b a -' or evaluating '10 2 /' as 2 divided by 10 (0.2).
    Example improved answer:For non-commutative operations in RPN, the first operand popped from the stack is the right-hand operand, and the second is the left-hand operand. Therefore, 'a - b' translates strictly to 'a b -', and evaluating '10 2 /' yields 10 / 2 = 5.
    Examiner Tip: Always write down the stack trace step-by-step for evaluation questions; label popped items clearly as operand2 (top) and operand1 (second).
    Pitfall: Incorrectly handling operator precedence when converting complex infix expressions with multiple operators of varying precedence.
    ❌ Weak Answer (Loses Marks):Converting '3 + 4 * 2' directly from left to right as '3 4 + 2 *'.
    Example improved answer:Multiplication takes precedence over addition. In expression tree terms, '4 * 2' forms a subtree evaluated first, resulting in the postfix expression '3 4 2 * +'.
    Examiner Tip: Fully parenthesise the infix expression manually before converting if doing it by inspection: write '(3 + (4 * 2))' to avoid misplacing operators.
    Step-by-Step Worked Solutions

    Question: Convert the infix expression '(A + B) * (C - D) / E' into Reverse Polish Notation (RPN). Show full intermediate working.

    1. 1.Step 1: Identify sub-expressions based on operator precedence and brackets. The sub-expressions are '(A + B)' and '(C - D)'.
    2. 2.Step 2: Convert the bracketed terms to postfix: '(A + B)' becomes 'A B +' and '(C - D)' becomes 'C D -'.
    3. 3.Step 3: Evaluate multiplication and division left-to-right. Combine the first two terms with '*': '(A B +) (C D -) *'.
    4. 4.Step 4: Append the remaining division operand and operator: '(A B + C D - *) E /'.
    Final Answer: A B + C D - * E /

    Question: Show the state of the stack at each step when evaluating the following RPN expression: '12 4 / 3 2 * +'. State the final evaluated result.

    1. 1.Step 1: Push '12' to the stack. Stack: [12].
    2. 2.Step 2: Push '4' to the stack. Stack: [12, 4].
    3. 3.Step 3: Read operator '/'. Pop '4' (operand 2) and '12' (operand 1). Calculate 12 / 4 = 3. Push '3'. Stack: [3].
    4. 4.Step 4: Push '3' to the stack. Stack: [3, 3].
    5. 5.Step 5: Push '2' to the stack. Stack: [3, 3, 2].
    6. 6.Step 6: Read operator '*'. Pop '2' and '3'. Calculate 3 * 2 = 6. Push '6'. Stack: [3, 6].
    7. 7.Step 7: Read operator '+'. Pop '6' and '3'. Calculate 3 + 6 = 9. Push '9'. Stack: [9].
    Final Answer: Final result = 9. Final stack contains a single item: [9].
    Active Recall Memory Test
    What tree traversal method converts an expression tree into Reverse Polish Notation?
    Key Fact: Post-order traversal (Left, Right, Root).
    Why does RPN eliminate the need for brackets and operator precedence?
    Key Fact: Because the explicit positioning of operators immediately after their operands unambiguously defines execution order.
    When evaluating '8 2 -' using a stack, what calculation is performed upon encountering '-'?
    Key Fact: The top item (2) is popped as operand 2, the next (8) as operand 1, calculating 8 - 2 = 6.
    Which abstract data type is fundamentally used to evaluate RPN expressions?
    Key Fact: A LIFO stack.
    Frequently Asked Questions
    Why do computers use Reverse Polish Notation instead of normal infix?
    Infix expressions are complex for compilers to evaluate because they require lookaheads, backtracking, and memory overhead to handle brackets and precedence rules. RPN can be processed in a single sequential pass from left to right using a simple LIFO stack, saving CPU cycles and memory.
    Does the order of variables change when converting infix to RPN?
    No. The relative order of the operands (numbers or variable names) remains identical in both infix and RPN representations. Only the positions of the operators change relative to their operands.
    How do you handle comparison operators or boolean logic in RPN?
    Boolean and comparison operators (such as AND, OR, NOT, >, <) follow the exact same stack mechanics as arithmetic operators. Binary operators like AND or '>' pop two operands and push a boolean result (True/False or 1/0), while NOT pops a single operand.
    What is the difference between prefix, infix, and postfix notation?
    Infix places operators between operands (A + B). Postfix (Reverse Polish) places operators after their operands (A B +). Prefix (Polish notation) places operators before their operands (+ A B). Postfix and prefix both remove the need for brackets.
    What algorithm is used by compilers to convert infix expressions to RPN?
    Dijkstra's Shunting-yard algorithm is the standard method used to convert infix to RPN. It uses an operator stack and an output queue to reorder operators and operands according to their precedence and associativity.