Problem statement

Evaluate an arithmetic expression given in Reverse Polish Notation (postfix). Valid operators are +, -, *, /. Division truncates toward zero. No division by zero occurs, and every expression is valid.

Example 1

Input: tokens = ["2","1","+","3","*"]
Output: 9
Explanation: ((2 + 1) × 3) = 9.

Example 2

Input: tokens = ["4","13","5","/","+"]
Output: 6
Explanation: (4 + (13 / 5)) = 6.

Constraints

• 1 <= tokens.length <= 30
• Operands fit in 32-bit integers.

Hints for Evaluate Reverse Polish Notation

1. Hint 1

   Push numbers; on an operator pop two, apply, push the result.

2. Hint 2

   Order matters for - and /: the second pop is the left operand.

How to solve Evaluate Reverse Polish Notation

Postfix notation exists precisely so that no precedence rules and no parentheses are needed — the order of the tokens already encodes the tree. An operator always applies to the two subexpressions immediately before it, so operands can simply wait on a stack until an operator claims them.

Approach

1. Scan the tokens left to right, keeping a stack of computed values.
2. If the token is a number, push it.
3. If it is an operator, pop twice. The first pop is the right operand b, the second is the left operand a.
4. Compute a op b and push the result back — a finished subexpression is just another operand.
5. The single value left on the stack at the end is the answer.

Why it works

By induction, every value on the stack is a fully evaluated subexpression. When an operator is read, the expression is valid, so its two operands are the two most recently completed subexpressions — which are exactly the top two entries. Replacing them with the result keeps the invariant, so the last remaining value is the whole expression.

Complexity

• Time — O(n)
• Space — O(n)

Pitfalls

• Pop order is the classic bug. a is the second pop. It makes no difference for + and *, but reversing it silently breaks - and /.
• Division must truncate toward zero, not floor. In Python, -7 // 2 is -4 — wrong here; int(-7 / 2) gives -3, which is why the solution divides then truncates. JavaScript needs Math.trunc, since / yields a float.

Reference solution

Python

from typing import List

def evalRPN(tokens: List[str]) -> int:
    st = []
    for t in tokens:
        if t in ("+", "-", "*", "/"):
            b = st.pop()
            a = st.pop()
            if t == "+":
                st.append(a + b)
            elif t == "-":
                st.append(a - b)
            elif t == "*":
                st.append(a * b)
            else:
                st.append(int(a / b))
        else:
            st.append(int(t))
    return st[0]

Java

public static int evalRPN(String[] tokens) {
    Deque<Integer> st = new ArrayDeque<>();
    for (String t : tokens) {
        if (t.equals("+") || t.equals("-") || t.equals("*") || t.equals("/")) {
            int b = st.pop();
            int a = st.pop();
            if (t.equals("+")) st.push(a + b);
            else if (t.equals("-")) st.push(a - b);
            else if (t.equals("*")) st.push(a * b);
            else st.push(a / b);
        } else {
            st.push(Integer.parseInt(t));
        }
    }
    return st.pop();
}

C++

int evalRPN(vector<string>& tokens) {
    vector<int> st;
    for (const string& t : tokens) {
        if (t == "+" || t == "-" || t == "*" || t == "/") {
            int b = st.back(); st.pop_back();
            int a = st.back(); st.pop_back();
            if (t == "+") st.push_back(a + b);
            else if (t == "-") st.push_back(a - b);
            else if (t == "*") st.push_back(a * b);
            else st.push_back(a / b);
        } else {
            st.push_back(stoi(t));
        }
    }
    return st.back();
}

JavaScript

var evalRPN = function(tokens) {
    const st = [];
    for (const t of tokens) {
        if (t === "+" || t === "-" || t === "*" || t === "/") {
            const b = st.pop(), a = st.pop();
            if (t === "+") st.push(a + b);
            else if (t === "-") st.push(a - b);
            else if (t === "*") st.push(a * b);
            else st.push(Math.trunc(a / b));
        } else {
            st.push(parseInt(t, 10));
        }
    }
    return st[0];
};

Also on the editorial tab: C, C#, Go, Kotlin, PHP, Ruby, Rust, Swift, TypeScript.

More arrays problems

• Implement Router Medium
• Design Memory Allocator Medium
• Design a Food Rating System Medium
• Design an ATM Machine Medium
• Design Bitset Medium
• Range Frequency Queries Medium