题解 | #表达式求值#

题目描述：
输入一个表达式（用字符串表示），求这个表达式的值。
保证字符串中的有效字符包括[‘0’-‘9’],‘+’,‘-’, ‘*’,‘/’ ,‘(’， ‘)’,‘[’, ‘]’,‘{’ ,‘}’。且表达式一定合法。

解题思路：使用两个stack，一个存放数字nums，一个存放操作符ops。
解题步骤如下：
1、先将输入的string预处理成string数组（数组中存放的字符串，要么是符号，要么是数字），注意对于"-"既可能是负号也可能是减号，需要注意区分。
2、遍历step1生成的字符串数组，根据每次处理的string str，分情况讨论
3、str若是数字，直接push进nums
4、str若是(,直接push进ops
5、str若是),将ops一直出栈运算，直到ops栈顶是左括号。
6、str若是*，直接ops入栈。因为成人乘法前面可以接任何运算，倒序运算的时候不会影响结果。
7、str若是/，需要将前面的连除先运算了，比如8/4/2，必须先把第一个除法计算掉。
7、str若是+，需要将前面的乘除、减法运算掉
8、str若是-，需要将前面的乘除、减法运算掉
9、将string数组遍历结束之后，ops里面可能还有一些运算符。最后需要将ops里面所有的操作符依次弹出计算，最后nums只剩一个数字，即为最终结果。

实现细节原理需要注意：
1、一个符号入栈ops的前面是，和前面的运算相连之后，倒序运算也不会影响结果。
2、因为此题要求输入的字符串一定合法，所以省去了异常判断。但如果不能保证输入字符串一定合法，则代码中需要注意异常判断，如pop前判断非空。除法前判断除数非0.

献上粗糙的AC代码

using namespace std;
#include<iostream>
#include<string>
#include<vector>
#include<stack>
//将字符串分解为数字、符号
vector<string> split(string s){
    vector<string> res;
    while(s.size()){
        char ch=s[0];
        if(ch=='('||ch=='{'||ch=='['){
            res.push_back("(");
            s.replace(0,1,"");
        }else if(ch==')'||ch==']'||ch=='}'){
            res.push_back(")");
            s.replace(0,1,"");
        }else if(ch=='*'||ch=='/'||ch=='+'){
            res.push_back(s.substr(0,1));
            s.replace(0,1,"");
        }else if(ch=='-'){
            if(res.size()==0||res[res.size()-1]=="("){
                //如果是开头或者前面是括号，则是负号
                int len=1;
                while(len<s.size()&&(s[len]>='0'&&s[len]<='9'))
                    len++;
                res.push_back(s.substr(0,len));
                s.replace(0,len,"");
            }else{//仅仅是一个减号
                res.push_back("-");
                s.replace(0,1,"");
            }
        }else{//数字
            int len=0;
            while(len<s.size()&&(s[len]>='0'&&s[len]<='9'))
                len++;
            res.push_back(s.substr(0,len));
            s.replace(0,len,"");
        }
    }
    return res;
}
//取出并弹出两个操作数
vector<int> twoNum(stack<int>& nums){
    int b=nums.top();
    nums.pop();
    int a=nums.top();
    nums.pop();
    return {a,b};
}
char takeOp(stack<char>& ops){
    char op=ops.top();
    ops.pop();
    return op;
}
int solve(string s){
    vector<string> ss=split(s);
    //for(string x:ss)cout<<x<<"  ";  cout<<"\n";
    stack<int> nums;
    stack<char> ops;
    for(string str:ss){
        if(str=="(")ops.push('(');//左括号直接入符号栈
        else if(str==")"){//进行运算，直到符号栈遇到一个左括号
            while(ops.top()!='('){
                vector<int> ab=twoNum(nums);
                char op=takeOp(ops);
                int c=0;
                if(op=='+')c=ab[0]+ab[1];
                else if(op=='-')c=ab[0]-ab[1];
                else if(op=='*')c=ab[0]*ab[1];
                else c=ab[0]/ab[1];
                nums.push(c);
                //cout<<ab[0]<<op<<ab[1]<<"="<<c<<"\n";
            }
            ops.pop();//将那个左括号弹出
        }else if(str=="+"||str=="-"){
            //加号前面只能保留加号，遇到高优先级乘除、以及减法，都需要先把前面的计算掉
            while(ops.size()&&(ops.top()=='*'||ops.top()=='/'||ops.top()=='-')){
                vector<int> ab=twoNum(nums);
                char op=takeOp(ops);
                int c=0;
                if(op=='*')c=ab[0]*ab[1];
                else if(op=='/') c=ab[0]/ab[1];
                else c=ab[0]-ab[1];
                nums.push(c);
                //cout<<ab[0]<<op<<ab[1]<<"="<<c<<"\n";
            }
            if(str=="+")ops.push('+');
            else ops.push('-');
        }
        else if(str=="*")ops.push('*');
        else if(str=="/"){
            //除法前面不可以保留除号，因为不能连除。其他加减乘法均可以
            if(ops.size()&&ops.top()=='/'){
                ops.pop();
                vector<int> ab=twoNum(nums);
                int c=ab[0]/ab[1];
                nums.push(c);
                //cout<<ab[0]<<"/"<<ab[1]<<"="<<c<<"\n";
            }
            ops.push('/');
        }else nums.push(std::stoi(str));//数字直接入栈
    }
    while(ops.size()){//将符号栈运算清空
        vector<int> ab=twoNum(nums);
        char op=takeOp(ops);
        int c=0;
        if(op=='+')c=ab[0]+ab[1];
        else if(op=='-')c=ab[0]-ab[1];
        else if(op=='*')c=ab[0]*ab[1];
        else c=ab[0]/ab[1];
        nums.push(c);
        //cout<<ab[0]<<op<<ab[1]<<"="<<c<<"\n";
    }
    //cout<<"-----------\n"<<nums.top()<<"\n";
    return nums.top();
}
int main(){
    string s;
    cin>>s;
    cout<<solve(s);
    return 0;
}