# Evaluate Reverse Polish Notation
**Difficulty:** MEDIUM
[External](https://leetcode.com/problems/evaluate-reverse-polish-notation)
Canonical: https://scaleengineer.com/dsa/problems/evaluate-reverse-polish-notation
**Patterns:** [Math](https://scaleengineer.com/dsa/patterns/math)
**Data structures:** Array, Stack
**Companies:** [LinkedIn](https://scaleengineer.com/companies/linkedin), [Yandex](https://scaleengineer.com/companies/yandex), [Citadel](https://scaleengineer.com/companies/citadel), [Odoo](https://scaleengineer.com/companies/odoo), [Grammarly](https://scaleengineer.com/companies/grammarly), [Attentive](https://scaleengineer.com/companies/attentive), [Apollo.io](https://scaleengineer.com/companies/apollo.io), [Canonical](https://scaleengineer.com/companies/canonical), [Zendesk](https://scaleengineer.com/companies/zendesk)
---
## Problem
You are given an array of strings `tokens` that represents an arithmetic expression in a [Reverse Polish Notation](http://en.wikipedia.org/wiki/Reverse%5FPolish%5Fnotation).

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 <= 104`
* `tokens[i]` is either an operator: `"+"`, `"-"`, `"*"`, or `"/"`, or an integer in the range `[-200, 200]`.

# Approaches
## In-place List Reduction
This approach involves repeatedly finding the first operator in the list of tokens, evaluating it with its two preceding operands, and replacing the three tokens with the single result. This process continues until only one token (the final result) remains in the list.
**Time:** O(N^2) · **Space:** O(N)
**Pros:** Does not require an explicit auxiliary data structure like a stack.; The reduction process is conceptually straightforward.
**Cons:** Highly inefficient with a time complexity of O(N^2).; Modifying a list while iterating over it is complex and can be error-prone.; The repeated scanning of the list from the beginning after each reduction is very slow.
### Explanation
The core idea is to simulate the reduction of the expression in-place within a list. We start by converting the input array into a dynamic list structure like an `ArrayList` to allow for element removal.

*   Initialize a loop that runs as long as the expression has not been fully evaluated (i.e., the list size is greater than 1).
*   Inside the loop, we search for the first occurrence of an operator.
*   Once an operator is found at index `i`, we know its operands must be the two preceding elements at `i-2` and `i-1`.
*   We parse these operands, perform the calculation, and then update the list. This involves replacing the element at `i-2` with the result and removing the elements at `i-1` and `i`.
*   Because the list's structure has changed, we reset our search pointer to the beginning and repeat the process.
*   The loop terminates when the list contains a single element, which is the final answer.

```java
import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;

class Solution {
    public int evalRPN(String[] tokens) {
        List<String> tokenList = new ArrayList<>(Arrays.asList(tokens));
        while (tokenList.size() > 1) {
            int i = 0;
            // Find the first operator
            while (!isOperator(tokenList.get(i))) {
                i++;
            }
            
            // Operands are at i-2 and i-1
            int b = Integer.parseInt(tokenList.get(i - 1));
            int a = Integer.parseInt(tokenList.get(i - 2));
            int result = 0;
            
            switch (tokenList.get(i)) {
                case "+": result = a + b; break;
                case "-": result = a - b; break;
                case "*": result = a * b; break;
                case "/": result = a / b; break;
            }
            
            // Replace the three tokens with the result
            tokenList.set(i - 2, String.valueOf(result));
            tokenList.remove(i);
            tokenList.remove(i - 1);
        }
        return Integer.parseInt(tokenList.get(0));
    }

    private boolean isOperator(String s) {
        return s.equals("+") || s.equals("-") || s.equals("*") || s.equals("/");
    }
}
```
### Algorithm
1. Convert the input `String[]` to a mutable list, like `ArrayList<String>`.
2. Loop until the list has only one element:
    - Iterate through the list to find the first operator at index `i`.
    - The operands are at indices `i-2` and `i-1`.
    - Perform the operation.
    - Replace the three elements (operand, operand, operator) with the single result.
    - Restart the search from the beginning of the modified list.
3. When the loop terminates, the list will have one element. Parse it to an integer and return.

## Recursive Evaluation
This approach treats the RPN expression as a post-order traversal of an expression tree. We can evaluate it recursively. The last token is the root (the main operator), and its children are the results of recursively evaluating the preceding sub-expressions.
**Time:** O(N) · **Space:** O(N)
**Pros:** An elegant solution that directly maps to the recursive definition of an expression tree.; The code can be very concise.
**Cons:** Can cause a `StackOverflowError` for very long expressions due to deep recursion.; Has higher constant overhead due to function calls compared to an iterative solution.; Managing the index state across recursive calls can be less intuitive than a simple loop.
### Explanation
An RPN expression can be defined recursively. The expression is either a number, or it is two RPN expressions followed by an operator. This structure lends itself to a recursive solution. We can process the tokens from right to left.

*   We use a global index, initialized to the last index of the token array.
*   A recursive function `evaluate()` is called.
*   Inside `evaluate()`, we read the token at the current global index and then decrement the index.
*   If the token is an operator, we know it needs two operands. Since we are processing from right to left, the next token to be processed will be the end of the right operand's sub-expression. So, we make a recursive call to `evaluate()` to get the right operand's value. After that returns, we make another recursive call to get the left operand's value.
*   If the token is a number, it's a base case; we parse it and return the value.
*   The result of the operation is then returned up the call stack.

```java
class Solution {
    int index;
    
    public int evalRPN(String[] tokens) {
        index = tokens.length - 1;
        return evaluate(tokens);
    }
    
    private int evaluate(String[] tokens) {
        String token = tokens[index--];
        if (isOperator(token)) {
            int b = evaluate(tokens); // Evaluate right operand first
            int a = evaluate(tokens); // Evaluate left operand
            switch (token) {
                case "+": return a + b;
                case "-": return a - b;
                case "*": return a * b;
                case "/": return a / b;
            }
        }
        return Integer.parseInt(token);
    }

    private boolean isOperator(String s) {
        return s.equals("+") || s.equals("-") || s.equals("*") || s.equals("/");
    }
}
```
### Algorithm
1. The main function initiates the recursion starting from the end of the `tokens` array.
2. A recursive helper function is defined. A global or member variable is used to track the current token index, starting from the last one.
3. **Base Case:** If the token at the current index is a number, parse it and return the value.
4. **Recursive Step:** If the token is an operator:
    - Decrement the index and recursively call the helper to evaluate the right operand.
    - Decrement the index again and recursively call the helper to evaluate the left operand.
    - Perform the operation on the two results.
    - Return the final result.

## Stack-based Evaluation
This is the canonical and most efficient method for evaluating Reverse Polish Notation. It uses a stack to hold operands. When an operator is encountered, it pops the necessary operands, performs the calculation, and pushes the result back onto the stack.
**Time:** O(N) · **Space:** O(N)
**Pros:** Optimal time complexity of O(N).; Simple, intuitive, and easy to implement correctly.; Iterative approach avoids recursion depth limits and potential stack overflow errors.; It is the standard and most widely recognized algorithm for this problem.
**Cons:** Requires O(N) auxiliary space for the stack.
### Explanation
Reverse Polish Notation is perfectly suited for evaluation using a stack. The 'last-in, first-out' (LIFO) nature of a stack allows us to store operands and retrieve the most recent ones when an operator appears.

The algorithm proceeds as follows:
*   We iterate through the tokens one by one.
*   If the current token is a number, we push it onto our stack of integers.
*   If the current token is an operator, we know that the top two elements on the stack must be the operands for this operation. We pop them, being careful about the order (the first element popped is the right-hand operand, the second is the left-hand operand).
*   We then perform the calculation and push the single numerical result back onto the stack.
*   By the end of the token list, the stack will hold a single number: the final result of the entire expression.

```java
import java.util.Stack;

class Solution {
    public int evalRPN(String[] tokens) {
        Stack<Integer> stack = new Stack<>();
        for (String token : tokens) {
            switch (token) {
                case "+":
                    stack.push(stack.pop() + stack.pop());
                    break;
                case "-":
                    int b = stack.pop();
                    int a = stack.pop();
                    stack.push(a - b);
                    break;
                case "*":
                    stack.push(stack.pop() * stack.pop());
                    break;
                case "/":
                    int divisor = stack.pop();
                    int dividend = stack.pop();
                    stack.push(dividend / divisor);
                    break;
                default:
                    stack.push(Integer.parseInt(token));
            }
        }
        return stack.pop();
    }
}
```
### Algorithm
1. Initialize an empty stack of integers.
2. Iterate through each token in the input array from left to right.
3. If the token is a number, convert it to an integer and push it onto the stack.
4. If the token is an operator (`+`, `-`, `*`, `/`):
    - Pop the top element from the stack (second operand `b`).
    - Pop the new top element from the stack (first operand `a`).
    - Perform the operation `a operator b`.
    - Push the result back onto the stack.
5. After the loop, the stack will contain one element. Pop and return this final result.

# Solutions
### CSharp

```csharp
using System.Collections.Generic ; public class Solution { public int EvalRPN ( string [] tokens ) { var stack = new Stack < int >(); foreach ( var token in tokens ) { switch ( token ) { case "+" : stack . Push ( stack . Pop () + stack . Pop ()); break ; case "-" : stack . Push (- stack . Pop () + stack . Pop ()); break ; case "*" : stack . Push ( stack . Pop () * stack . Pop ()); break ; case "/" : var right = stack . Pop (); stack . Push ( stack . Pop () / right ); break ; default : stack . Push ( int . Parse ( token )); break ; } } return stack . Pop (); } }
```

### Java

```java
class Solution {
public
  int evalRPN(String[] tokens) {
    Deque<Integer> stk = new ArrayDeque<>();
    for (String t : tokens) {
      if (t.length() > 1 || Character.isDigit(t.charAt(0))) {
        stk.push(Integer.parseInt(t));
      } else {
        int y = stk.pop();
        int x = stk.pop();
        switch (t) {
        case "+":
          stk.push(x + y);
          break;
        case "-":
          stk.push(x - y);
          break;
        case "*":
          stk.push(x * y);
          break;
        default:
          stk.push(x / y);
          break;
        }
      }
    }
    return stk.pop();
  }
}

```

### CPP

```cpp
class Solution {
public:
  int evalRPN(vector<string> &tokens) {
    stack<int> stk;
    for (auto &t : tokens) {
      if (t.size() > 1 || isdigit(t[0])) {
        stk.push(stoi(t));
      } else {
        int y = stk.top();
        stk.pop();
        int x = stk.top();
        stk.pop();
        if (t[0] == '+')
          stk.push(x + y);
        else if (t[0] == '-')
          stk.push(x - y);
        else if (t[0] == '*')
          stk.push(x * y);
        else
          stk.push(x / y);
      }
    }
    return stk.top();
  }
};

```

### Python

```python
class Solution:
    def evalRPN(self, tokens: List[str]) -> int: nums = [] for t in tokens: if len(t) > 1 or t . isdigit(): nums . append(int(t)) else: if t == "+": nums[- 2] += nums[- 1] elif t == "-": nums[- 2] -= nums[- 1] elif t == "*": nums[- 2] *= nums[- 1] else: nums[- 2] = int(nums[- 2] / nums[- 1]) nums . pop() return nums[0]

```