Welcome to the World of Reverse Polish Notation!

Hi there! Today we are going to look at a topic that sounds a bit intimidating but is actually a very clever "shortcut" for computers. We are learning about Reverse Polish Notation (RPN), also known as Postfix Notation.

By the end of these notes, you’ll understand why computers prefer this over the math we learn in school, and you'll be able to convert expressions back and forth like a pro. Don't worry if it seems a bit "backwards" at first—that's exactly the point!

1. What is Reverse Polish Notation?

In our everyday lives, we use Infix Notation. This means the operator (like +, -, or *) goes in between the numbers.
Example: \( 3 + 4 \)

In Reverse Polish Notation (RPN), the operator goes after the numbers.
Example: \( 3 \ 4 \ + \)

Why do we use it?

Computers love RPN for three main reasons:

  • No Brackets Needed: In RPN, the order of the numbers and operators tells the computer exactly what to do. There is never a need for parentheses!
  • Standard Order: It removes any confusion about BIDMAS/BODMAS. The order of operations is built right into the string.
  • Stack-Friendly: It is incredibly easy for a computer to evaluate using a Stack data structure (which we will look at in a moment).

Quick Review:
Infix: Operator is in the middle (\( A + B \)).
Postfix (RPN): Operator is at the end (\( A \ B \ + \)).

2. How to Convert: Infix to RPN

Converting might seem tricky, but there is a simple "Bracket Trick" you can use to get it right every time.

The "Bracket and Move" Method

  1. Take your Infix expression: \( (3 + 4) * 5 \)
  2. Ensure it is fully bracketed according to BIDMAS: \( ((3 + 4) * 5) \)
  3. Move each operator to the right, just inside its closing bracket: \( ((3 \ 4 + ) \ 5 * ) \)
  4. Remove all the brackets: \( 3 \ 4 \ + \ 5 \ * \)

Analogy: Imagine a chef. In Infix, the recipe says "Add the flour and sugar, then bake." In RPN, the chef gets the ingredients first: "Flour, Sugar, Add, Bake." The action (operator) always comes after the items (operands).

3. How to Convert: RPN to Infix

If you see an RPN expression and need to turn it back into "human-readable" math, follow these steps:

  1. Read the expression from left to right.
  2. When you see an operator, apply it to the two numbers immediately to its left.
  3. Put brackets around this new "package" and treat it as one number.

Example: \( 5 \ 3 \ 2 \ * \ + \)
1. We see \( 3 \ 2 \ * \). Turn that into \( (3 * 2) \).
2. Now we have \( 5 \ (3 * 2) \ + \).
3. The \( + \) applies to the \( 5 \) and the \( (3 * 2) \).
4. Final Infix: \( 5 + (3 * 2) \)

Key Takeaway: When converting to RPN, move operators to the right. When converting back, move them to the middle of the two numbers directly to their left.

4. Evaluating RPN Using a Stack

This is a favorite topic for exam questions! A computer uses a Stack (a Last-In, First-Out data structure) to solve RPN expressions.

Step-by-Step Evaluation

Let's evaluate: \( 6 \ 2 \ / \ 3 \ + \)

  • Scan the first item (\( 6 \)): It’s a number, so Push it onto the stack. [Stack: 6]
  • Scan the next item (\( 2 \)): It’s a number, so Push it. [Stack: 6, 2]
  • Scan the next item (\( / \)): It’s an operator!
    • Pop the top number (\( 2 \)). This is your second operand.
    • Pop the next number (\( 6 \)). This is your first operand.
    • Calculate \( 6 / 2 = 3 \).
    • Push the result (\( 3 \)) back onto the stack. [Stack: 3]
  • Scan the next item (\( 3 \)): It’s a number, so Push it. [Stack: 3, 3]
  • Scan the next item (\( + \)): It’s an operator!
    • Pop (\( 3 \)), Pop (\( 3 \)).
    • Calculate \( 3 + 3 = 6 \).
    • Push the result (\( 6 \)) back onto the stack. [Stack: 6]

The final number remaining on the stack is your answer!

Common Mistake Alert!
When subtracting or dividing, the first number you pop is the one on the right of the minus/divide sign.
Example: If the stack is [10, 2] and you see \( - \), the calculation is \( 10 - 2 \), not \( 2 - 10 \)!

5. Real-World Applications

You might be wondering, "Do people actually use this?" Yes! RPN is used in places where speed and simplicity are vital:

  • Interpreters: Many programming language interpreters (like those for Postscript or Java Bytecode) use stacks and RPN because it's faster for the computer to process than complex Infix strings.
  • Calculators: Early Hewlett-Packard (HP) calculators used RPN. Some engineers still prefer them today because they can perform long calculations without ever needing to use brackets!

Did you know? Postscript is a language used by printers. When you print a PDF, your computer is often sending a long string of RPN-style commands to the printer!

Summary: Quick Review Box

Definition: RPN (Postfix) places the operator after the operands (\( 3 \ 4 \ + \)).
Advantage 1: No brackets/parentheses needed.
Advantage 2: No ambiguity with order of operations (BIDMAS).
Mechanism: Evaluated using a Stack (Push numbers, Pop for operators).
Uses: Stack-based interpreters, Postscript, and computer bytecode.