Evaluate Reverse Polish Notation

LeetCode 150 | Difficulty: Medium

Medium

Problem Description

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

Evaluate the expression. Return an integer that represents the value of the expression.

Note that:

- The valid operators are `'+'`, `'-'`, `'*'`, and `'/'`.

- Each operand may be an integer or another expression.

- The division between two integers always **truncates toward zero**.

- There will not be any division by zero.

- The input represents a valid arithmetic expression in a reverse polish notation.

- The answer and all the intermediate calculations can be represented in a **32-bit** integer.

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
= ((10 * (6 / (12 * -11))) + 17) + 5
= ((10 * (6 / -132)) + 17) + 5
= ((10 * 0) + 17) + 5
= (0 + 17) + 5
= 17 + 5
= 22

Constraints:

- `1 <= tokens.length <= 10^4`

- `tokens[i]` is either an operator: `"+"`, `"-"`, `"*"`, or `"/"`, or an integer in the range `[-200, 200]`.

Topics: Array, Math, Stack

---

Approach

Stack

Use a stack (LIFO) to track elements that need future processing. Process elements when a "trigger" condition is met (e.g., finding a smaller/larger element). Monotonic stack maintains elements in sorted order for next greater/smaller element problems.

When to use

Matching brackets, next greater element, evaluating expressions, backtracking history.

Mathematical

Look for mathematical patterns or formulas. Consider: modular arithmetic, GCD/LCM, prime factorization, combinatorics, or geometric properties.

When to use

Problems with clear mathematical structure, counting, number properties.

---

Solutions

Solution 1: C# (Best: 100 ms)

Metric	Value
Runtime	100 ms
Memory	24.8 MB
Date	2019-12-28

Solution

public class Solution {
    public int EvalRPN(string[] tokens) {
       Stack<int> vals = new Stack<int>();
    foreach (var token in tokens)
    {
        if(token == "+" ||token == "-" ||token == "*" ||token == "/" )
        {
            var num2 = vals.Pop();
            var num1 = vals.Pop();
            if(token == "+")
            {
                vals.Push(num1+num2);
            }
            else if(token == "-")
            {
                vals.Push(num1 - num2);
            }
            else if (token == "*")
            {
                vals.Push(num1 * num2);
            }
            else if (token == "/")
            {
                vals.Push(num1 / num2);
            }
        }
        else
        {
            vals.Push(Int32.Parse(token));
        }
    }
    
    
    return vals.Peek();
}
}

---

Complexity Analysis

Approach	Time	Space
Stack	$O(n)$	$O(n)$

---

Interview Tips

Key Points

• Discuss the brute force approach first, then optimize. Explain your thought process.
• Think about what triggers a pop: is it finding a match, or finding a smaller/larger element?