Reverse polish notation
is really related to tree traversal
algorithms. If you build a tree
and its leaves
are the numbers
), 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
Building the tree for (3+4)*5-2 gives us a tree like this one:
(-) - (2)
I know it's an awful way to draw a tree... my excuses...
(*) - (5)
(+) - (4)
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.