Postfix notation

Postfix notation, or reverse Polish notation, is one of the four operator notations, and one of the three powerful notations (Prefix notation, Postfix, Surround notation), and due to ease of implementation, arguably the most powerful. It is usually used with a stack (FILO queue).

Examples

 2 2 + 4 *

Implementation

Postfix notation is INCREDIBLY easy to implement. The reason is simple: It directly maps to a stack operation. Here's a pseudocode algorithm to represent it:

st = stack()
postfixexp = input() // Assume input is always a valid postfix expression (well, don't do that, not in real programming, but this is pseudocode)

exp = split(postfixexp, " ") // Split by spaces

foreach(symbol in exp) {
    if isDigit(symbol) {
        st.push(int(symbol))
    }
    elif isOp(symbol) {
        if symbol == "+" {
            a = st.pop()
            b = st.pop()
            st.push(b+a)
        } else if symbol == "-" {
            a = st.pop()
            b = st.pop()
            st.push(b-a)
        } else if symbol == "*" {
            a = st.pop()
            b = st.pop()
            st.push(b*a)
        } else if symbol == "/" {
            a = st.pop()
            b = st.pop()
            st.push(b/a)
        } else if symbol == "%" {
            a = st.pop()
            b = st.pop()
            st.push(b%a)
        }
    }
}

A more straightforward pseudocode:

st = stack()
postfixexp = input() // An invalid postfix expression is still a postfix expression.
exp = split(postfixexp, " ") // Split by spaces

foreach(symbol in exp) {
    if isDigit(symbol) {
        st.push(int(symbol))
    }
    elif "+-*/%" has symbol {
        execute(st.pop(),symbol,st.pop())
        // evaluates stack[-1] op stack[-2]
    }
}

Concrete Implementations

Example implementations of postfix expression evaluators in concrete languages:

• Haskell: here.

This is an implementation in Python supporting numbers with multiple digits:

stack = []
prog = "22 22+4*" # Our program, a postfix expression.
for x,i in enumerate(prog): # Foreach program:
    if i in "0123456789":
        if prog[x-1] in "0123456789":
            stack.append(stack.pop() * 10 + int(i))
        else:
            stack.append(int(i))
    elif i in "+-*/%":
        stack.append (
            eval (
                str(stack.pop())
                + i
                + str(stack.pop())
            )
        )

print(stack)