150. Evaluate Reverse Polish Notation

← All Problems
medium Stack
Given an array of string tokens representing an arithmetic expression in Reverse Polish Notation (postfix notation), evaluate the expression and return the result as an integer. The valid operators are +, -, *, and /. Each operand is either an integer or another RPN expression. Division between two integers should truncate toward zero. The input is guaranteed to be a valid RPN expression.

Example

tokens = ["2", "1", "+", "3", "*"]

Output: 9

In standard notation this is (2 + 1) * 3 = 9. The + applies to 2 and 1 giving 3, then the * applies to that 3 and 3 giving 9.

Walk through the tokens left to right. If it's a number, push it onto the stack. If it's an operator, pop the top two numbers, apply the operator (second-popped op first-popped), and push the result back. The final value on the stack is the answer.

Why this works

Reverse Polish Notation puts operators after their operands, so you never need parentheses or precedence rules. A stack naturally collects operands. When you hit an operator, the two most recent operands are right on top of the stack, ready to be combined.

Step by step

  1. See a number — push it onto the stack.
  2. See an operator — pop two values (the top is the right operand, the second is the left operand).
  3. Apply the operator — compute the result and push it back onto the stack.
  4. Return the result — after processing all tokens, the single remaining value on the stack is the answer.
Time: O(n) Space: O(n) 
class Solution {
    public int evalRPN(String[] tokens) {
        Deque<Integer> stack = new ArrayDeque<>();
        for (String token : tokens) {
            switch (token) {
                case "+": stack.push(stack.pop() + stack.pop()); break;
                case "-":
                    int b = stack.pop(), a = stack.pop();  // order matters: a - b, not b - a
                    stack.push(a - b); break;
                case "*": stack.push(stack.pop() * stack.pop()); break;
                case "/":
                    int d = stack.pop(), c = stack.pop();  // order matters: c / d, not d / c
                    stack.push(c / d); break;
                default: stack.push(Integer.parseInt(token));  // push operand
            }
        }
        return stack.pop();
    }
}

class Solution {
public:
    int evalRPN(vector<string>& tokens) {
        stack<int> st;
        for (const string& token : tokens) {
            if (token == "+" || token == "-" || token == "*" || token == "/") {
                int b = st.top(); st.pop();
                int a = st.top(); st.pop();  // a op b — second-popped is the left operand
                if (token == "+") st.push(a + b);
                else if (token == "-") st.push(a - b);
                else if (token == "*") st.push(a * b);
                else st.push(a / b);  // C++ int division truncates toward zero
            } else {
                st.push(stoi(token));  // push operand
            }
        }
        return st.top();
    }
};

def evalRPN(tokens: list[str]) -> int:
    stack = []
    for token in tokens:
        if token in "+-*/":
            b, a = stack.pop(), stack.pop()  # b is top, a is second — order matters for - and /
            if token == '+':
                stack.append(a + b)
            elif token == '-':
                stack.append(a - b)
            elif token == '*':
                stack.append(a * b)
            else:
                stack.append(int(a / b))  # truncate toward zero
        else:
            stack.append(int(token))  # push operand
    return stack[0]