Postfix Notation

Postfix also known as Reverse Polish Notation (or RPN), is a notational system where the operation/function follows the arguments. For example, "1 2 add" would be postfix notation for adding the numbers 1 and 2.

Most programming languages use either prefix notation ("add(1, 2)" or "(add 1 2)") or infix notation ("1 add 2" or "1 + 2"). Prefix and infix are more familiar to most people, as they are the standard notations used for arithmetic and algebra. Many people wonder why anyone would use this "weird" postfix notation.

The answer is that it is useful, especially for programming, because it clearly shows the order in which operations are performed, and because it disambiguates operator groupings. For example, look at this postfix expression: 

  1 2 + 3 * 6 + 2 3 + /
This means "take 1 and 2, add them, take 3 and multiply, take 6 and add, take 2 and 3, add them, and divide". In contrast, the equivalent expression in InfixNotation is 

  (((1 + 2) * 3) + 6) / (2 + 3)
This may seem more familiar, but note the need for parentheses to control the order of evaluation. The prefix notation would be 

  (/ (+ (* (+ 1 2) 3) 6) (+ 2 3))
which you to read "inside-out" to evaluate.

It isn't all roses, however: for example, in the expression above, you have to remember all arguments left for "future operations": for example, for the last operation ("divide"), it is at least as cumbersome to find out just what is to be divided as it is to read the prefix expressions. Postfix notation also really only makes sense for languages where operations are not first-class; and so, is ill suited for most FunctionalProgrammingLanguages.

In programming languages that use postfix notation, the order of operations is clear. For example, 

  getWindow topLeft x
means "call getWindow, then call topLeft with that result, then call x with that result". The prefix notation would be 

  (x (topLeft (getWindow)))
which is "inside-out and backwards" in comparison to the actual order of operations.

The most difficult thing in functional prefix notation is that, usually the arguments are evaluated before the function, but arguments to the left are evaluated before arguments to the right. So you actually end reading some parts of the expression from left to right, and some from right to left.

Some programming languages, such as ForthLanguage, are designed to use postfix notation. Such languages generally use a stack to hold arguments and intermediate results. So, for example, "1 2 + 3 *" is evaluated as "push 1 to the stack; push 2 to the stack; pop two items from the stack, add them, and push the result (3) to the stack; push 3 to the stack; pop two items from the stack, multiply them, and push the result (9) to the stack". Such an evaluator is very easy to implement, and very easy to extend with additional operations.

Many other programming languages support similar notations. For example, "getWindow topLeft x" could be a SmalltalkLanguage expression, where getWindow returns an object, topLeft is a message sent to it, and x is a message sent to the result of that operation.

In many languages, a similar expression could be represented as "getWindow().topLeft().x()" or "getWindow()->topLeft()->x()". Here, "." or "->" are infix operators, but if you ignore them and look only at the function calls, you get something similar to a postfix expression. The point here is that postfix is not really unnatural; programmers think this way all the time. Postfix only becomes difficult for people to read when the stack is used to store a value "under" some evaluation.

This is not an attempt to convert the world to postfix, nor to convince anyone that prefix and infix notations are "bad". It simply demonstrates why some people like to use postfix for some purposes.

The prefix notation doesn't require parentheses if the number of arguments are known. Then you can write the postfix expression 

 1 2 + 3 * 6 + 2 3 + /
as the prefix expression 

 / + * + 1 2 3 6 + 2 3
. Both of these are tree-traversals (preorder vs. postorder), but both of them depend on the number of arguments being known, as well as the fact that the leaf nodes have numbers on them while the non-leaf nodes have operators on them. 

                    /
             +             +
       *           6     2   3
   +       3
 1   2
Postfix notation still has the advantage that it reflects the order in which operations are performed.

-- EdwardKiser

The main difference is that postfix doesn't require parsing in the sense that the prefix notation does. In postfix notation, the number of arguments for a given operator (word) needs only be known to that word -- no additional layer of look-ahead is required -- the elements are executed as they are encountered.

Consider print + * 3 2 1 and the gymnastics required to evaluate it:

And the icky part is that you need some mechanism to tell print how many arguments to expect in the expression that follows.

As opposed to 3 2 * 1 + print which goes like this:

Now, optimizing compilers can pretty much make all of this moot, but what's not moot is that I can read and evaluate a progression of RPN expressions without getting lost, whereas, without brackets of some kind, other notations are more of an adventure.

Not really. Optimizing compilers can't rearrange the order of functions that return values, only atomic numbers. The reason is side-effects: "10 + getSalary() + getBonus()" could yield a different result than "getBonus() + getSalary() + 10" since the methods could be dependent upon the sequencing of shared (global) state.

Further, because the RPN notation more closely models what the machine has to do to accomplish the task, interactive testing and analysis is easier.

And magically, because of the lack of look-ahead parsing overhead, the whole thing tends to fit in really small spaces. I have to admit that, though I make my living as an InfixNotation coder with occasional excursions into raw AssemblyLanguage, I'm a big fan of PostfixNotation.

Another consequence of extensible RPN is readable stuff like this: 

 conveyor signal until
 right arm full extend
 right hand open
 10 seconds wait
 right hand close
 right arm 5 degrees raise
 right arm 15 degrees rotate
 right arm 5 degrees lower
 right hand open
 right arm return
-- GarryHamilton

The prefix notation can also be evaluated with a stack, but the stack has to be able to contain partial subexpressions. When each subexpression is completed, you must evaluate it and push its result back into the input (or at least pretend to). The evaluator produces the result of * 3 2 slightly sooner than you think, like this:

It might be amusing to write a Scheme program to do this. If you want to see a Scheme macro that converts infix to postfix, there's one on DefineSyntax.

The JoyLanguage is a lovely postfix FunctionalProgrammingLanguage. -- ThomasColthurst

In JoyLanguage and ForthLanguage this is also known as ConcatenativeCombinators?.

Wouldn't PipesAndFilters also qualify as PostfixNotation? also known as CollectsAndSelects? or UseEnumerationsInsteadOfForLoops. -- zuzu

Contrast: PolishNotation, InfixNotation

CategoryMath

EditText of this page (last edited January 5, 2014) or FindPage with title or text search