题解 | #表达式求值#

#include <cctype>
class Solution {
public:
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     * 返回表达式的值
     * @param s string字符串 待计算的表达式
     * @return int整型
     */
    unordered_map<char,int> map;
    void calu(stack<int>&nums,stack<char> &ops){
        int a=nums.top();nums.pop();
        int b=nums.top();nums.pop();
        char op=ops.top();ops.pop();
        if(op=='+')
            nums.push(a+b);
        else if(op=='-')
            nums.push(b-a);
        else
            nums.push(b*a);
    }
    void replace(string &s){
        int pos=s.find(" ");
        while(pos!=-1){
            s.replace(pos,1,"");
            pos=s.find(" ");
        }
    }
    int solve(string s) {
        // write code here
        map['+']=1;
        map['-']=1;
        map['*']=2;
        replace(s);
        int n=s.size();
        stack<int> nums;
        stack<char> ops;
        nums.push(0);
        for(int i=0;i<n;i++){
            char c=s[i];
            if(c=='('){
                ops.push(c);
            }
            else if(c==')'){
                while(!ops.empty()&&ops.top()!='('){
                    calu(nums,ops);
                }
                if(!ops.empty())
                    ops.pop();
            }
            else if(isdigit(c)){
                int sum=0;
                while(i<n&&isdigit(s[i])){
                    sum=sum*10+(s[i]-'0');
                    i++;
                }
                i--;
                nums.push(sum);
            }
            else{
                if(i>0&&s[i-1]=='(')
                    nums.push(0);
                while(!ops.empty()&&ops.top()!='('&&(map[c]<=map[ops.top()])){
                    calu(nums,ops);
                }
                ops.push(c);
            }
        }
        while(!ops.empty()){
            calu(nums,ops);
        }
        return nums.top();
    }
};