题意整理:

题目会给出一个包含括号，数字以及加减乘三种运算符的表达式，需要计算出表达式最终的值。

方法一：栈+递归

核心思想：可以利用栈对表达式进行解析。

思路：对于一个表达式，可以先记录当前遇到的前一个符号，开始时默认为+号。当解析完成一个数字时（字符串结尾或遇到符号），将数字与记录的符号进行运算后压栈，并更新符号。在遍历完字符串后，将栈中的数字一一弹出进行求和即可得到结果。
具体分析：
当遇到数字时，对其求值即可。
当遇到左括号时，递归进入下一层
当遇到右括号时，结束本层，计算出结果进行返回
当遇到符号或字符串结尾时，根据前一个遇到的符号进行数字的压栈
当前一个符号为号时，直接将数字压入（此时为 x + 当前数字）
当前一个符号为号时，将数字的相反数压入（此时为 x - 当前数字）
当前一个符号为号时，将栈中前一个数字弹出与当前数字相乘后压入（此时为 x * 当前数字）

核心代码：

class Solution {
public:
    int n = 0;//表达式长度

    int calHelper(string s, int& i) {
        //主要i为引用，记录当前解析到的长度
        char operation = '+';//初始化符号为+
        stack<int> nums;
        int num = 0;
        for (; i < n; ++i) {
            if(s[i] >= '0' && s[i] <= '9') {
                //对数字计算
                num = num * 10 + (s[i] - '0');
            } else if (s[i] == '(') {
                //遇见括号时递归括号内数字
                num = calHelper(s, ++i); 
                i++; 
            } 
            if((s[i] < '0' || s[i] > '9') || i >= (n - 1)) {
                //根据上一个符号将对应数字压栈
                switch (operation)
                {
                case '+': 
                    nums.push(num);
                    break;
                case '-': 
                    nums.push(-num);
                    break;
                case '*':
                    num *= nums.top();
                    nums.pop();
                    nums.push(num);
                    break;
                }
                operation = s[i];//记录当前符号
                num = 0;
            }
            if(s[i] == ')') {
                //退出循环，回到上一层
                break;
            } 
        }
        num = 0;
        while (!nums.empty()) {
            //取出栈中数字累加
            num += nums.top();
            nums.pop();
        }
        return num;
    }

    int solve(string s) {
        int i = 0;
        n = s.length();
        return calHelper(s, i);
    }
};

复杂度分析：

时间复杂度：，为字符串长度。求值中对每个字符进行了一次访问。
空间复杂度：，即为显式使用的栈空间以及递归使用的栈空间，显式使用的栈空间最多将所有数字压入，递归的栈空间最极端为全为括号包含一个数字，此时达到

方法二：转换为后缀表达式求值

核心思想：

一般的算术表达式是中缀形式，利于人的计算但不利于编程计算。所有可以先可以利用逆波兰算法将算术表达式的中缀形式转为易于计算的后缀形式。中缀和后缀表达式既对计算树的不同遍历方式，如下图：

转换步骤：
对当前字符情况：
1.如果是数字，读出其后连续数字字符为一个字符串，将其加入到字符串数组中。
2.如果是左括号，则直接入栈
3.如果是右括号，则说明已有一对括号配对，开始对栈进行出栈操作，将出栈的元素加入到数组中。出栈操作直到遇到左括号结束。左右括号不加入数组。
4.如果遇到了运算符,则需要对栈顶元素进行判断
（1）如果栈为空，或栈顶字符不为运算符，则直接将运算符入栈。
（2）如果栈顶是运算符，则比较两则的优先级：如果当前运算符优先级高于栈顶字符优先级，则直接将其入栈；否则，将栈顶运算符出栈加入到数组中，并再次回到4
5.表达式读取完毕后，将栈中剩余元素加到数组中。
对后缀表达式求值：
此时需要使用栈存储操作数和中间结果。如果遇到数字则进行入栈，如果遇到了运算符，则从栈中取出两个元素，按照运算符对两个数进行计算，得出的结果再次放入栈中。遍历完成之后，栈顶元素就是最终的计算结果。

核心代码：

class Solution {
public:
    //此函数用于将中缀表达式转换为后缀表达式
    vector<string> change(string& s) {
        stack<string> sk;
        vector<string> res;//记录读取字符串
        int i = 0, n = s.length();
        while(i < n) {
            string t;
            char w = s[i];
            if(w == '(') {//左括号直接入栈
                t += w;
                sk.push(t);
                ++i;
            } else if(w == ')') {//遇到右括号，将左右括号间元素出栈
                while(!sk.empty()) {
                    string c = sk.top();
                    sk.pop();
                    if(c == "(") {
                        break;//丢弃左括号
                    } else res.push_back(c);
                }
                ++i;
            } else if(w == '+' || w == '-' || w =='*') {
                if(sk.empty()) {
                    t += w;
                    sk.push(t);
                } else {
                    while(!sk.empty() && (sk.top() == "+" || sk.top() == "-" || sk.top() == "*") && w != '*') {//栈顶优先级大于等于当前字符优先级
                        res.push_back(sk.top());
                        sk.pop();
                    }
                    t += w;
                    sk.push(t);
                }
                ++i;
            } else {
                while (i < n && s[i] >= '0' && s[i] <= '9'){
                    t += s[i++];//读取数字字符
                }
                res.push_back(t);
            }
        }
        //将栈中剩余元素读出
        while(!sk.empty()) {
            string t;
            t += sk.top();
            sk.pop();
            res.push_back(t);
        }
        return res;
    }

    int solve(string s) {
        vector<string> res = change(s);//得到后缀表达式
        stack<int> nums;
        int n = res.size();
        for (int i = 0; i < n; ++i) {
            if (res[i] == "+" || res[i] == "-" || res[i] == "*") {
                int num2 = nums.top();
                nums.pop();
                int num1 = nums.top();
                nums.pop();
                //按表达式进行计算
                if (res[i] == "+") nums.push(num1 + num2);
                if (res[i] == "-") nums.push(num1 - num2);
                if (res[i] == "*") nums.push(num1 * num2);
            }
            else {
                nums.push(stoi(res[i]));//计算出数字压栈
            } 
        }
        return nums.top();//最后栈顶即为答案
    }
};

复杂度分析：

时间复杂度：，为字符串长度。求值中对每个字符进行了一次访问，
空间复杂度：，即为使用的两个栈空间以及数组空间，二者都不会超过字符串长度。