leetcode 150 逆波兰表达式求值

- 日理万妓 2022-09-11 02:28 180阅读 0赞

## 前言 ##

题目：[150. 逆波兰表达式求值][150.]

参考题解：[逆波兰表达式求值-力扣官方题解][-]、[逆波兰表达式求值-代码随想录][- 1]

--------------------

## 提交代码 ##

> 逆波兰表达式主要有以下两个优点：
> 
>  *  去掉括号后表达式无歧义。
>  *  适合用栈操作运算：遇到数字则入栈；遇到算符则取出栈顶两个数字进行计算，并将结果压入栈中。

#include <stack>
    #include <vector>
    #include <string>
    #include <cctype>
    #include <iostream>
    #include <algorithm>
    
    using namespace std;
    
    
    class Solution {
    public:
        int calculator(int num1, int num2, char operation){
            int result;
            switch (operation){
                case '+':
                    result = num1+num2;
                    break;
                case '-':
                    result = num1-num2;
                    break;
                case '*':
                    result = num1*num2;
                    break;
                case '/':
                    result = num1/num2;
                    break;
                default:
                    // perror("not such operation\n");
                    exit(1);
            }
            return result;
        }
    
        int evalRPN(vector<string>& tokens) {
            // 默认输入合法
            stack<int> operand;
    
            for(string s : tokens){
                // all_of(s.begin(),s.end(),[](char c){return isdigit(c);});
                if(isdigit(s[0]) || (s[0]=='-'&&isdigit(s[1])))
                    operand.push(stoi(s));
                else{
                    int num2 = operand.top();
                    operand.pop();
                    int num1 = operand.top();
                    operand.pop();
                    operand.push(calculator(num1,num2,s[0]));
                }
            }
    
            return operand.top();
        }
    };
    
    int main(void){
        vector<string> tokens = {"10","6","9","3","+","-11","*","/","*","17","+","5","+"};
        Solution s;
        cout<<s.evalRPN(tokens);
    }

这道题目有些难以处理的地方，不在于逆波兰表达式本身，而在于：**判断字符串是否为数字；将字符串转换成数字**。

C++标准库并没有提供判断字符串是否为数字的函数。判断字符串是否为`int`类型。我在网上翻了翻，得到两种思路。

注：下面两种思路实现的代码，没有经过测试，可能存在逻辑bug。

第一种是，对非符号位，使用[isdigit][]逐个判断。

bool isNumber(const string& s){
        bool flag = false;
        if(s.empty())
            return false;
        if(isdigit(s[0]))
            flag = all_of(s.begin(),s.end(),[](char c){return isdigit(c););
        else if(s[0]=='-' && s.size()>1)
            flag = all_of(s.begin()+1,s.end(),[](char c){return isdigit(c););
        return flag;
    }

第二种是使用正则表达式。C++标准库提供了[正则表达式库][Link 1]

bool isNumber(cong string& s){
        // 正则表达式整理:https://zhuanlan.zhihu.com/p/30573054
        string numRuleStr{ "-?[0-9]" };
        regex re(numRuleStr);
        return regex_match(s,re);
    }

我倾向于使用**正则表达式**来进行判断，字符串是否为数字。因为判断基于规则，正则擅长于规则。若后期有缘，在某些开源库中看到`isNumber`的具体实现，我再单独整理一片blog。

至于，将字符串转换成数字，标准库中已提供函数，咱们可以不自己实现：[std::stoi, std::stol, std::stoll][std_stoi_ std_stol_ std_stoll]

[150.]: https://leetcode-cn.com/problems/evaluate-reverse-polish-notation/
[-]: https://leetcode-cn.com/problems/evaluate-reverse-polish-notation/solution/ni-bo-lan-biao-da-shi-qiu-zhi-by-leetcod-wue9/
[- 1]: https://leetcode-cn.com/problems/evaluate-reverse-polish-notation/solution/dai-ma-sui-xiang-lu-dai-ni-gao-ding-zhan-9jtu/
[isdigit]: https://zh.cppreference.com/w/cpp/header/cctype
[Link 1]: https://zh.cppreference.com/w/cpp/regex
[std_stoi_ std_stol_ std_stoll]: https://zh.cppreference.com/w/cpp/string/basic_string/stol