题解 | 表达式求值

class Solution {
public:
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     * 返回表达式的值
     * @param s string字符串 待计算的表达式
     * @return int整型
     */
    map<char,int> mf={
        {'+',1},
        {'-',1},
        {'*',2},
    };
    void calc(stack<int> &msnum,stack<char> &ms){//注意要引用，不要拷贝赋值会死循环
        if(ms.empty()||msnum.empty()||msnum.size()<2) return;
        int x1=msnum.top();msnum.pop();
        int x2=msnum.top(); msnum.pop();
        int x3=0;
        switch (ms.top()) {
            case '+':
                x3=x2+x1;
                break;
            case '-':
                x3=x2-x1;
                break;
            case '*':
                x3=x2*x1;
                break;
            default:
                break;
        }
        ms.pop();
        msnum.push(x3);
    }
    int solve(string s) {
        // write code here
        //优先级 （） * +-
        stack<char>ms;
        stack<int>msnum;
        //入栈
        string num="";
        for(int i=0;i<s.length();i++){
            if('0'<=s[i]&&s[i]<='9'){//处理数字
                num+=s[i];
                if(i+1==s.length()||s[i+1]<'0'||s[i]>'9'){
                    msnum.push(stoi(num));
                    num="";
                } 
            }
            else{
                //处理符号
                if(s[i]=='('){
                    ms.push(s[i]);
                }
                else if(s[i]==')'){
                    while(!ms.empty()){
                        if(ms.top()!='('){
                            calc(msnum,ms);//计算
                        }
                        else {
                            ms.pop();//'('出栈
                            break;
                        }
                    }
                }
                else if(s[i]=='*'||s[i]=='+'||s[i]=='-'){
                    while(!ms.empty()){//栈内优先级高的先算
                        if(ms.top()=='('){
                            break;
                        }
                        if(mf.at(s[i])<=mf.at(ms.top())){
                            calc( msnum,  ms);
                        }else {
                            break;
                        }
                    }
                    ms.push(s[i]);
                }
                
            }
        }
        while(!ms.empty()){//栈内剩余算
            if(ms.top()=='(')
            {
                ms.pop();
            }
            else{
                calc( msnum,  ms);
            }
        }
        return msnum.top();
    }
};