题解 | #表达式求值#

方法：栈+递归

该题的难点在于如何处理括号和运算符的优先级。

问题一，如何处理括号：当遇到括号‘（’，进行递归处理，直到括号被处理成数字；这样表达式就是数字之间的运算，而没有括号。

问题二，如何处理运算符的优先级：当遇到加法运算符的时候，将后面的数字直接压入栈中；

当遇到减法运算法时，将后面的数字取相反数压入栈中；

当遇到乘法运算符时，直接进行处理，并将乘法运算后的数字压入栈中。

这样栈中就只剩下一堆数字，将栈中的所有数字相加即可得到最终表达式的值。

时间复杂度：o(n)。

空间复杂度：o(n)。

class Solution {
  public:
    vector<int> function(string s, int index) {
        stack<int> stack;
        int num = 0;
	  	//初始化为+，因为最开始数字是正数
        char op = '+';
        int i;
        for (i = index; i < s.length(); i++) {
            //数字转换成int数字
            if (isdigit(s[i])) {
                num = num * 10 + s[i] - '0';
                if (i != s.length() - 1)
                    continue;
            }
            //碰到'('时，把整个括号内的当成一个数字处理
            if (s[i] == '(') {
                //递归处理括号
                vector<int> res = function(s, i + 1);
                num = res[0];
                i = res[1];
                if (i != s.length() - 1)
                    continue;
            }
            switch (op) {
                //加减号先入栈
                case '+':
                    stack.push(num);
                    break;
                case '-':
                    //相反数
                    stack.push(-num);
                    break;
                //优先计算乘号
                case '*':
                    int temp = stack.top();
                    stack.pop();
                    stack.push(temp * num);
                    break;
            }
            num = 0;
            //右括号结束递归
            if (s[i] == ')')
                break;
            else
			  	//得到运算符
                op = s[i];
        }
        int sum = 0;
        //栈中元素相加
        while (!stack.empty()) {
            sum += stack.top();
            stack.pop();
        }
        return vector<int> {sum, i};
    }

    int solve(string s) {
        return function(s, 0)[0];
    }
};