Start practising

Evaluate Reverse Polish Notation

Medium Stack Stack Basics Original on LeetCode

Evaluate Reverse Polish Notation is a medium stack problem solved with the stack basics pattern. The best approach, optimal (stack), runs in O(n) time and O(n) space.

Problem

Evaluate an arithmetic expression written in Reverse Polish Notation (operators come after their operands). Tokens are integers or one of + - * /. Division truncates toward zero.

Examples

Example 1

Input
tokens = ["3", "4", "+", "2", "*"]
Output
14
Why
(3 + 4) * 2.

Example 2

Input
tokens = ["7", "-2", "/"]
Output
-3
Why
Division truncates toward zero.

Constraints

  • 1 <= tokens.length <= 10^4
  • Operators are + - * /; the expression is always valid.

Animated walkthrough

A narrated, step-by-step animation that builds the solution from the idea up. Press play, or step through it at your own pace.

Concepts first, then the problem and every approach, step by step.

Space to play or pause · ← → to jump a step · click or drag the bar to seek

Solutions

Try it yourself first. Then compare: each approach lists its idea, the steps, its time and space, and the Java code.

ApproachTimeSpace
Optimal (stack)O(n)O(n)

1Optimal (stack)

TimeO(n)
SpaceO(n)

Push numbers. On an operator, pop b then a (b was pushed last) and push a op b. The single value left is the answer. This is the standard, and only sensible, approach.

  1. For each token: if it is an operator, pop b, pop a, push a op b.
  2. Otherwise push Integer.parseInt(token).
  3. Return the top.
Java
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();
    }
}

Edge cases to test

  • Negative number tokens like -2 (not the minus operator)
  • Operand order for - and /

Hints

Hint 1

When you see an operator, its two operands are the two most recent values.

FAQ

What is the best time complexity for Evaluate Reverse Polish Notation?

Optimal (stack) runs in O(n) time and O(n) extra space.

Which pattern does Evaluate Reverse Polish Notation use?

It is a stack problem that uses the stack basics pattern. Other problems with the same pattern: Valid Parentheses, Baseball Game, Asteroid Collision.

Which edge cases should I test for Evaluate Reverse Polish Notation?

Negative number tokens like -2 (not the minus operator); Operand order for - and /.