If you're new here, you may want to subscribe to my RSS feed. Thanks for visiting!

Reverse Polish Notation

So why begin with Reverse Polish Notation (RPN)? Although binary is pretty important to the operation of your computer I thought it better to cover a rarely covered subject that is fundamental to how those binary values are processed.

We humans think about mathematics very differently to computers. The way we express a mathematical equation is called ‘Infix’. Here is an example.

1 + 4 * 3

So this seems pretty simple. Except for one point, it can have two results. If you type that that equation into the calculator on your computer it will either come up with the result 13 or 15. Why? Because of operator precedence. Sometime in the 16th century (sorry about the history lesson) some clever bugger came up with a simple table of precedence.

1. exponents and roots (highest precedence)
2. multiplication and division
3. addition and subtraction (lowest precedence)

This means that it is more important to multiply two values together than add them together. In our above example let us first look at it without precedence.

1 + 4 = 5
5 *3 = 15

Then with precedence we multiply the 4 and 3 first.

4 * 3 = 12
12 + 1 = 13

So is your calculator wrong to return 15? Not really it just means it does not take into account operator precedence. (note: Windows Calculator lets you switch between Standard & Scientific, in standard it ignores precedence, in scientific it uses operator precedence, go try this simple example if you can be bothered)

Parentheses

We can be clearer about our intentions so if we really want the 1+4 added together first then (in Infix) put the 1 + 4 in parentheses (brackets to you and me). So with or without precedence we get the same result.

(1 + 4) * 3 = 15

Back to RPN

Computers are not great with dealing with things that are ambiguous and more importantly they evaluate the instructions we give them one at a time. So given that they cannot inherently understand precedence they rely upon being fed the instructions in an order that matches how they work.

This is where RPN comes in. RPN is a notation that a computer can understand because it is stack based. A stack is a LIFO (Last In First Out) which means that the last item you put on the stack is the first one out.

Our example again.

1 + 4 * 3

In RPN (taking into account precedence)

1 4 3 * +

Now at this point I am not going to give you lots of example output on how the stack works but let you try it for yourself. I have written a RPN parser (in PHP) for you to try out yourself. Go to RPN Parser and type in the above RPN (in left hand entry box) and press ‘EVAL’. You should get the correct answer ‘13‘.

Now try.

1 4 + 3 *

This time you should have got 15. So you can now see that with RPN that there is no ambiguity and hopefully you can start to see how the stack is used to create the precedence that is missing without having any parentheses.

Converting to RPN

A large proportion of commonly used programming languages use Infix notation so must have the Infix translated into RPN during compilation time (something like Forth is stack based and natively understands RPN).

What is interesting (to me anyway) is that understanding the process of compilation of Infix TO Postfix (RPN) is the basis for writing a complete compiler and not just the maths parts. The compilation subject is a massive one (so not something I can cover here!) but I hope this has given an insight and has piqued your interest in the subject.)

What can we learn from this?

So why is this all so important? Operator precedence affects every line of code you write. Your compiler/interpreter evaluates your code and (in most cases) produces a RPN like output. When you are trying to work out where to put brackets you can now see what effect it has on the order of execution. (Keep in mind that many compilers operator precedence left to right AND right to left, example)

RPN Parser

If you have not already done so please go check out the RPN Parser. I had great fun writing it and I hope it will help some of you learn something.

Further Reading

• Stack
• LIFO
• Reverse Polish Notation
• Infix
• Compiler