Polish Notation

Polish Notation is a way of expressing arithmetic expressions that avoids the use of brackets to define priorities for evaluation of operators. Polish Notation was devised by the Polish philosopher and mathematician Jan Ɓukasiewicz (1878-1956) for use in symbolic logic. In his notation, the operators preceded their arguments, so that the InfixNotation expression

    (3 + 5) * (7 - 2)

would be written as

    * + 3 5 - 7 2

The 'reversed' form, Reverse Polish Notation (RPN), has however been found more convenient from a computational point of view. In this notation the above expression would be

    3 5 + 7 2 - *

In the first expression, the brackets tell us that we have to add 3 to 5, then subtract 2 from 7, and multiply the two results together. In Polish Notation, one has to parse the expression recursively to obtain the operands for each operator. In RPN, the numbers and operators are listed one after another, and an operator always acts on the most recent numbers in the list. The numbers can be thought of as forming a stack, like a pile of plates. The most recent number goes on the top of the stack. An operator takes the appropriate number of arguments from the top of the stack and replaces them by the result of the operation.

Reading from left to right, this is interpreted as follows:

   * + 3 5 - 7 2

This looks rather like lisp without the parentheses. Equivalent lisp:

   (* (+ 3 5) (- 7 2))

That's not a coincidence. LispLanguage is indeed a form of PolishNotation. Its parentheses are necessary in order to deal with things like operators with no fixed arity, e.g. both "(list 1 2)" and "(list 1 2 3 4 5)" are legal.


    3 5 + 7 2 - *

is a Forth expression.

ForthLanguage, in turn, uses ReversePolishNotation. Forth's operators have fixed arity and so do not need parentheses.
Q: Would the function-calling syntax of the conventional C/pascal-style programming languages be considered polish notation? Such as
or is there a different terminology for that syntax?

A: I would call it Polish or PrefixNotation, yes. This is especially exploited in functional languages such as ML and Haskell, which use currying to avoid even using parentheses to group parameters.

HewlettPackard calculators also used RPN. The expression would be entered:

    3 [enter] 5 + 7 [enter] 2 - *

where [enter] was effectively pushing a number onto a stack.
Contrast: InfixNotation, PostfixNotation

View edit of July 30, 2013 or FindPage with title or text search