Evaluate Reverse Polish Notation

Mediumstackarray
Category: Stack
Companies that ask this question:
AmazonFacebookLinkedIn
LeetCode →NeetCode →

Approach

Evaluate Reverse Polish Notation

Problem Statement

You are given an array of strings tokens that represents an arithmetic expression in Reverse Polish Notation (RPN).

Evaluate the expression and return an integer that represents the value of the expression.

Note:

  • Valid operators are +, -, *, and /
  • Each operand may be an integer or another expression
  • Division between two integers should truncate toward zero
  • The input is guaranteed to be a valid RPN expression

Examples

Example 1

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

Example 2

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

Example 3

Input: tokens = ["10","6","9","3","+","-11","*","/","*","17","+","5","+"]
Output: 22
Explanation: ((10 * (6 / ((9 + 3) * -11))) + 17) + 5 = 22

Intuition

Reverse Polish Notation (postfix notation) is a mathematical notation where operators follow their operands. For example:

  • Infix: (2 + 1) * 3
  • RPN: 2 1 + 3 *

The beauty of RPN is that it doesn't require parentheses and can be evaluated using a stack in a single left-to-right scan.

Algorithm:

  1. Scan tokens from left to right
  2. If token is a number → push to stack
  3. If token is an operator → pop two operands, apply operator, push result back

Pattern Recognition

This is a classic Stack problem with these characteristics:

  • Linear scan of input
  • Need to track intermediate results
  • LIFO (Last In First Out) processing
  • Operators work on most recent operands

Approach

  1. Initialize Stack: Create an empty stack
  2. Process Each Token:
    • If Number: Convert string to integer and push to stack
    • If Operator:
      • Pop second operand (right)
      • Pop first operand (left)
      • Apply operator: left op right
      • Push result back to stack
  3. Return Result: The stack will contain exactly one element (the final result)

Order Matters: When popping for operators, remember:

right = stack.pop()
left = stack.pop()
result = left op right  // NOT right op left

Edge Cases

  • Single number (no operators)
  • Negative numbers
  • Division by zero (guaranteed not to happen per problem)
  • Integer division truncating toward zero
  • Long expressions with many operators

Complexity Analysis

  • Time Complexity: O(n) where n is the number of tokens
    • Single pass through all tokens
    • Each token processed once (push or pop operations are O(1))
  • Space Complexity: O(n)
    • Stack can grow up to n/2 elements (all numbers before any operator)
    • In worst case, proportional to input size

Solution

java
1class Solution {
2    public int evalRPN(String[] tokens) {
3        Stack<Integer> stack = new Stack<>();
4
5        for (String token : tokens) {
6            if (isOperator(token)) {
7                // Pop two operands (order matters!)
8                int right = stack.pop();
9                int left = stack.pop();
10
11                // Apply operator and push result
12                int result = applyOperator(left, right, token);
13                stack.push(result);
14            } else {
15                // It's a number, push to stack
16                stack.push(Integer.parseInt(token));
17            }
18        }
19
20        // Final result is the only element in stack
21        return stack.pop();
22    }
23
24    private boolean isOperator(String token) {
25        return token.equals("+") || token.equals("-") ||
26               token.equals("*") || token.equals("/");
27    }
28
29    private int applyOperator(int left, int right, String operator) {
30        switch (operator) {
31            case "+": return left + right;
32            case "-": return left - right;
33            case "*": return left * right;
34            case "/": return left / right;  // Integer division (truncates toward zero)
35            default: throw new IllegalArgumentException("Invalid operator");
36        }
37    }
38}
39
Loading visualizer...