RPN is a form of expressing mathematical calculations through making good use of the stack. You specify the numbers first, then specify the actions to be performed upon those numbers.

I.e., what normally would be written as "2 + 3 - 5" in RPN would look like "2 3 + 5 -". It takes a while to sink in, but it becomes quite easy once you picture how the stack works:
Operation:
  2     3        +      5      -
Stack:
|  |   |  |    |  |    |  |   |  |
|  |   |3 |    |  |    |5 |   |  |
|2 |   |2 |    |5 |    |5 |   |0 |
----   ----    ----    ----   ----   
The result of the operation is placed back into the stack and is ready for the next operation. This continues until there's only one number left in the stack.

That's really all there is to it.
In point of fact, RPN is used to this day in Hewlett-Packard electronic calculators because it was much easier to implement than the more linear forward notation when the electronic calculator was new. A stack-based system (such as RPN) is more efficient (especially for the machine) and minimizes the use of randomly-addressable registers, which are more costly to implement (at least, they were then).

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.

Reverse polish notation is really related to tree traversal algorithms. If you build a tree whose nodes are operations and its leaves are the numbers (or variables), you can express any calculation you like. If you read the tree in post order, you get the reverse polish notation equivalent of that. If you use pre order or in order, you get polish notation and traditional notation, respectively.

Example:

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

(-) - (2) 
 |
(*) - (5)
 |
(+) - (4)
 |
(3)

I know it's an awful way to draw a tree... my excuses...

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
However, things get a little hairy when you write RPN like this:
6 12 4 3 / * -
This is, in fact, the same as the problem above. You use a similar process to make sense of it. However, you must reverse the number line first.

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
*:OK, so most people would put the + on the left. Sue me.
When I was in calculus at the University of Minnesota everyone either had the HP 48G or the TI-83 calculator. Now the TI (Texas Instruments) was far easier to use, it had graphing, and advanced math functions but it also worked just like a normal calculator. The HP was much more powerful (could solve integrals, graph 3d equations, etc) but used RPN. This made it highly entertaining when someone asked to borrow your calculator during a test and could not for the life of them figure out how the damn things worked.

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.

Log in or register to write something here or to contact authors.