题目的主要信息：

输入一个字符串表达式，求这个表达式的值。
字符串中包括数字、加减乘除、括号。

方法一：

用compute函数计算字符串中数字之间的运算，op为栈顶数字和当前数字的运算操作，pos为遍历的位置。在compute函数中，遍历一遍字符串，若当前字符是括号，则递归计算括号内的内容；若当前字符是数字，则继续往前走，直至遇到非数字字符，就提取出整个数字；提取出数字后，用一个switch操作判断当前数字和栈顶数字的运算，如果是‘+’，直接让当前数字入栈，因为最后我们的结果是栈中所有元素相加；如果是‘-’号，将当前数字取负入栈；如果是乘号，pop栈顶数字和当前数字作乘法，并存入栈中；如果是除号，pop栈顶数字和当前数字作除法，存入栈中。

运算结束后，更新op的值。最后的结果是栈中的所有数字相加。 alt 具体做法：

#include <iostream>
#include <stack>

using namespace std;

int p;

int compute(string & data)
{
    int len = data.size();
    int num = 0;
    char op = '+';
    stack<int> st;

    while (p < len) {
        if (data[p] == '{' || data[p] == '[' || data[p] == '(') {
            p++;
            num = compute(data);//如果是左括号，则递归计算括号后面的内容
        }
        while (p < len && isdigit(data[p])) {//如果当前字符是数字，循环提取整个整数
            num = num * 10 + data[p] -'0';
            p++;
        }
        switch (op) {//当前数字需要和栈顶数字作运算，把每次运算的结果放入栈中
        case '+'://加号
            st.push(num);
            break;
        case '-'://减号
            st.push(-num);
            break;
        case '*'://乘号，当前数字num和栈顶数字作乘法
            {
                int temp = st.top();
                temp *= num;
                st.pop();
                st.push(temp);
                break;
            }
        case '/'://除号，当前数字num和栈顶数字作除法
            {
                int temp = st.top();
                temp /= num;
                st.pop();
                st.push(temp);
                break;
            }
        }
        num = 0;//数字清空，等待下一轮
        op = data[p];//记录当前的符号
        if (data[p] == '}' || data[p] == ']'|| data[p] == ')') {
            p++;
            break;
        }
        p++;
    }

    int sum = 0;
    while (st.size()) {//将栈内数字相加即为结果
        sum += st.top();
        st.pop();
    }
    return sum;
}

int main()
{
    string data;
    while (cin >> data) {
        p = 0;
        cout << compute(data) << endl;
    }
    return 0;
}

复杂度分析：

时间复杂度： $O (n)$ ，需要遍历一遍字符串。
空间复杂度： $O (n)$ ，借助了栈来计算。

方法二：

不采用递归，使用两个栈。一个栈记录运算的数字，一个栈记录运算符。首先遍历一遍字符串，将中括号和大括号转换为小括号。第二次遍历一遍字符串，若当前字符是左括号则将它存入符号栈中，若为右括号则不断出栈计算，直至左括号出栈；若当前字符是运算符，且这个运算符前有数字（即flag为True），判断运算符栈顶符号和当前运算符的优先级，若栈顶优先级高则直接计算，然后将当前符号存入栈中；若当前字符是数字，循环往前移动，提取出整个数字，并设置flag为True。

具体做法：

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

string mp="+-*/";

bool isPrior(char top, char cur){ //比较运算符优先级
    if(top == '('){//括号优先级最高，但无法直接计算
        return false;
    }else if((top == '+' || top == '-') && (cur == '*' || cur == '/')) //加减的优先级小于乘除，不能直接计算
        return false;
    return true;
}

void compute(stack<int>& stk1, stack<char>& stk2){ //按栈顶运算符计算
    int num1 = stk1.top();//运算数1
        stk1.pop();
    int num2 = stk1.top();//运算数2
        stk1.pop();
    char op = stk2.top(); //运算符
        stk2.pop();
    switch(op){
        case '+': {
            num2 = num2 + num1; //加法
            break;
        }
        case '-': {
            num2 = num2 - num1; //减法
            break;
        }
        case'*': {
            num2 = num2 * num1; //乘法
            break;
        }
        case '/': {
            num2 = num2 / num1; //除法
            break;
        }
    }
    stk1.push(num2);
}


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(mp.find(s[i]) != mp.npos && flag){ //当前字符是运算符且前面有数字
               while(isPrior(st2.top(), s[i])){ //判断当前运算符和栈顶运算符的优先级
                   compute(st1, st2); //若栈顶运算符的优先级更高，则直接计算
               }
               st2.push(s[i]); //将当前运算符加入运算符栈
               flag = false;
           } else{
               int num = 0;
               while (i < s.size() && isdigit(s[i])) {//如果当前字符是数字，循环提取整个整数
                   num = num * 10 + s[i] -'0';
                   i++;
               }
               st1.push(num); //将当前数字存入栈中
               i--;
               flag = true;
           }
       }
      cout << st1.top() << endl; //输出
    }
    return 0;
}

复杂度分析：

时间复杂度： $O (n)$ ，需要遍历一遍字符串。
空间复杂度： $O (n)$ ，借助了栈来计算。

题解 | #表达式求值#

题目的主要信息：

方法一：

方法二：