Reverse Polish Notation Revision Notes for AQA A-Level Computer Science

Reverse Polish Notation

Introduction to notation types

When we write mathematical expressions in everyday life, we typically use what's called infix notation. This is where the operator (like +, -, ×, ÷) appears between the numbers it operates on. For example, we write $5 + 3$ or $7 \times 2$ .

However, this isn't the only way to represent mathematical expressions. There are three main types of notation you need to understand:

Infix notation - the operator sits between the operands (e.g., $5 + 3$ )
Prefix notation - the operator comes before the operands (e.g., $+ 5 3$ )
Postfix notation - the operator comes after the operands (e.g., $5 3 +$ )

Reverse Polish Notation (RPN) is another name for postfix notation. It provides a way of writing mathematical expressions where the operators are placed after the values they work with. While this might seem unusual at first, RPN offers several important advantages, particularly for computer systems.

infoNote

The main benefit of RPN is that it removes the need for brackets in expressions and creates a sequence that interpreters can evaluate more easily. This makes it particularly valuable in computing contexts where efficient processing of mathematical expressions is essential.

Understanding infix notation and BODMAS

Before we explore RPN further, let's make sure we understand how standard infix expressions work. When we see an expression like $5 + 3$ , we know we need to add 3 to 5 to get the result. The operator (+) sits between the two operands (5 and 3), which is why it's called infix notation.

Things become more complex when expressions contain multiple operators. Consider the expression $3 \times 2 + 5$ . Should we perform the multiplication first or the addition? This is where BODMAS comes in - a methodology that tells us the order in which to evaluate parts of an expression.

BODMAS stands for:

Brackets
Orders (powers and square roots)
Division and Multiplication (equal priority, work left to right)
Addition and Subtraction (equal priority, work left to right)

lightbulbExample

Worked Example: Evaluating an Expression Using BODMAS

Let's apply BODMAS to evaluate $3 + (18 \div 3^2 \times 3) - 4$ :

Step 1: Start with the brackets: evaluate $18 \div 3^2 \times 3$

Step 2: Within the brackets, handle the order (power) first: $3^2 = 9$

Step 3: Now we have $18 \div 9 \times 3$

Step 4: Division and multiplication have equal priority, so work left to right: $18 \div 9 = 2$

Step 5: Then multiply: $2 \times 3 = 6$

Step 6: Now we can perform the addition: $3 + 6 = 9$

Step 7: Finally, subtract: $9 - 4 = 5$

Final Answer: $5$

chatImportant

Brackets are particularly important because they override the normal order of operations. The expression $(3 \times 2) + 5$ gives a different result from $3 \times (2 + 5)$ because the brackets tell us which operation to perform first.

Polish notation and Reverse Polish notation

Polish Notation was invented by Polish mathematician Jan Łukasiewicz in 1924, predating modern computers. It was developed as a way to simplify mathematical expressions by eliminating the need for brackets entirely, while still producing unambiguous expressions. This form of notation became known as prefix notation because the operators appear before the operands.

In the 1950s, this concept was adapted and reversed to create Reverse Polish Notation (RPN). In RPN, operators come after the operands rather than before them. This became particularly useful for interpreters because it provides a convenient format for evaluating expressions in programming code.

Here's how the three notations compare:

Prefix (Polish): The operator appears first, followed by the operands. For example, $7 + 3$ becomes $+ 7 3$
Infix: The operator sits between operands. For example, $7 + 3$
Postfix (RPN): The operands come first, then the operator. For example, $7 + 3$ becomes $7 3 +$

Why RPN matters for interpreters

An interpreter is software that translates and executes programs line by line. It converts programming statements into machine code (binary: 0s and 1s) or calls instructions to execute high-level language statements.

When an interpreter processes code, it must parse each line to check that it follows the syntax rules of the programming language. For expressions, the interpreter needs to identify the operands first, then determine which operators to apply to them. This is exactly what RPN provides - the operands come first, making them easy to identify, followed by the operators that show what to do with those operands.

infoNote

This structure makes RPN more efficient for computer processing because:

No brackets are needed
The order of evaluation is clear from left to right
Operands can be identified and stored before operators are encountered
It matches the way stack-based evaluation naturally works

Converting between infix and postfix notation

When converting from infix to postfix notation, the operands stay in the same order - only the position of the operators changes. This is an important rule to remember.

Let's look at some examples:

Infix	Postfix	Result	Explanation
$(6 \times 3) - 1$	$6 3 \times 1 -$	17	Multiply 6 by 3 to get 18 and then minus 1
$(6 \times 2) \div 3$	$6 2 \times 3 \div$	4	Multiply 6 by 2 to get 12 and then divide by 3 to get 4
$(4 \times 3) \div (6 \times 2)$	$4 3 \times 6 2 \times \div$	1	Multiply 4 by 3 to get 12, then multiply 6 by 2 to get 12, divide the two answers to get 1

infoNote

Notice in the third example how brackets group parts of the expression. When converting to RPN:

The first bracketed section $(4 \times 3)$ becomes $4 3 \times$
The second bracketed section $(6 \times 2)$ becomes $6 2 \times$
The division operator that was between the bracketed sections comes last

chatImportant

Converting Bracketed Expressions

When you have brackets in an infix expression, you evaluate the contents of each bracket first. In RPN, you write out the postfix version of each bracketed section, then add the operator that combines them.

lightbulbExample

Worked Example: Converting with Multiple Brackets

For the expression $(5 + 4) \div (4 - 1)$ :

Step 1: First part: $5 + 4$ becomes $5 4 +$

Step 2: Second part: $4 - 1$ becomes $4 1 -$

Step 3: The divide operator combines them: $5 4 + 4 1 - \div$

It's also possible to convert in the opposite direction, from postfix back to infix. For example:

The postfix expression $3 4 +$ becomes the infix expression $3 + 4$
The postfix expression $18 3 \div 2 +$ becomes $(18 \div 3) + 2$

Evaluating RPN expressions using a stack

The most common and efficient method for evaluating postfix expressions is to use a stack data structure. A stack follows a Last In First Out (LIFO) principle, like a stack of plates where you can only add or remove from the top.

lightbulbExample

Worked Example: Stack-Based Evaluation

Let's work through the evaluation of the RPN expression $2 3 \times 5 +$ , which represents the infix expression $(2 \times 3) + 5$ :

Step 1: Read 2 (a number), so push it onto the stack.
Stack: [2]

Step 2: Read 3 (a number), so push it onto the stack.
Stack: [2, 3]

Step 3: Read $\times$ (an operator). This means we need to:

Pop the top two values (3 and 2)
Perform the operation: $2 \times 3 = 6$
Push the result back onto the stack
Stack: [6]

Step 4: Read 5 (a number), so push it onto the stack.
Stack: [6, 5]

Step 5: Read $+$ (an operator). This means we need to:

Pop the top two values (5 and 6)
Perform the operation: $6 + 5 = 11$
Push the result back onto the stack
Stack: [11]

Step 6: We've reached the end of the expression. The final answer (11) is on top of the stack.

chatImportant

Key Rule for Stack-Based Evaluation

When you encounter a number, push it onto the stack; when you encounter an operator, pop the required number of operands, perform the calculation, and push the result back.

Binary trees and expression notation

There's an interesting connection between different notation types and the way we can represent expressions as binary trees. A binary tree is a data structure where each node can have up to two child nodes.

When we represent a mathematical expression as a binary tree:

The operators become the internal nodes
The operands (numbers) become the leaf nodes (nodes with no children)

For the expression $2 \times 3 + 5$ , we can create a binary tree where:

The root node contains the $+$ operator (the final operation)
The left subtree represents $2 \times 3$ (with $\times$ as a node and 2, 3 as leaves)
The right subtree contains just the leaf node 5

infoNote

Tree Traversal and Notation Types

The fascinating connection is that different ways of traversing (visiting the nodes of) this tree produce different notation types:

In-order traversal visits nodes in the pattern: left subtree, root, right subtree. This produces infix notation ( $2 \times 3 + 5$ )
Post-order traversal visits nodes in the pattern: left subtree, right subtree, root. This produces postfix notation ( $2 3 \times 5 +$ )
Pre-order traversal visits nodes in the pattern: root, left subtree, right subtree. This produces prefix notation ( $+ \times 2 3 5$ )

This relationship helps explain why these notation types are useful - they each represent a different way of processing the same underlying expression structure.

Applications of RPN in computing

RPN has several important applications in computer science, particularly in areas where mathematical expressions need to be processed efficiently.

Stack-oriented programming languages

Some programming languages are specifically designed to be stack-oriented, meaning they naturally work with postfix notation. When the interpreter or compiler encounters postfix (RPN) notation in code, it can reference the syntax rules that expect operators to come after operands. This makes stack-oriented languages ideally suited for processing RPN expressions efficiently.

infoNote

One well-known example is PostScript, a language used to create vector graphics. PostScript works by pushing operands onto a stack, and when an operator is encountered, it pops the required operands off the stack, performs the calculation, and pushes the answer back. This elegant approach makes it particularly efficient for graphics operations.

How computers process expressions

RPN is closer to the way computers actually perform calculations. While humans naturally work with infix notation (we expect an operand followed by an operator), processors work differently. They consist of registers and functional units that each perform different tasks.

To calculate an expression, the processor needs to:

Know all the operands first
Store them in appropriate registers
Then apply the operators to perform calculations

This matches the structure of postfix notation, where operands come first, allowing the processor to load them into registers before encountering the operators that tell it what operations to perform.

Different types of programming languages

Programming languages exist at different levels of abstraction:

High-level languages allow programmers to write code similar to natural language, making it easier for humans to understand
Low-level languages are closer to machine code (the binary instructions processors actually execute)

infoNote

Some low-level languages, particularly bytecode formats, use postfix notation because it maps more directly to how processors work. This makes the translation from code to machine instructions more straightforward.

Why interpreters prefer RPN

When code is written in a programming language, interpreters must parse each line to check syntax and convert it into executable instructions. When parsing expressions, the interpreter needs to analyse the operands first, then identify the operators that act upon them.

Infix notation requires the interpreter to look ahead or use complex parsing algorithms to determine the correct order of operations. With RPN, the structure is simpler - operands always come first, and operators that follow tell the interpreter exactly what to do with the most recently encountered operands. This makes RPN a more convenient format for interpreters to process.

bookmarkSummary

Key Points to Remember:

RPN (postfix notation) places operators after operands (e.g., $5 3 +$ instead of $5 + 3$ ), eliminating the need for brackets and creating expressions that are easier for computers to evaluate.
Use a stack to evaluate RPN expressions: push numbers onto the stack as you encounter them, and when you reach an operator, pop the required operands, calculate the result, and push it back onto the stack.
Converting from infix to postfix keeps operands in the same order - only the position of operators changes. Handle bracketed sections first, converting each to postfix before applying operators between them.
Tree traversal methods correspond to notation types: in-order traversal produces infix notation, post-order produces postfix (RPN), and pre-order produces prefix notation.
RPN is valuable in computing because it matches how processors work (needing operands before operators) and makes expression parsing simpler for interpreters and stack-oriented programming languages like PostScript.

Reverse Polish Notation (AQA A-Level Computer Science): Revision Notes