Reverse Polish Notation

What is it

Reverse polish notation is a post fix notation created in you guessed it Poland by a logician named Jan Łukasiewicz. The reason for this form of notation is that it allows for math to be expressed in the most concise manner and leave absolutely no ambiguity to what the formula’s author is trying to express. When you think of mathematical equations you usually think in terms of infix notation. Let’s look at the following example:

1 + 6 * 4 = 25

This formula is solved using the order of operations which most people learn when they are young. The problem is that this becomes ambiguous as to what the author was intending to model. The argument can always be made that the author swapped the two operations around without thinking. Meaning what he really meant was:

1 + 6 * 4 = 28

To help clearly define meaning in infix notation we use common symbols such as parenthesis and brackets, so to clearly define the above lets add some parenthesis:

1 + (6 * 4) = 25

There you go. We now have a clearly defined formula that is not ambiguous. The only thing is that it could be more concise. That’s where RPN comes in. To express the above it would look something like:

6 4 * 1 + = 25

Looks confusing doesn’t it?

How to Use it

Let’s keep things simple to start off. Let’s do a simple addition problem in RPN. When written using infix notation it will look like:

1 + 2 + 3 = 6

The way RPN works is you read the formula left to right. When you encounter a number, you push the number onto the “stack”. Every time you encounter an operator you apply it to the top two numbers in the stack. Well that’s easy enough in theory let’s look at it in practice. Let’s put the above example into RPN:

1 2 3 + + = 6

Now let’s break this down into a step by step process, and solve the equation. To review we read the formula from left to right, so the first thing that we read is a 1. Therefore, we add it to the stack.

1

Now we keep reading right and the next thing we encounter is a 2. So we now add that to the stack.

2

1

We then keep reading right and find a 3 and you guessed it. Add it to the stack.

3

2

1

Now this is where it gets tricky. The next thing we encounter is an operator, so we apply it to the top two numbers in the stack. The answer is then pushed into the stack. To put it in infix notation we would do “3 + 2” which is  5 then add that to the stack, so that our stack would look like this:

5

1

Finally, we reach another operator so we apply that to the top two numbers in the stack. We therefore end up with the answer we were looking for, which is the only number left in the stack.

6

Right about now you’re probably asking why not just use infix notation since it is much easier to read, and everyone understands it.

Why Use it

The main reason RPN has survived until today is because of technology. Computers and calculators don’t have an understanding of context and meaning. Remember computers think in binary which is a very literal language of 1’s and 0’s. Parenthesis is a concept that cannot be literally translated into a computer. Instead that knowledge is programmed through logical statements parsing the formula that it has been presented with and ordering them in you guessed it RPN. So with our above example the logical code would determine that what you would like to run is:

3 + 2 = 5

5 + 1 = 6

Do you see the similarity? In reality a modern processors would see something like:

11 10 +

101 1 +

Now remember what I said earlier, that RPN is very unambiguous, concise, and that computers think in binary. Therefore, RPN mimics how computers would solve the problem with none of the overhead involved in giving context to symbols such as parenthesis or even having to figure out orders of operations. It allows processors to be brutally efficient by allowing it to do the absolute least amount of work to solve math problems. It doesn’t even have an equals sign to read and waste time on.

So most IT professionals at this point ask why they should care. Well it is commonly implemented in several technologies. One of the best uses for it is to pass a formula on to a computer in an unambiguous and concise manner which would not require additional overhead from having to decipher what the user is trying to convey. Your program would be able to just read from left to right, and the computer would be able to know exactly what the user intends.

In Practice

So now that we know all about RPN let’s make a short little program to demonstrate its ease to parse and process. I started off by declaring variables and creating objects. It asks the user to input a RPN formula then divides the formula up into different components.

 1: //Declare Variables

 

 2: String formula = "";

 

 3: String delims = "[ ]+";

 

 4: int top = 0;

 

 5: int result, num1, num2 = 0;

 

 6: //Create objects

 

 7: InputStreamReader isr = new InputStreamReader(System.in);

 

 8: BufferedReader input = new BufferedReader(isr);

 

 9: //Request input

 

 10: System.out.print("Please input formula in reverse polish notation: ");

 

 11: try

 

 12: {

 

 13:     formula = input.readLine();

 

 14: }

 

 15: catch (IOException e)

 

 16: {

 

 17:     e.printStackTrace();

 

 18: }

 

 19: //Prepare data for interpretation

 

 20: String[] tokens = formula.split(delims);

 

 21: String[] stack = new String[formula.length()];

 

Now for the code that actually processes the formula. For this part I just used loops to run through and identify if each value is an operator or if it is a value. If it is not an operator then it will assume it is a value and add it to the stack. It then adjusts the “top” variable to the next slot in the array. If it is an operator, it will figure out which number is on the top of the stack by going through it until it finds a value other than “null”. It then does the appropriate operation with the top two numbers in the stack. It then enters the new value into the stack, removes the top number, and readjusts the “top” variable to make incoming values go into the right spot within the stack.

 1: for(int i = 0; i < tokens.length; i++)

 

 2:         {

 

 3:             if(tokens[i].contains("+"))//Add values

 

 4:             {

 

 5:                 for(int k = stack.length-1; k > 0; k--)

 

 6:                 {

 

 7:                     if(stack[k] != null)

 

 8:                     {

 

 9:                         num1 = Integer.parseInt(stack[k]);

 

 10:                         num2 = Integer.parseInt(stack[k-1]);

 

 11:

 

 12:                         result = num1 + num2;

 

 13:                         stack[k] = null;

 

 14:                         stack[k-1] = Integer.toString(result);

 

 15:                         top--;

 

 16:                         k = -1;

 

 17:

 

 18:                         System.out.println("Operation: " + num1 + " + " + num2 + " = " + result);

 

 19:                     }

 

 20:                 }

 

 21: ...

 

 22:

 

 23:

 

 24: ...

 

 25:

 

 26:     else//Value not an operator, add to stack 

 

 27:     {

 

 28:         stack[top] = tokens[i];

 

 29:         System.out.println("Added " + tokens[i] + " to stack");

 

 30:         top++;

 

 31:     }

 

 32: }//End for loop

 

Finally, it outputs the answer. So that’s it. That’s Reverse Polish Notation and how to use it. For actual production implementations this example could use quite a bit of optimization, and error handling. For the entire example you can download it below.

Downloads

Download Example

Comments

  1. I’m really impressed with your writing skills as well as with the layout on your weblog. Is this a paid theme or did you customize it yourself? Either way keep up the excellent quality writing, it’s rare to see a great blog like this one today.. shared hosting | cheap web hosting |

Leave a Reply

Your email address will not be published. Required fields are marked *