Evaluate postfix (RPN)

Evaluate an expression written with the operator after its operands, such as "3 4 +". No brackets or precedence rules needed.

Time O(n)Space O(n)Code C++, Python and C#

Watch it animatedStep through it, with the running line highlighted. Free with an account.

The idea

Numbers wait on the stack. An operator takes the top two numbers, applies itself, and pushes the result back for a later operator to use.

Code

C++PythonC#

int evalRpn(const vector<string>& tokens) {
    stack<int> st;
    for (const string& t : tokens) {
        if (isdigit(t.back())) { st.push(stoi(t)); continue; }
        int b = st.top(); st.pop(); int a = st.top(); st.pop();
        st.push(t == "+" ? a + b : t == "-" ? a - b
              : t == "*" ? a * b : a / b);
    }
    return st.top();
}

def eval_rpn(tokens: list[str]) -> int:
    stack = []
    for t in tokens:
        if t.lstrip('-').isdigit(): stack.append(int(t)); continue
        b, a = stack.pop(), stack.pop()
        stack.append(a + b if t == '+' else a - b if t == '-' else a * b if t == '*' else int(a / b))
    return stack.pop()

public static int EvalRpn(string[] tokens) {
    var stack = new Stack<int>();
    foreach (string t in tokens) {
        if (int.TryParse(t, out int n)) { stack.Push(n); continue; }
        int b = stack.Pop(), a = stack.Pop();
        stack.Push(t switch {
            "+" => a + b, "-" => a - b,
            "*" => a * b, _ => a / b });
    }
    return stack.Pop();
}

Tips

The first value popped is the right-hand operand. Getting that backwards breaks subtraction and division.
Compilers and calculators convert normal infix expressions to this form for exactly this reason.

In the .NET library

int.TryParse separates numbers from operators without exceptions. The switch expression is a compact way to map an operator to its result. C# integer division truncates towards zero.