# LeetCode – Evaluate Reverse Polish Notation
Date: 2019-08-04


#### **题目：**

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

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

**Note:**

- Division between two integers should truncate toward zero.
- The given RPN expression is always valid. That means the expression would always evaluate to a result and there won't be any divide by zero operation.

**Example 1:**

**Input:**

```
 ["2", "1", "+", "3", "*"]

```

**Output:**

```
 9

```

**Explanation:**

```
 ((2 + 1) * 3) = 9

```

**Example 2:**

**Input:**

```
 ["4", "13", "5", "/", "+"]

```

**Output:**

```
 6

```

**Explanation:**

```
 (4 + (13 / 5)) = 6

```

**Example 3:**

**Input:**

```
 ["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
```

#### **解题：**

          [**逆波兰表示法**](https://zh.wikipedia.org/wiki/%E9%80%86%E6%B3%A2%E5%85%B0%E8%A1%A8%E7%A4%BA%E6%B3%95)（**Reverse Polish notation**，**RPN**，或**逆波兰记法**），将操作数放到操作符前的一种数学表达式方式，也被称作后缀表示法。

         1. **使用栈：** 针对本题由于操作符指定为二元运算，具体操作有流程有所简化， 遇到操作数入栈， 遇到操作符，将两个操作数出栈，进行运算，将结果再次入栈，以此类推，知道完成所有数组的遍历，栈顶指针即为结果。

#### **实现：**

```
class Solution {
public:
    int evalRPN(vector<string>& tokens) {
        stack<int> ss;
        if (tokens.size() == 1) { 
            return stoi(tokens[0]);
        } 
        for (auto s:tokens){            
            if (s !="+" && s !="-" && s!="*" && s!="/" ){
                ss.push(stoi(s));
            }
            else{
                int num2 = ss.top();
                ss.pop();
                int num1 = ss.top();
                ss.pop();
                
                int result;
                switch (s[0]){
                    case '+':
                        result = num1+num2;
                        break;
                    case '-':
                        result = num1-num2;
                        break;
                    case '*':
                        result = num1*num2;
                        break;
                    case '/':
                        if (num2 == 0){
                            result = 0;
                        }else {
                            result = num1/num2;
                        }
                        break;
                    default:
                        result = 0;
                        break;
                }
               
                ss.push(result);
            }
        }
             
        return ss.top();
    }
};
```

             2. 递归**：** 从数组末尾开始调用，如果遇到操作符，继续向前递归调用，找到对应的两个数字后，进行运算返回结果； 如果遇到数字，直接返回。

#### 实现：

```
int evalRPN(vector<string>& tokens) {
    auto t = tokens.back(); tokens.pop_back();
    if (isdigit(t.back())) return stoi(t);
    int n2 = evalRPN(tokens), n1 = evalRPN(tokens);
    return t[0] == '+' ? n1 + n2 : t[0] == '-' ? n1 - n2 : t[0] == '*' ? n1 * n2 : n1 / n2;
}
```

#### 参考：

[\[LeetCode\] Evaluate Reverse Polish Notation 计算逆波兰表达式](https://www.cnblogs.com/grandyang/p/4247718.html)

[Evaluate Reverse Polish Notation - C++ 4 lines](https://leetcode.com/explore/learn/card/queue-stack/230/usage-stack/1394/discuss/341310/C++-4-lines)