题解 | 表达式求值

C++主要是参考官方题解写的，递归还是有点懵

class Solution {
  public:
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     * 返回表达式的值
     * @param s string字符串 待计算的表达式
     * @return int整型
     */
    vector<int> cal(string s, int idx) {
        stack<int> num;
        char op = '+';
        int a = 0;
        int i;
        for (i=idx; i<s.size(); i++) {
            if (isdigit(s[i])) {
                int j;
                for (j = i; j < s.size() && isdigit(s[j]); j++);
                a = stoi(s.substr(i, j - i));
                i = j; // 数字后面接的符号
            }
            if (s[i]=='(') {
                vector<int> r = cal(s, i+1);
                a = r[0];
                i = r[1];
                // cout << a << ' ' << i << endl;
                if (i != s.size()-1) continue; // 不能少
            }
            switch (op) {
                case '+':
                    num.push(a); break;
                case '-':
                    num.push(-a); break;
                case '*':
                    a *= num.top(); num.pop();
                    num.push(a); break;
            }
            if (s[i]==')') break;
            else op = s[i];
        }
        int sum=0;
        while (!num.empty()) {
            // cout << num.top() << endl;
            sum += num.top();
            num.pop();
        }
        return vector<int> {sum, i};
    }

    int solve(string s) {
        // write code here
        // 要求：1. 运算符号有优先级 * > +- ；2. 支持括号
        // 遍历字符串：遇到
        // 数字 - 将连续数字字符转为 int
        // 运算符 - 若为 + 则数字正常入栈，若为 - 则相反数入栈，
        //        - 若为 * 则栈顶出栈、与栈顶相乘后的结果入栈
        // 左括号 - 进入子递归，遇右括号，返回 int 入栈；
        return cal(s, 0)[0];
    }
};