题解 | #表达式求值#

思路：

题目的主要信息：

支持+ - *三种符号的运算器，其中优先级+ - 是一级，*更高一级
支持括号运算

方法一：栈 + 递归
具体做法：
对于上述两个要求，我们要考虑的是两点，一是处理运算优先级的问题，二是处理括号的问题。

优先级处理我们可以借助栈，当遇到符号的时候如果是+，正常入栈，如果是-，则将其相反数入栈，如果是*，则将栈中内容弹出与后一个元素相乘再入栈，最后将栈中所有元素相加即可。
括号的处理我们可以借助递归，将括号内的运算视为一个子问题，由此来简化。

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];
    }
};

复杂度分析：

时间复杂度： $O(n)$ ，n为字符串长度，相当于遍历一遍
空间复杂度： $O(n)$ ，辅助栈和递归栈的空间

方法二：数组 + 递归
具体做法：
递归将式子分成子块：单独数字或者去掉括号的部分组成一个子块，加入elems中，同时用一个数组记录符号。
去掉括号依赖两个数组统计左右括号，并比较数量来决定。
由此，分成了子块和运算符。
然后遍历运算符的数组，遇到一个乘号需要判断其后一位是否是乘号*,如果是则需要递归乘上后面的子块，然后再计算当前的加减号，最后所有结果加起来即可。

class Solution {
public:
    int solve(string s) {
        //返回对应数值
        if (s.empty()) 
            return 0;
        else
        {
            int temp = 0;
            //组合数字
            for (size_t i = 0; i < s.size(); i++)
                if (s[i] >= '0'&&s[i] <= '9')
                {
                    temp = 10 * temp + (s[i] - '0');
                    if (i == s.size() - 1) 
                        return temp;
                }
                else//如果是式子则将式子分块
                    break;
        }
        //将式子分块
        vector<string> elems;//保存元素块
        vector<char> op; //保存该层式子的运算符
        vector<char> left;//记录左括号
        vector<char> right;//记录右括号
        op.push_back('+');//为了将结果加入result第一个运算符必须是+
        int i = 0; //当前元素块为i,从0开始
        for (auto iter = s.begin(); iter != s.end(); )
        {
            if (*iter >= '0' && *iter <= '9')//将数值型元素块加入elems
            {
                elems.push_back("");
                for (; iter != s.end() && *iter >= '0' && *iter <= '9'; iter++)
                    elems[i].push_back(*iter);
                i++;
            }
            else if (*iter == '+' || *iter == '-' || *iter == '*')//将运算符加入op
            {
                op.push_back(*iter);
                iter++;
            }
            else if (*iter == '(')//将带括号的元素块去掉最外侧括号后加入elems
            {
                elems.push_back("");
                std::string& temp = elems[i];
                while (iter != s.end() && (left.size() != right.size() || *iter == '('))
                {
                    if (*iter == '(') 
                        left.push_back(*iter);
                    else if (*iter == ')') 
                        right.push_back(*iter);
                    temp.push_back(*iter);
                    iter++;
                }
                temp = temp.substr(1, temp.size() - 2);//去掉最外侧括号
                i++;
            }
            else iter++;

        }
        //计算当前分式子的值
        int res = 0;
        for (int i = 0; i < op.size(); i++)
        {
            char o = op[i];
            if (i + 1 < op.size())//先预测后一位运算符是不是*
            {
                int temp = solve(elems[i]);
                while(i + 1 < op.size() && op[i + 1] == '*')//如果后面的*，则先计算乘
                {
                    temp *= solve(elems[i + 1]); //递归
                    i++;
                }
                switch (o)//当前符号进行加减处理
                {
                case '+': res += temp;
                          break;
                case '-': res -= temp;
                          break;
                }
            }
            else//若乘法已经算过了，只剩下加减
            {
                switch (o)
                {
                case '+': res += solve(elems[i]);
                          break;
                case '-': res -= solve(elems[i]);
                          break;
                }
            }
        }
        return res;//返回结果
    }
};

复杂度分析：

时间复杂度： $O(n)$ ，最多遍历一遍字符串
空间复杂度： $O(n)$ ，虽然用了很多辅助数组，最大不过 $O(n)$