题解 | #表达式求值 双栈+递归，非常简洁易懂#

双栈+递归

双栈：一个栈用于存放数字，一个用于存放符号

递归：括号内表达式求值作为返回值，减少处理括号时边界条件的处理难度

class Solution {
public:
    unordered_map<char, int> oper_prio{
    {'+', 1},
    {'-', 1},
    {'*', 2},
    {'/', 2},
    {'%', 2},
    {'^', 3}
    };

    int func(string &s, int &idx) {
        stack<int> nums;
        stack<char> opers;
        if (s[idx] == '+') {
            nums.push(0);
            opers.push('+');
            ++idx;
        } else if (s[idx] == '-') {
            nums.push(0);
            opers.push('-');
            ++idx;
        }

        int num = 0;
        while(idx < s.length()) {
            // 1. 读取数字
            if (isdigit(s[idx])) {
                while (isdigit(s[idx])) {
                    num = num * 10 + s[idx] - '0';
                    ++idx;
                }
                nums.push(num);
                num = 0;    
                --idx;      // 恢复指针
            }
            // 2.读取到'('
            else if (s[idx] == '(') nums.push(func(s, ++idx));
            // 3.读取到')'
            else if (s[idx] == ')') break;
            // 4. 读取到 Other operators
            else {
                while (!opers.empty() && oper_prio[opers.top()] >= oper_prio[s[idx]]) {
                    calc(nums, opers);
                }
                opers.push(s[idx]);
            }

            ++idx;
        }
        
        while (!opers.empty()) {
            calc(nums, opers);
        }

        return nums.top();
    }

    static void calc(stack<int> &nums, stack<char> &opers) {
        long long num2 = nums.top(); nums.pop();
        long long num1 = nums.top(); nums.pop();
        char oper = opers.top(); opers.pop();
        long long res;

        switch(oper) {
            case '+' : res = num1 + num2; break;
            case '-' : res = num1 - num2; break;
            case '*' : res = num1 * num2; break;
            case '/' : res = num1 / num2; break;
            case '%' : res = num1 % num2; break;
            case '^' : res = pow(num1, num2); break;
        }
        
        nums.push(res);
    }

    int solve(string s) {
        // write code here
        int i = 0;
        return func(s, i);
    }
};