思路:

题目的主要信息:

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

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

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

复杂度分析:

  • 时间复杂度:,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;//返回结果
    }
};

复杂度分析:

  • 时间复杂度:,最多遍历一遍字符串
  • 空间复杂度:,虽然用了很多辅助数组,最大不过