Reverse Polish notation
Introduction
Computers need to work out the result of algebraic expressions. The way humans work out expressions is not the way that computers work – they are digital not human!
Infix notation
If we wanted to add to variables together, such as A and B, we could put the + sign between the A and the B like this:
A + B
We would read this as “A plus B” and because the + sign is between the two variables, we call this ' infix ‘notation’.
Prefix notation
We could also add two variables by saying, “Add A and B”. We would write this down as:
+ AB
Because we are putting the sign before the variables, we call this ‘prefix notation’. It is also known as ‘Polish notation’ after the nationality of the person who invented it.
Postfix notation
Finally, we might say, “Take the variable A and the variable B and then add them together”. We would write this down as:
AB +
Because we are putting the sign after the variables, we call this ‘postfix notation’. It’s also got another name, ‘reverse Polish notation', because the operators (the plus sign, the minus sign etc) go after the operands (the numbers). This is the opposite of Polish notation (or prefix notation), where the operators go in front of the operands.
Brackets
One result of reverse Polish notation is that there is no need for any brackets, like we sometimes put in mathematical expressions we humans do. For example, consider this expression, which uses infix notation:
( ( ( 1 + 2) * 4 ) + 7 / (5 + 3)
The brackets are important to us humans because of precedance. We need them to ensure the 1 + 2 is done before we multiply by 4, for example. Now consider the reverse Polish notation equivalent:
1 2 + 4 * 7 + 5 3 + /
This can be interpretted as the following: take 1 and 2 and add them to get a result. Then take 4 and multiply it to the result to get a new result. Then take 7 and add it to the new result. Then take 5 and 3 and add them. Finally divide the numbers. If you are slightly confused by this, all will become clear in the next section. What you should always remember at this time, however, is that when you reach an operator you go back and get only the last two operands.
Why do we need Reverse Polish notation?
You can see from the last example that we have removed all the brackets. They are not needed anymore because the order in which you add, multiply, subtract and divide, for example, is absolutely clear and unambiguous. This in itself is good but reverse Polish notation was proposed and became widely used because of the way computers work, using an area of RAM called the 'stack'. By using reverse Polish notation, two things result:
- the number of times a computer has to access the memory will be reduced
- the stack can be used.
The stack
The stack is a special area of memory. It is a data structure in that it holds data items. The interesting property of a stack, however, is that data items leave it in a LAST IN FIRST OUT (or LIFO) order. Think of a spindle of blank DVDs. You put blank DVDs on the spindle. When you want to remove one, you have to remove the one that was put on last - it's impossible to get to ones lower down without removing the top ones first.