Course4all
Join us on telegram
Home/dsa/Stack/Evaluate Reverse Polish Notation

Evaluate Reverse Polish Notation

Master this topic with zero to advance depth.

Evaluate Reverse Polish Notation

Evaluate the value of an arithmetic expression in Reverse Polish Notation. Valid operators are +, -, *, and /.

Visual Representation

Tokens: ["2", "1", "+", "3", "*"] 1. Token "2": Push. Stack: [2] 2. Token "1": Push. Stack: [2, 1] 3. Token "+": Pop 1, Pop 2. Res = 2 + 1 = 3. Push. Stack: [3] 4. Token "3": Push. Stack: [3, 3] 5. Token "*": Pop 3, Pop 3. Res = 3 * 3 = 9. Push. Stack: [9] Result: 9
Medium

Examples

Input: tokens = ["2","1","+","3","*"]
Output: 9

((2 + 1) * 3) = 9

Approach 1

Level I: Brute Force (Recursive Evaluation)

Intuition

Without knowing the stack trick, one naive approach is to scan the token list for an operator, evaluate the two preceding operands, replace those three tokens with the result, and repeat until one token remains. This is simpler to reason about but requires repeated passes over the list.

⏱ O(N^2) because for each of the N tokens that is an operator, we scan back to find the two operands.💾 O(N) for the mutable token list copy.
java
import java.util.*;

public class Main {
    public static int evalRPN(String[] tokens) {
        List<String> list = new ArrayList<>(Arrays.asList(tokens));
        while (list.size() > 1) {
            for (int i = 0; i < list.size(); i++) {
                String t = list.get(i);
                if (t.equals("+") || t.equals("-") || t.equals("*") || t.equals("/")) {
                    int a = Integer.parseInt(list.get(i - 2));
                    int b = Integer.parseInt(list.get(i - 1));
                    int res = 0;
                    if (t.equals("+")) res = a + b;
                    else if (t.equals("-")) res = a - b;
                    else if (t.equals("*")) res = a * b;
                    else res = a / b;
                    list.set(i - 2, String.valueOf(res));
                    list.remove(i - 1);
                    list.remove(i - 1);
                    break;
                }
            }
        }
        return Integer.parseInt(list.get(0));
    }

    public static void main(String[] args) {
        System.out.println(evalRPN(new String[]{"2","1","+","3","*"})); // 9
    }
}
Approach 2

Level III: Optimal (Stack Evaluation)

Intuition

Use a stack to store operands. When an operator is encountered, pop the top two operands, apply the operator, and push the result back. This naturally handles the postfix order without parentheses.

⏱ O(N)💾 O(N)

Detailed Dry Run

TokenActionStack StatusCalculated
"2"Push[2]-
"1"Push[2, 1]-
"+"Pop, Pop, Add[3]2 + 1 = 3
"3"Push[3, 3]-
"*"Pop, Pop, Mul[9]3 * 3 = 9
java
import java.util.Stack;

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

    public static void main(String[] args) {
        Solution sol = new Solution();
        System.out.println(sol.evalRPN(new String[]{"2","1","+","3","*"})); // Output: 9
    }
}

⚠️ Common Pitfalls & Tips

Be mindful of integer division in Python (int(a/b)) and JavaScript (Math.trunc(a/b)), as they must truncate toward zero.

← Previous QuestionImplement Stack using Queues
Next Question →Daily Temperatures