【3.20】LeetCode每日一题· 逆波兰表达式求值

2021年03月20日 12时23分

标签： LeetCode 栈

## 题目描述
根据[逆波兰表示法](https://baike.baidu.com/item/%E9%80%86%E6%B3%A2%E5%85%B0%E5%BC%8F/128437)，求表达式的值。

有效的算符包括`+`、`-`、`*`、`/` 。每个运算对象可以是整数，也可以是另一个逆波兰表达式。

说明：

* 整数除法只保留整数部分。
* 给定逆波兰表达式总是有效的。换句话说，表达式总会得出有效数值且不存在除数为 0 的情况。

#### 示例1
```
输入：tokens = ["2","1","+","3","*"]
输出：9
解释：该算式转化为常见的中缀算术表达式为：((2 + 1) * 3) = 9
```

#### 示例2
```
输入：tokens = ["4","13","5","/","+"]
输出：6
解释：该算式转化为常见的中缀算术表达式为：(4 + (13 / 5)) = 6
```

#### 示例3
```
输入：tokens = ["10","6","9","3","+","-11","*","/","*","17","+","5","+"]
输出：22
解释：
该算式转化为常见的中缀算术表达式为：
  ((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
```

#### 提示
```
1 <= tokens.length <= 10^4
tokens[i] 要么是一个算符（"+"、"-"、"*" 或 "/"），要么是一个在范围 [-200, 200] 内的整数
```

#### 逆波兰表达式
逆波兰表达式是一种后缀表达式，所谓后缀就是指算符写在后面。

平常使用的算式则是一种中缀表达式，如`( 1 + 2 ) * ( 3 + 4 )` 。
该算式的逆波兰表达式写法为`( ( 1 2 + ) ( 3 4 + ) * )`。
逆波兰表达式主要有以下两个优点：

去掉括号后表达式无歧义，上式即便写成`1 2 + 3 4 + *`也可以依据次序计算出正确结果。
适合用栈操作运算：遇到数字则入栈；遇到算符则取出栈顶两个数字进行计算，并将结果压入栈中。

#### 来源
> 来源：力扣（LeetCode）
> 链接：[题目链接](https://leetcode-cn.com/problems/evaluate-reverse-polish-notation/ "题目链接")

## 解题思路
由于逆波兰表达式去掉括号后表达式无歧义，不存在计算顺序不一致导致的结果不一致，因此只需要**维护一个数字栈**。具体步骤如下：
1. 遇到数字则入栈；
2. 遇到算符则取出栈顶两个数字计算，并将结果压入栈中。

由于给出的数字可能是多位数或负数，因此需要编写一个函数专门将字符串转化为数字（代码中的`getNum`方法）。

## 代码
```cpp
class Solution {
public:
    inline bool isNum(const char& c){
        return c >= '0' && c <= '9';
    }
    bool getNum(const string& token, int& num){
        // 是操作符
        if(token.length() == 1 && !isNum(token[0])){
            num = -0x3f3f3f3f;
            return false;
        }else{
            int sign = 1, i = 0;
            num = 0;
            if(token[0] == '-'){
                sign = -1;
                i++;
            }
            while(i < token.length()){
                num *= 10;
                num += token[i] - '0';
                i++;
            }
            num *= sign;
            return true;
        }
    }

int cal(const int& num1, const int& num2, const string& curr){
        if(curr == "+"){
            return num1 + num2;
        }else if(curr == "-"){
            return num1 - num2;
        }else if(curr == "*"){
            return num1 * num2;
        }else{
            return num1 / num2;
        }
    }

int evalRPN(vector<string>& tokens) {
        stack<int> nums;
        int temp, num1, num2;
        for(string& token: tokens){
            bool isNum = getNum(token, temp);
            if(isNum){
                nums.push(temp);
            }else{
                num2 = nums.top(); nums.pop();
                num1 = nums.top(); nums.pop();
                nums.push(cal(num1, num2, token));
            }
        }

return nums.top();
    }
};
```

### 用时和内存
> 执行用时：8 ms，在所有 C++提交中击败了95.72%的用户
> 内存消耗：11.6 MB，在所有 C++提交中击败了47.08%的用户

所有评论

暂无评论

新增评论

邮箱

邮箱仅作验证使用

图形验证码

邮箱验证码

目录

【3.20】LeetCode每日一题· 逆波兰表达式求值

所有评论

暂无评论

新增评论