# 150J. Evaluate Reverse Polish Notation

difficulty: Medium

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.

&#x20;

**Example 1:**

<pre><code><strong>Input: tokens = ["2","1","+","3","*"]
</strong><strong>Output: 9
</strong><strong>Explanation: ((2 + 1) * 3) = 9
</strong></code></pre>

**Example 2:**

<pre><code><strong>Input: tokens = ["4","13","5","/","+"]
</strong><strong>Output: 6
</strong><strong>Explanation: (4 + (13 / 5)) = 6
</strong></code></pre>

**Example 3:**

<pre><code><strong>Input: tokens = ["10","6","9","3","+","-11","*","/","*","17","+","5","+"]
</strong><strong>Output: 22
</strong><strong>Explanation: ((10 * (6 / ((9 + 3) * -11))) + 17) + 5
</strong>= ((10 * (6 / (12 * -11))) + 17) + 5
= ((10 * (6 / -132)) + 17) + 5
= ((10 * 0) + 17) + 5
= (0 + 17) + 5
= 17 + 5
= 22
</code></pre>

&#x20;

**Constraints:**

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

## Method One

```Java
class Solution {
    public int evalRPN(String[] tokens) {
        ArrayDeque<Integer> values = new ArrayDeque<>();
        for(String str : tokens){
            if(str.equals("+")){
                values.push(values.pop() + values.pop());
            }else if(str.equals("-")){
                values.push(- values.pop() + values.pop());
            }else if(str.equals("*")){
                values.push(values.pop() * values.pop());
            }else if(str.equals("/")){
                int a = values.pop();
                int b = values.pop();
                values.push(b/a);
            }else{
                values.push(Integer.valueOf(str));
            }
        }
        return values.pop();
    }
}
​
```

202309写的，很多年过去了这也太巧了吧，和之前的几乎一样。

```java
class Solution {
    public int evalRPN(String[] tokens) {
        ArrayDeque<Integer> stack = new ArrayDeque<>();
        for (String token : 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 "/":
                    int b = stack.pop();
                    int a = stack.pop();
                    stack.push(a / b);
                    break;
                default:
                    stack.push(Integer.valueOf(token));
            }
        }
        return stack.pop();
    }
}

```
