Command Palette

Search for a command to run...

Hectal
Problem 9.3 · Stack and Monotonic StackMedium

Evaluate Reverse Polish Notation

PatternStack for Matching and Undo

What it teaches: Postfix expressions need no brackets: push numbers, and each operator pops its two operands.

Practise it on judges as “Evaluate Reverse Polish Notation”.

The problem

Evaluate an arithmetic expression in Reverse Polish Notation, given as tokens. Operators are + - * /; division truncates towards zero. The expression is always valid.

Example 1

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

(2 + 1) × 3.

Example 2

Input: tokens = ["4", "13", "5", "/", "+"]
Output: 6

4 + 13 / 5 = 4 + 2.

Constraints

  • 1 ≤ tokens.length ≤ 10⁴
  • Results fit in a 32-bit int

Pattern clues in the wording

  • → Operators come after their operands
  • → The two most recent values combine

These clues point to Stack for Matching and Undo: Push openers and pop when the matching closer arrives; anything left over or mismatched is an error.

Stuck? Take one hint at a time

Solution.java · starter
import java.util.*;

class Solution {
    public int evalRPN(String[] tokens) {
        return 0;
    }
}

Write your solution locally or in your editor for now. The in-browser runner (Java first, then Python, C++ and more) will run these tests right here.

Test cases

#InputExpected
1
tokens = ["2","1","+","3","*"]
9
2
tokens = ["4","13","5","/","+"]
6
3
tokens = ["10","6","9","3","+","-11","*","/","*","17","+","5","+"]
22

+ 1 hidden test the code runner will check

From slow to fast

Approaches

1. Optimal: value stack · O(n)
1

Optimal: value stack

Time O(n) Space O(n)

Push numbers. For an operator, pop b then a, push a op b. The final value is the answer.

▶ Dry run: Evaluating 2 1 + 3 *tokens = [2, 1, +, 3, *]
2
0
1
1
↑i
+
2
3
3
*
4

stack(stack)

21

Step 1/4Push 2 and 1.

Approach 1
import java.util.ArrayDeque;
import java.util.Deque;

class Solution {
    public int evalRPN(String[] tokens) {
        Deque<Integer> st = new ArrayDeque<>();
        for (String t : tokens) {
            switch (t) {
                case "+" -> st.push(st.pop() + st.pop());
                case "*" -> st.push(st.pop() * st.pop());
                case "-" -> { int b = st.pop(), a = st.pop(); st.push(a - b); }
                case "/" -> { int b = st.pop(), a = st.pop(); st.push(a / b); }
                default -> st.push(Integer.parseInt(t));
            }
        }
        return st.pop();
    }
}

Verdict: One pass.

Before you submit

Edge cases and common mistakes

Test these inputs

  • Negative numbers like "-11" (a number, not the operator)
  • Division with negative results (truncates towards zero)
  • A single number

Mistakes people make

  • Popping operands in the wrong order for − and /.
  • Treating "-3" as the minus operator (compare whole tokens, not first characters).

Interview

Follow-up questions

How do you convert an ordinary infix expression to RPN?