题解 | #表达式求值#

#include<regex>
class Solution {
public:
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     * 返回表达式的值
     * @param s string字符串 待计算的表达式
     * @return int整型
     */
    // set operator priority
    map<char,int> mymap;
    int solve(string s) {
        // write code here
        mymap['-'] = 1;
        mymap['+'] = 1;
        mymap['*'] = 2;
        mymap['/'] = 2;
        mymap['%'] = 2;
        mymap['^'] = 3;

        std::regex r("\\s+");
        s = std::regex_replace(s,r,"");
        deque<int> nums;
        nums.push_back(0);
        deque<char> ops;

        for (int i=0;i<s.size();i++){
            char c = s[i];
            if (c=='('){
                ops.push_back(c);
            }else if (c==')'){
                while(!ops.empty()){
                    if (ops.back()!='('){
                        calculate(nums,ops);
                    }else{
                        ops.pop_back();
                        break;
                    }
                }
            }else {
                // number
                if (c>'0'&&c<'9'){
                    int val = 0;
                    int j = i;
                    while(j<s.size()&&(s[j]>='0'&&s[j]<'9')) val = val * 10 + (s[j++] - '0');
                    nums.push_back(val);
                    i = j - 1;
                }else{
                    // operator
                    // handle signed number
                    if (i>0&&(s[i-1]=='+'||s[i-1]=='-')) nums.push_back(0);

                    while (!ops.empty()&&ops.back()!='('){
                        char prev = ops.back();
                        if (mymap[prev]>=mymap[c]){
                            calculate(nums,ops);
                        }else{
                            break;
                        }
                    }
                    ops.push_back(c);
                }
            }
        }
        while(!ops.empty()&&ops.back()!='(') {
            calculate(nums,ops);
        }
        return nums.back();
    }

    void calculate(deque<int>& nums, deque<char>& ops){
        if (nums.empty()|| nums.size()<2) return;
        if (ops.empty()) return;
        int b = nums.back();
        nums.pop_back();
        int a = nums.back();
        nums.pop_back();
        char op = ops.back();
        ops.pop_back();
        int ans = 0;
        if (op=='-') ans = a - b;
        else if (op=='+') ans = a + b;
        else if (op=='*') ans = a * b;
        else if (op=='/') ans = a / b;
        else if (op=='%') ans = a % b;
        else if (op=='^') ans = pow(a,b);
        nums.push_back(ans);
    }
};