As part of our brief look at other programming languages and paradigms, we concentrated on writing expressions in prefix (operator comes first) and postfix (operator comes last).

Our usual arithmetic notation is called infix, because operators come in the middle (in between) the operands, as in:

    1 + 2
    3 * 4 + 5
    6 + 6 * 7

Prefix

The Lisp family of languages (including Scheme) use prefix notation, and surround each operation with parentheses, so the above three expressions look like these:

    (+ 1 2)
    (+ (* 3 4) 5)
    (+ 6 (* 6 7))

You evaluate them from the inside out, and left to right. Here’s a worked example:

    (+ (* 2 3) (* (- 5 1) 6))
 ⇒ (+ 6 (* (- 5 1) 6))
 ⇒ (+ 6 (* 4 6))
 ⇒ (+ 6 24)
 ⇒ 30

Postfix

Postfix notation is also known as RPN (Reverse Polish Notation). Many calculators were built to use RPN in decades past, and it is used in a few older programming languages like Forth and Postscript. (Postscript is still used today in many higher-end printers, and it’s the core of PDF.) Postfix is a very simple notation that needs no parentheses at all.

Here are the initial three examples in postfix:

    1 2 +
    3 4 * 5 +
    6 6 7 * +

As you evaluate postfix expressions, you manipulate a stack data structure. Just leave numbers on the stack (our stacks will grow left to right). When you reach an operator, remove the top two numbers on the stack, apply the operator two them, and replace them with the result. Here’s a demonstration:

    6 6 7 * +    ; at the multiply, pop 6 and 7, push 42
 ⇒ 6 42 +       ; at the add, pop 6 and 42, push 48
 ⇒ 48           ; the answer

The larger example is written and evaluated like this:

    2 3 * 5 1 - 6 * +
 ⇒ 6 5 1 - 6 * +
 ⇒ 6 4 6 * +
 ⇒ 6 24 +
 ⇒ 30