题目的主要信息：

• 输入一个表达式（用字符串表示），求这个表达式的值
• 字符串中有0-9的数字，加减乘除符号，只有小括号
• 表达式一定合法，不用判断括号是否合法之类的问题
• 除数用整数运算

方法一：递归

具体做法：

括号中的运算式可以看成运算式的子问题，因此可以用递归解决。

第一次运算是运算字符串的起始到结尾，之后的子问题也是从子问题的开始到结尾。运算的时候，遍历每个子问题的开始到结尾，对于每个字符如果是数字字符则组装成数字，如果是左括号我们进入括号以后开始遍历到右边，每次遇到一个左括号累增一个层数，遇到一个右括号递减一个层数，层数为0则最后的右括号刚好匹配了最左端的左括号，则两个括号之间就是子问题，可以送入函数递归。递归得到的结果可以当成一个数字。

对于非数字非括号或者到了子问题结尾，我们开始运算，默认运算符为加号，根据运算符将其分别送入存储的数组，如果加减就送入整数或者负数，如果是乘除就与数组末尾的数字计算，得到的结果存入数组，该为就作为下一次的运算符（因为每个运算符是与后面的信息计算）。

最后数组中全部的元素累加和就是表达式的结果。

#include<iostream>
#include<string>
#include<vector>
using namespace std;

int compute(string& s, int left, int right){
    char op = '+'; //默认加开始
    int num = 0;
    vector<int> st;
    for(int i = left; i <= right; i++){
        if(isdigit(s[i])) //数字
            num = num * 10 + s[i] - '0'; //计算该部分数字总和
        if(s[i] == '('){ //进入左括号
            int layer = 0; //统计左括号层数
            int j = i;
            while(j <= right){ //遍历到右边
                if(s[j] == '(')
                    layer++; //遇到左括号，层数累加
                else if(s[j] == ')'){
                    layer--; //遇到右括号层数递减
                    if(layer == 0) //直到层数为0
                        break;
                }
                j++;
            }
            num = compute(s, i + 1, j - 1); //递归计算括号中的部分
            i = j + 1;
        }
        if(!isdigit(s[i]) || i == right){ //遇到运算符或者结尾
            switch(op){ //根据运算符开始计算
                case '+': st.push_back(num); break; //加减法加入到末尾
                case '-': st.push_back(-num); break;
                case '*': st.back() *= num; break; //乘除法与末尾计算
                case '/': st.back() /= num; break;
            }
            op = s[i]; //修改为下一次的运算符
            num = 0;
        }
    }
    int res = 0; 
    for(int x : st) //累加和
        res += x;
    return res;
}
int main(){
    string s;
    while(cin >> s){
        cout << compute(s, 0, s.length() - 1) << endl;
    }
    return 0;
}

复杂度分析：

• 时间复杂度：$O(n)O(n)$，其中$nn$为字符串长度，遍历整个字符串进行计算
• 空间复杂度：$O(n)O(n)$，辅助数组及递归栈深度最大为$nn$

方法二：双栈法

具体做法：

上述的子问题也用栈来解决括号，我们用一个栈记录刚刚的计算结果，每次都与栈顶元素计算，然后加入栈顶，用另一个栈记录包括括号在内的所有运算符，根据运算优先级来计算第一个栈中的内容。

因为不用考虑括号的合法性，我们可以在栈中添加括号。遍历的时候遇到左括号就将其加入栈中，遇到右括号依次弹出运算符栈和数字栈中的内容进行计算，直到遇到左括号为止，就相当于计算了一个子问题，运算结果依旧存在栈中，不影响后续的计算。

遇到数字要区分正负号和加减号，可以用一个flag标记每轮是否出现过了数字了，数字之前的为正负号，数字之后的为加减号。

#include<iostream>
#include<stack>
using namespace std;

void compute(stack<int>& st1, stack<char>& st2){ //根据栈顶运算符弹出栈顶两个元素进行运算
    int b = st1.top();
        st1.pop();
    int a = st1.top();
        st1.pop();
    char op = st2.top(); //栈顶运算符
        st2.pop();
    if(op == '+') a = a + b; //加
    else if(op == '-') a = a - b; //减
    else if(op == '*') a = a * b; //乘
    else if(op == '/') a = a / b; //除
    st1.push(a);
}

bool priority(char m, char n){ //比较运算符优先级
    if(m == '(') //括号优先级最高
        return false;
    else if((m == '+' || m == '-') && (n == '*' || n == '/')) //加减法小于乘除法
        return false;
    return true;
}
int main(){
    string s;
    while(cin >> s){
       stack<int> st1; //记录运算数字
       stack<char> st2; //记录运算符
       st2.push('('); //整个运算式添加括号
       s += ')';
       bool flag = false;
       for(int i = 0; i < s.length(); i++){
           if(s[i] == '(') //如果是左括号都在运算符栈加入(
               st2.push('(');
           else if(s[i] == ')'){ //遇到右括号
               while(st2.top() != '('){ //弹出开始计算直到遇到左括号
                   compute(st1, st2);
               }
               st2.pop(); //弹出左括号
           } else if(flag){ //运算符
               while(priority(st2.top(), s[i])){ //比较运算优先级
                   compute(st1, st2); //可以直接计算
               }
               st2.push(s[i]); //需要将现阶段加入栈中等待运算
               flag = false;
           } else{ //数字
                int j = i; //记录起始
                if(s[j] == '-' || s[j] == '+') //正负号
                    i++;
                while(isdigit(s[i])){
                    i++;
                }
                string temp = s.substr(j, i - j); 
                st1.push(stoi(temp)); //截取数字部分，转数字
                i--;
                flag = true; //数字结束，下一次flag为true就是运算符了
           }
       }
      cout << st1.top() << endl; //输出
    }
    return 0;
}

复杂度分析：

• 时间复杂度：$O(n)O(n)$，其中$nn$为字符串长度，遍历整个字符串进行计算
• 空间复杂度：$O(n)O(n)$，辅助栈深度最大为$nn$