> For the complete documentation index, see [llms.txt](https://jaywin.gitbook.io/leetcode/llms.txt). Markdown versions of documentation pages are available by appending `.md` to page URLs; this page is available as [Markdown](https://jaywin.gitbook.io/leetcode/solutions/0150-evaluate-reverse-polish-notation.md).

# 0150. Evaluate Reverse Polish Notation

<https://leetcode.com/problems/evaluate-reverse-polish-notation>

## Description

Evaluate the value of an arithmetic expression in [Reverse Polish Notation](http://en.wikipedia.org/wiki/Reverse_Polish_notation).

Valid operators are `+`, `-`, `*`, and `/`. Each operand may be an integer or another expression.

**Note** that division between two integers should truncate toward zero.

It is guaranteed that the given RPN expression is always valid. That means the expression would always evaluate to a result, and there will not be any division by zero operation.

**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]`.

## ac

```java
// basic knowledge, stack
class Solution {
    public int evalRPN(String[] tokens) {
        // edge cases
        // if (tokens.length == 0) return -1;

        // stack store number
        Stack<Integer> stack = new Stack<Integer>();

        // walk list
        for (int i = 0; i < tokens.length; i++) {
            int res = 1;
            if (tokens[i].equals("+") || tokens[i].equals("-") 
                || tokens[i].equals("*") || tokens[i].equals("/")) {
                int operand = stack.pop();
                int number = stack.pop();
                switch (tokens[i]){
                    case "+": 
                        res = number + operand;
                        break;
                    case "-":
                        res = number - operand;
                        break;
                    case "*":
                        res = number * operand;
                        break;
                    case "/":
                        res = number / operand;
                        break;
                }
            } else {
                res = Integer.parseInt(tokens[i]);
            }
            stack.push(res);
        }
        // return 
        return stack.pop();
    }
}
// walk list, if number push to stack, else pop 2 numbers from stack -> calculate -> push back to stack
// stack1: 4 13 5
```

wrap operation in a helper function.

```java
class Solution {
    public int evalRPN(String[] tokens) {
        // edge cases
        if (tokens == null || tokens.length == 0) return 0;

        Stack<Integer> stack = new Stack<>();
        for (String s : tokens) {
            if (s.equals("+") || s.equals("-") || s.equals("*") || s.equals("/")) {
                int val2 = stack.pop();
                int val1 = stack.pop();
                stack.push(operate(val1, s, val2));
            } else {
                stack.push(Integer.parseInt(s));
            }
        }

        return stack.pop();
    }

    private int operate(int val1, String oper, int val2) {
        int res = 0;
        if (oper.equals("+")) res = val1 + val2;
        else if (oper.equals("-")) res = val1 - val2;
        else if (oper.equals("*")) res = val1 * val2;
        else if (oper.equals("/")) res = val1 / val2;
        return res;
    }
}
```