Reverse Polish Notation - What is is and where did the name come from?

Reverse Polish notation (or postfix notation) is a mathematical notation where the operators follow their operands. This contrasts with the more generally adopted infix notation where operators are interspersed with operands.

For example, the infix expression \(1 + 2 * 3\) would be represented in RPN as \(1 \space 2 + 3 \space *\).

Reverse Polish Notation was acually created as “Polish Notation” by the Polish logician Jan Lukasiewicz. Faced with such a “unfamilar” spelling, people chose the simpler name of Polish notation rather than woo-kah-sheh-vitch notation and the name stuck.

In Polish Notation the operators precede the operands. The previous example would be written \(* \space 3 + 1 \space 2\).

For this reason Polish (or Lukasiewicz) notation can also be referred to as prefix notation.

RPN has several advantanges over infix notation. For example the order of evaluation is unambiguous. Infix notation on the other hand would require parenthesis to override the standard precedence rules.

It is also easier to parse RPN and evaluate it in a computer program, just a simple stack is required.

1. If the current symbol is an operand, push it to the stack.
2. Otherwise if it is an operator, pop the required number of operands from the stack.
3. Apply the operator to the operands and then push the result back on to the stack.

This simplicity led to RPN being used by stack based languages such as Forth and Postscript. Additionally Hewlett-Packard used RPN in their desktop and handheld calculators during the 1970s and 80s.

The most notable use of postfix notation today is in the LISP family of languages.