题目链接：AcWing 3302. 表达式求值

本题可以作为模板，处理含有任何运算符的中缀表达式问题！

一、题意

给定一个表达式，其中运算符仅包含 +,-,*,/（加 减 乘 整除），可能包含括号，请你求出表达式的最终值。

二、题解

简单分析：

给定一个中缀表达式，例如(2+2)*(1+1)，要我们计算出最终结果！包含加减乘除和括号！

这时候，我们想到了后缀表达式，但是由于后缀表达式的特殊性，我们只要将该表达式放入一个栈中，遇到数字入栈，遇到运算符则出栈两个栈顶元素计算后再入栈，最终栈顶元素就是我们的表达式的值！

但是中缀表达式不一样，它并没有这样的性质！

后缀表达式是表达式树的后序遍历，中缀表达式就是表达式树的中序遍历！

对于上方样例(2+2)*(1+1)，表达式树的后序遍历为2 2 + 1 1 + *，没有问题；中序遍历为2 + 2 * 1 + 1，很明显，中序遍历得到的结果有一个优先级问题！

括号：括号只影响表达式优先级，不影响表达式树的结构！

我们建立表达式树进行分析：

  • 叶子节点为运算数
  • 其他节点为运算符

如下方简图：

我们可以对该表达式树进行递归运算，但是并没有必要将树建立出来，我们可以利用中缀表达式的性质，用栈来达到和递归一样的效果！

  • 当我们遍历到根节点，它是一个运算符，这时我们并不能直接和右节点运算，和后缀表达式不一样，因为右子树还没有被遍历，我们只有遍历完右子树才能和当前运算符进行运算！

好了，一个重要问题，如何判断一颗子树被遍历完了？

只要我们往下走（往下遍历），则说明该子树没有被遍历；只要我们往上走（往上遍历），说明该子树已经被遍历完毕！

针对运算符又如何判断呢？

如下图：栈中运算符（上一个）为乘法，当前运算符为加法

  • 若当前比上一个运算符优先级要低，则要先算a和b再算c，表示以上一个节点为根节点的子树已经遍历完毕了
  • 若当前和上一个运算符优先级相同（都为乘法），则要先算a和b再算c，同优先级从左向右，也可表明该子树遍历完毕
  • 若当前比上一个运算符优先级要高（乘法加法互换a + b * c）, 则无法计算a和b，表明该子树没有遍历完毕

总结：只要当前运算符优先级不大于上一个运算符优先级，就表明该子树被遍历完毕了，该子树就可以进行计算了！

还有一个括号问题：

  • 若为左括号，不必进行额外处理
  • 若为右括号，我们只需要将从右括号开始从右向左计算到左括号即可

为何为从右向左：

解释一：由于我们只有当当前运算符优先级不大于上一个运算符优先级的时候才会去计算该子树，意味着剩下的表达式，或者说括号内的表达式都一定是优先级递增的，因为优先级逆序的都由于子树被遍历完毕而被计算完了，所以括号内的一定是优先级递增的，从右向左运算完全符合运算法则！

解释二：或者说，一个运算符没有被计算过的话，一定是往下走的，向子树去走，如果往上走，说明该运算符已经计算过了！

由于括号内的运算符还没有被计算过，则说明是往下走的！可以往下走，则说明当前比上一个运算符优先级要高，所以运算符优先级必然是递增的！

双栈存储：

  • 一个存储运算符
  • 一个存储运算数

本题完全可以拓展：

由于本题的解法实在属于模板，毕竟处理第一行，后面代码都没有出现运算符，因此可以拓展到任何运算符的情况的题！

只需要做一个修改即可：将哈希表的运算符加上多出来的运算符和其优先级，并在eval函数中实现他的运算即可！

时间复杂度： O(n)

空间复杂度： O(n)

三、AC代码

参考如下：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
#include <iostream>
#include <unordered_map>
#include <stack>

using namespace std;

stack<int> num;
stack<char> op;
string str;

// 处理最后两个数的运算，注意：出栈顺序和运算顺序是相反的！
void eval(){
    auto a = num.top(); num.pop();
    auto b = num.top(); num.pop();
    auto c = op.top(); op.pop();
    
    if(c == '+') num.push(b + a);
    else if(c == '-') num.push(b - a);
    else if(c == '*') num.push(b * a);
    else if(c == '/') num.push(b / a);
}

int main(){
    cin >> str;
    unordered_map<char, int> map{{'+', 1}, {'-', 1}, {'*', 2}, {'/', 2}};
    for(int i = 0; i < str.size(); i ++){
        auto c = str[i];
        // 将连续数字抠出来
        if(isdigit(c)){
            int x = 0, j = i;
            while(j < str.size() && isdigit(str[j])) x = x * 10 + str[j ++] - '0';
            // 放入num栈中，for循环i要++，因此此处i应该为j - 1
            num.push(x), i = j - 1;
        }else if(c == '(') op.push(c); // 左括号无需处理，直接如op栈
        else if(c == ')'){
            // 遇到右括号，则从右向左依次处理num栈中的数，直到遇到op栈的左括号
            while(op.top() != '(') eval();
            // 左括号出栈
            op.pop();
        }else{
            // 四种运算符：只要op栈中的运算符优先级不小于当前运算符优先级即可进行运算
            while(op.size() && map[op.top()] >= map[c]) eval();
            // 运算完毕或者当前运算符优先级更高则当前运算符c直接入栈
            op.push(c);
        }
    }
    // 处理剩下的部分，直到运算符处理完毕
    while(op.size()) eval();
    cout << num.top() << endl;
    return 0;
}