Polish Notation

Polish notation (prefix). A way of writing expressions in which the operator is written before its operands. For a binary operation, the form is op left right. The infix a + b becomes + a b.

Reverse Polish notation (postfix). The mirror image: the operator is written after its operands, as left right op. The infix a + b becomes a b +.

Both forms are parenthesis-free. The position of each operator relative to its operands already fixes the order of evaluation, so there is no need for parentheses and no need for precedence rules. This is the property that makes Polish notation so convenient for machines.

We will use one running expression throughout:

Polish notation is not a trick — it falls straight out of the syntax tree of the expression. Here is the tree for (a + b) \* (c - d):

Now read the tree with two classic traversals:

• Prefix = preorder traversal — visit the node first, then its left subtree, then its right subtree: \*, then + a b, then - c d.

  Prefix: \* + a b - c d

• Postfix = postorder traversal — visit the left subtree, then the right subtree, then the node: a b +, then c d -, then \*.

  Postfix: a b + c d - \*

The infix (a + b) \* (c - d) itself corresponds to an inorder traversal — and inorder is exactly the traversal that loses information unless you add parentheses back in.

Infix notation is ambiguous on its own. Without rules, a + b \* c could mean "add then multiply" or "multiply then add". We patch this with precedence (\* binds tighter than +) and with parentheses to override precedence.

Polish notation needs neither. Compare the two readings:

The two postfix strings are different sequences of tokens, so there is nothing to disambiguate — no brackets, no precedence table. The order of the operators alone tells you that in a b + c \* the + happens first, while in a b c \* + the \* happens first.

Postfix has a simple, mechanical evaluation rule using a single stack.

Rule. Scan the tokens left to right. Push every operand onto the stack. On every operator, pop the top two values, apply the operator, and push the result. When the scan ends, the single value left on the stack is the answer.

Order matters for non-commutative operators. The first popped value is the right operand and the second popped is the left operand. So for - you compute left - right, not right - left.

Let us evaluate 5 3 + 8 2 - \* (the postfix of (a + b) \* (c - d) with a=5, b=3, c=8, d=2):

The final value is 48, matching (5 + 3) \* (8 - 2) = 8 \* 6 = 48.

Postfix is one of the simplest intermediate representations a compiler can emit. It is linear — just a flat list of tokens — and it carries no parentheses or precedence, so a tiny stack machine can execute it directly with the loop above. Many bytecode interpreters (and old calculators) are essentially postfix stack machines.

It also connects naturally to three-address code (TAC). Each operator in the postfix string corresponds to one operation that "pops two, computes, pushes one result". Naming each result with a temporary turns postfix into TAC:

So postfix is essentially TAC with the temporaries left implicit on a stack instead of being named explicitly.

• Prefix = operator before operands (\* + a b - c d); postfix = operator after operands (a b + c d - \*).
• Both are parenthesis-free and unambiguous — no precedence rules or brackets needed.
• Prefix = preorder traversal of the syntax tree; postfix = postorder traversal.
• Evaluate postfix with a stack: push operands; on an operator pop two, apply, push the result.
• Mind operand order for - and /: first popped is the right operand.
• Postfix is a compact linear intermediate representation runnable by a stack machine, closely related to three-address code.