Problem #150: Evaluate Reverse Polish Notation

Intuition & Strategy Breakdown

Use a stack. Push numbers onto stack; when encountering an operator (+, -, *, /), pop two operands, evaluate result, and push result back.

Python Solution

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

Java Solution

class Solution {
    public int evalRPN(String[] tokens) {
        Stack stack = new Stack<>();
        for (String t : tokens) {
            if ("+-*/".contains(t) && t.length() == 1) {
                int b = stack.pop();
                int a = stack.pop();
                if (t.equals("+")) stack.push(a + b);
                else if (t.equals("-")) stack.push(a - b);
                else if (t.equals("*")) stack.push(a * b);
                else stack.push(a / b);
            } else {
                stack.push(Integer.parseInt(t));
            }
        }
        return stack.pop();
    }
}