Postfix notation

From Esolang
Jump to: navigation, search

Postfix 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)
        }
    }
}

Concrete Implementations

Example implementations of postfix expression evaluators in concrete languages: