Evaluate Reverse Polish Notation

Problem

Evaluate an arithmetic expression written in Reverse Polish Notation (RPN, a.k.a. postfix). In RPN, an operator comes after its two operands. ["2","1","+"] means 2 + 1. There are no parentheses — the order of tokens fully determines the order of operations. Each token is either an integer or one of +, -, , /. For an operator, apply it to the two most recent values, where the value seen first* is the left operand (so ["6","2","/"] is 6 / 2, not 2 / 6). Division truncates toward zero. The input is always a valid expression; return the final value.

Constraints

• 1 ≤ tokens.length ≤ 10⁴
• valid RPN expression

Approach — Stack

This is a Stack problem. The idea: scan the input once, pushing work onto a stack and popping when the top can be resolved, so the stack always reflects what's still open. Work through the reference code below line by line, then re-derive it yourself in the editor — that's how the pattern sticks.

Complexity: O(n) time, O(n) space.

Solution code

Python

class Solution:
    def evalRPN(self, tokens):
        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

import java.util.Stack;

class Solution {
    public int evalRPN(String[] tokens) {
        Stack<Integer> stack = new Stack<>();

        for (String token : tokens) {

            if (!"+-*/".contains(token)) {
                stack.push(Integer.valueOf(token));
                continue;
            }

            int number2 = stack.pop();
            int number1 = stack.pop();

            int result = 0;
            switch (token) {
                case "+":
                    result = number1 + number2;
                    break;
                case "-":
                    result = number1 - number2;
                    break;
                case "*":
                    result = number1 * number2;
                    break;
                case "/":
                    result = number1 / number2;
                    break;
            }

            stack.push(result);
        }

        return stack.pop();
    }
}

Practice it

Reading a solution isn't the same as being able to write it under pressure. Open this problem in the in-browser editor, hide the solution, and solve it from scratch — your code runs against real test cases instantly.