reverse Polish notation

Operation:
  2     3        +      5      -
Stack:
|  |   |  |    |  |    |  |   |  |
|  |   |3 |    |  |    |5 |   |  |
|2 |   |2 |    |5 |    |5 |   |0 |
----   ----    ----    ----   ----   

To this day, HP has managed to maintain the Cult of RPN - as can be seen on E2 and elsewhere, 'real (insert number-crunching profession here) use RPN' is a common theme when the subject comes up. Essentially, it was (and remains) a tradeoff; forcing the human to use an (initially) unfamiliar schema which was closer to the more efficient algorithms of the machine.

Before the flaming starts, please note that I have no opinion about which is 'better.' Once learned, RPN can, in fact, be more efficient than forward; it's a matter of taste. The Cult of RPN is akin to the Cult of Macintosh - there is always a small percentage of adherents to the system that vociferously claim it's better 'just because.'

Of course, the Germans, never ones to be slackers about anything, then went and built a conversational language around it. Go figure.

Nobody has bothered to mention why it's called Reverse Polish Notation.

It's because Jan Lukasiewicz, the inventor of this notation which allows arithmetic expressions to be written unambiguously without the use of parentheses, was from Poland.

Example:

Building the tree for (3+4)*5-2 gives us a tree like this one:

(-) - (2) 

 | 

(*) - (5) 

 | 

(+) - (4) 

 | 

(3) 
 

Inorder traversal gives us 3+4*5-2
Preorder traversal is - * + 3 4 5 2
Postorder traversal 3 4 + 5 * 2 -

Of course, with inorder, you need parenthesis in order to avoid ambiguity, but you don't need them with reverse polish notation.

This was also used in the venerable Forth programming language.

RPN is not as unnatural as you may think. In fact, you have probably been using RPN for a Very long time. How's that, you ask? Let me show you:

Lets start out with a simple RPN problem:

3 4 +

Now, add a line to the end:

     |
3 4 +|

And then move the + a bit:  

    +|
3 4  |

Finally, flip this puppy on its side*:

3
4 +
---

So, are you groking this now? The only thing I changed was the appearance of the problem, not the logic. Does it hold up with more complex problems? lets find out:

3 4 / 12 * 6 -

First, we have to add variables as place holders for results of operations:
          
3 4 / X 12 * Y 6 - Z

Then add the lines again, wherever there is an operator:

   |    |   |
3 4|X 12|Y 6|Z

Next, distribute the Operators:
  /|   *|  -|
3 4|X 12|Y 6|Z

And, finally, Flip it:
3
4/
--
X
12*
--
Y
6-
--
Z

6 12 4 3 / * -

3 4 12 6

   |    |   |
3 4|X 12|Y 6|Z

  /|   *|  -|
3 4|x 12|y 6|Z

3
4/
--
X
12*
--
Y
6-
--
Z

RPN is sort of like learning to touch type. It takes a while to get used to, but once you are good at it, it makes things a whole lot easier.