# LeetCode – Evaluate Reverse Polish Notation

#### 题目：

Evaluate the value of an arithmetic expression in 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```

#### 解题：

逆波兰表示法Reverse Polish notationRPN，或逆波兰记法），将操作数放到操作符前的一种数学表达式方式，也被称作后缀表示法。

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 计算逆波兰表达式