课堂要点：

在计算机中，递归依靠栈来实现。

(2+2)^(1+1)表达式的中缀表达式可以用二叉树来表示，而二叉树是一个基于递归的概念。

题目描述

给出一个表达式, 其中运算符仅包含+,-,*,/,^（加 减 乘 整除 乘方）要求求出表达式的最终值。

数据可能会出现括号情况，还有可能出现多余括号情况。

数据保证不会出现大于或等于 231 的答案。

数据可能会出现负数情况。

样例

输入样例：
(2+2)^(1+1)
输出样例：

算法

步骤

1. 当前的运算符优先级 小于等于 栈顶的运算符优先级，也可以说， 栈顶的运算符优先级 大于等于 当前的运算符优先级， 则符号栈弹出一个符号，数字栈弹出两个数字， 对运算符和数字进行运算，把结果压入数字栈，再把当前运算符压入符号栈。

2. 如果遇到括号：如果是左括号，直接入栈。如果是右括号，弹出栈中第一个左括号前所有的操作符，并将左括号弹出。

(模拟) $O(n)$

通过模拟的方法求解。

1. 对字符串进行预先处理，保证(数量 >= )数量。因为遇到)，就要弹出一个(，需要保证总是有(可弹出来。

时间复杂度

参考文献

C++ 代码

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

stack<int> nums;
stack<char> ops;

void cal(){
    int a = nums.top(); nums.pop();
    int b = nums.top(); nums.pop();
    char c = ops.top(); ops.pop();
    int d;

    if (c == '+') d = b + a;
    else if (c == '-') d = b - a;
    else if (c == '*') d = b * a;
    else if (c == '/') d = b / a;
    else {
        d = 1;
        while (a --) d *= b;
    }
    nums.push(d);
}

int main(){
    string str;
    cin >> str;
    // cout << str << endl;
    if (str[0] == '-') str = '0' + str;
    string left;
    for (int i = 0; i < str.size(); i ++) left += '(';//先加左括号，变成合法前缀
    str = left + str + ')';//加有括号，可以计算最后一步结果
/*
    字符是数字

    字符是其他字符
        0. (
        1. + -
            a. 负号
                -(
                一般情况
            b. + -
            符号栈栈顶元素 != '(' 则cal()
        2. * /
            != * / ^
        3. ^
            != ^
        4. )
            !=(
            pop
        5.invalid operator!
*/
    for (int i = 0; i < str.size(); i ++){
        if (str[i] >= '0' && str[i] <= '9'){//第一个字符是数字开头的话
            int j = i, t = 0;
            while (str[j] >= '0' && str[j] <= '9'){
                t = t * 10 + str[j] - '0';
                j ++;
            }
            nums.push(t);
            i = j - 1;
        }else{//其他符号开头
            char c = str[i];
            if (c == '(') ops.push(c);
            else if (c == '+' || c == '-'){//如果是 + -
                if (c == '-' && i && !(str[i - 1] >= '0' && str[i - 1] <= '9') && str[i - 1] != ')'){//-号需要特判，如果这个-表示负数，而不是减号
                    if (str[i + 1] == '('){
                        nums.push(-1);
                        ops.push('*');
                    }else{
                        int j = i + 1, t = 0;
                        while (str[j] >= '0' && str[j] <= '9'){
                            t = t * 10 + str[j] - '0';
                            j ++;
                        }
                        nums.push(-t);
                        i = j - 1;
                    }
                }
                else{//由于+ -优先级最低，如果栈里有其他运算符，直接计算
                    while (ops.top() != '(') cal();
                    ops.push(c);
                }
            }
            else if (c == '*' || c == '/'){//当前符号是 * /, 
                while (ops.top() == '*' || ops.top() == '/' || ops.top() == '^') cal();
                ops.push(c);
            }
            else if (c == '^'){//当前符号是^
                while (ops.top() == '^') cal();
                ops.push(c);
            }
            else if (c == ')'){//当前符号是)
                while (ops.top() != '(') cal();
                ops.pop();
            }
            else cout << "invalid operator!" << endl;
        }

    }
    cout << nums.top() << endl;
    return 0;
}