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:

Push 3 onto the stack.
Push 5 onto the stack. The stack now contains (3, 5).
Apply the + operation: take the top two numbers off the stack, add them together, and put the result back on the stack. The stack now contains just the number 8.
Push 7 onto the stack.
Push 2 onto the stack. It now contains (8, 7, 2).
Apply the - operation: take the top two numbers off the stack, subtract the top one from the one below, and put the result back on the stack. The stack now contains (8, 5).
Apply the * operation: take the top two numbers off the stack, multiply them together, and put the result back on the stack. The stack now contains just the number 40.

* + 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.

and

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

 pow(2,10);

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

CategoryMath