之前做了牛客的BM 49 表达式的计算之后感觉表达式计算确实很神奇。之前也有想自己实现一些查询语法的需求，但因为我没修过《编译原理》的课，于是一直被搁置着。虽然对这种复杂的查询表达式解析可能搞不太定，但是我觉得对四则运算和括号组成的这样的数学表达式应该还是要搞得定的，所以我开了这样一个专题来说明表达式计算背后的方法，也用几道题来实操一下这两个方法。

原理和方法

我们日常使用的表达式一般（夸张一点说，全部）是中缀表达式，这种表达式将操作数置于运算符两边，并通过括号和运算符的计算规则来表达优先级。比如"3+6*(2+5)"就是一个中缀表达式，因为(2+5)是被括号括起来的，因此要先计算括号的值，得到："3+6*7"。然后又因为乘法优先级更高，所以要先算"6*7"，得到："3+42"，最后算出结果是45。

这样的中缀表达式对人来说很自然，通过括号和运算符优先级，我们可以很容易地调整表达式去进行我们想进行的计算。但对于机器来说，这样复杂的优先级规则对编写代码很不友好。还好，前人想出了一种精妙的方法将中缀表达式转换为后缀表达式，后者不需要考虑运算符和括号（准确地说是后缀表达式里没括号）的优先级了，因而对后缀表达式求值肯定是更简单的。

这篇文章介绍的方法是通过调度场算法将（中缀）表达式转换为后缀表达式/逆波兰表达式后再使用逆波兰表达式的求值算法来求表达式的值。引用一下wiki上的说明简要介绍一下这两个方法吧：

词条：逆波兰表示法

逆波兰表示法（英语：Reverse Polish notation，缩写RPN，或逆波兰记法），是一种由波兰数学家扬·卢卡西维茨于1920年引入的数学表达式形式，在逆波兰记法中，所有操作符置于操作数的后面，因此也被称为后缀表示法、后序表示法。逆波兰记法不需要括号来标识操作符的优先级。

逆波兰结构由弗里德里希·L·鲍尔和艾兹格·迪科斯彻在1960年代早期提议用于表达式求值，以利用堆栈结构减少电脑内存访问。逆波兰记法和相应的算法由澳大利亚哲学家、电脑学家查尔斯·伦纳德·汉布尔在1960年代中期扩充。

词条：调度场算法

调度场算法（Shunting Yard Algorithm）是一个用于将中缀表达式转换为后缀表达式的经典算法，由艾兹格·迪杰斯特拉引入，因其操作类似于火车编组场而得名。

总结一下就是调度场算法能将中缀表达式转换为不用考虑操作符优先级的后缀表达式，之后对表达式求值就比较简单了。

调度场算法

那问题的关键之一就是这个调度场算法，因为我也不知道啥叫火车编组场，所以也不太能懂这个”调度场“指的是什么。但是我们看一下伪代码：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
当还有记号可以读取时：
----读取一个记号。
----如果这个记号表示一个数字，那么将其添加到输出队列中。
----如果这个记号表示一个函数，那么将其压入栈当中。
----如果这个记号表示一个函数参数的分隔符（例如，一个半角逗号 , ）：
----====从栈当中不断地弹出操作符并且放入输出队列中去，直到栈顶部的元素为一个左括号为止。如果一直没有遇到左括号，那么要么是分隔符放错了位置，要么是括号不匹配。
----如果这个记号表示一个操作符，记做o1，那么：
----====只要存在另一个记为o2的操作符位于栈的顶端，并且如果o1是左结合性的并且它的运算符优先级要小于或者等于o2的优先级，或者如果o1是右结合性的并且它的运算符优先级比o2的要低，那么将o2从栈的顶端弹出并且放入输出队列中（循环直至以上条件不满足为止）；
----====然后，将o1压入栈的顶端。
----如果这个记号是一个左括号，那么就将其压入栈当中。
----如果这个记号是一个右括号，那么：
----====从栈当中不断地弹出操作符并且放入输出队列中，直到栈顶部的元素为左括号为止。
----====将左括号从栈的顶端弹出，但并不放入输出队列中去。
----====如果此时位于栈顶端的记号表示一个函数，那么将其弹出并放入输出队列中去。
----====如果在找到一个左括号之前栈就已经弹出了所有元素，那么就表示在表达式中存在不匹配的括号。
当再没有记号可以读取时：
----如果此时在栈当中还有操作符：
----如果此时位于栈顶端的操作符是一个括号，那么就表示在表达式中存在不匹配的括号。
----将操作符逐个弹出并放入输出队列中。
退出算法。

这是一个考虑了函数符号的版本，我们先不考虑函数因此略去关于函数的部分。

我们从头开始看，”读取一个记号“中的”记号“其实对应的是英文中的"token"，意思是一个能表达含义的字符块。比如”132+133“里面的token应该是["132", "+", "133"]，而不是按字符读取的，这样的预处理可以让后面的算法专注于将有优先级的中缀表达式转换为后缀表达式而不需要关心怎么样将零散的数字字符合并为一个完整的数字。在实现中，我们可以使用正则表达式来做到token的切分。

之后，第二句开始提到了一个输出队列的概念，当算法退出时，这个队列依次出队就能完成中缀表达式到后缀表达式的转换。这个分支的意思是token是数字时把数字添加到队列里，这是必要的。

再后面就开始判断函数是操作符了，这也是最精彩的部分之一。因为中缀表达式操作符是在操作数中间的，而后缀表达式是在操作数后面，所以转换时操作符需要想火车一样驶入支路中，先让两个操作数开过去了之后再在合适的时机开到操作数后面。这个合适的时机有两个，一个是最后面了没操作符了，所以从符号栈中弹出所有符号；另一个就是这几行伪代码分支描述的，有低优先级/同优先级的运算符要开进去了，如果这个运算符再不开到输出队列里就会改变表达式的意思。

对符号栈出栈第二种情况，它是怎么判断时机合适的呢？当有一个新的运算符要进符号栈的时候，算法会检查这个运算符之前的符号是不是已经到了进去的时机了，具体来讲如果栈顶的符号优先级大于这个符号，那显然它是要先于这个符号计算的，所以现在不出栈的话后面就会在这个符号后面出栈，就违背了它在表达式中先进行计算的本意。反之，如果栈顶符号优先级小于这个符号，那么它不应该出栈，因为本来这个要入栈的符号就要先于现在栈顶的符号计算。至于同优先级的情况，则需要考虑当前的算符是左结合的还是右结合的，四则运算的算符都是左结合的，即从左到右计算；但有些算符比如幂计算是从右到左进行计算的，"2^3^2"应该表达的是\(2^{3^2}\)，因此要先算\(3^2=9\)之后再算\(2^9=512\)。对于左结合的运算符，那肯定是前面的先算，所以同优先级下先进来的算符应该先出栈；反之，如果是右结合计算符，那同优先级下应该先进来的应该后出栈，也即同优先级栈顶元素就不出栈了。

之后是对括号的处理，括号类似一个提高优先级的手段，如果发现了右括号，我们就会一直出符号栈直到遇到左括号。这种方法也是比较巧妙的一个点，就是利用了括号闭合的式子先算的特点，直接弹出运算符提高括号内运算的优先级。这里要注意左括号出栈的唯一机会就是被右括号抵消，因此它实际上应该是运算优先级”最低“的符号，它除非遇到左括号否则不应该在任何算符之前出栈。

最后就是符号栈出栈的第一种情况了，如果所有的标记都遍历完了，那就让符号栈的算符依次出去，这样可以保证操作数在对应操作符前面。遍历完所有标记，出完符号栈的所有符号，剩下的输出队列里就是后缀表达式了。

上面就是对这个调度场算法的全部解读了，引用一下wiki上的示意图来直观感受一下这个过程：

img

逆波兰表达式计算

逆波兰表达式的计算可以根据这个表示方法的性质进行操作，因为算符在操作数后面，因此如果遇到操作数就把操作数压入一个数字栈中，遇到运算符就从数字栈中出栈对应数目的数字完成计算，并将结果压回到数字栈。重复该过程直到完成整个逆波兰表达式的遍历即可，对正确的逆波兰表达式此时数字栈只会剩下唯一的一个元素，该元素就是这个逆波兰表达式的结果。

结合这两个过程，我们就可以计算中缀表达式啦！

双栈解法

能不能将调度场算法和逆波兰表达式计算融合起来，不需要转换成完整的后缀表达式就得出答案呢？答案是可以的，就是一开始就维护符号栈和数字栈两个栈。双栈解法的本质是逆波兰表达式优先计算的符号在前面，只要有符号出栈就说明这个符号需要先计算，因此可以边转化逆波兰表达式边完成逆波兰表达式的计算。这样不需要得到一个完整的逆波兰表达式，而只需要维护中间结果和还未出栈的符号，最后数字栈的唯一元素也就是表达式的解。

总结来说双栈解法就是边转化逆波兰表达式边计算的变体，本质上还是调度场算法和逆波兰表达式的计算。

表达式计算的实操

主要是用调度场算法+逆波兰表达式计算方法解决一下之前的提到的那几个题。

150. 逆波兰表达式求值

url：150. 逆波兰表达式求值

考察知识点：栈

就按上面说的实现一下即可。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
class Solution:
    def evalRPN(self, tokens: List[str]) -> int:
        stack = []
        for token in tokens:
            if token in "+-*/":
                a = stack.pop()
                b = stack.pop()
                if token == "+":
                    stack.append(b+a)
                elif token == "-":
                    stack.append(b-a)
                elif token == "*":
                    stack.append(b*a)
                elif token == "/":
                    stack.append(int(b / a))
            else:
                # 操作数
                stack.append(int(token))
        return stack[-1]

224. 基本计算器

url：224. 基本计算器

考察知识点：中缀表达式转后缀表达式、逆波兰表达式计算

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
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
import re
# 处理单目的"-"运算符
unimal_op = re.compile(r'(?<=[^\d)])-')

class Solution:
    def op_priority(self, c):
        if c == "*" or c == "/":
            return 2
        elif c == "+" or c == "-":
            return 1
        else:
            return 0

    def calculate(self, s: str) -> int:
        num_stack = []
        op_stack = []
        i = 0

        s = s.replace(" ", "")
        s = unimal_op.sub("0-", s)

        while i < len(s):
            c = s[i]

            if c == "(":
                op_stack.append(c)
                i += 1
            elif c in "+-*/":
                while len(op_stack) > 0 and self.op_priority(op_stack[-1]) >= self.op_priority(c):
                    op = op_stack.pop()
                    if op == "-" and len(num_stack) == 1:
                        num_stack.append(-1 * num_stack.pop())
                    else:  
                        a = num_stack.pop()
                        b = num_stack.pop()
                        if op == "+":
                            num_stack.append(b+a)
                        elif op == "-":
                            num_stack.append(b-a)
                        elif op == "*":
                            num_stack.append(b*a)
                        elif op == "/":
                            num_stack.append(int(b/a))
                op_stack.append(c)
                i += 1
            elif c == ")":
                while op_stack[-1] != "(":
                    op = op_stack.pop()
                    if op == "-" and len(num_stack) == 1:
                        num_stack.append(-1 * num_stack.pop())
                    else:  
                        a = num_stack.pop()
                        b = num_stack.pop()
                        if op == "+":
                            num_stack.append(b+a)
                        elif op == "-":
                            num_stack.append(b-a)
                        elif op == "*":
                            num_stack.append(b*a)
                        elif op == "/":
                            num_stack.append(int(b/a))
                op_stack.pop()
                i += 1
            else:
                # 操作数
                num_str = ""
                while i < len(s) and s[i].isdigit():
                    num_str += s[i]
                    i += 1
                num_stack.append(int(num_str))

        # 把没算完的算完
        while len(op_stack) > 0:
            op = op_stack.pop()
            if op == "-" and len(num_stack) == 1:
                num_stack.append(-1 * num_stack.pop())
            else:  
                a = num_stack.pop()
                b = num_stack.pop()
                if op == "+":
                    num_stack.append(b+a)
                elif op == "-":
                    num_stack.append(b-a)
                elif op == "*":
                    num_stack.append(b*a)
                elif op == "/":
                    num_stack.append(int(b/a))
        return num_stack[-1]

这里用了一个变通的方式处理单目的”-“号，就是预先将单目的”-“处理为”0-“，这样单目的负号可以转化为减号，就不用单独处理了。

P1175 表达式的转换

url：P1175 表达式的转换

考察知识点：中缀表达式转后缀表达式、逆波兰表达式计算

这题目就考察到了右结合的"^"算符的处理，然后额外要打印每次逆波兰表达式计算的中间情况。

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
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
import re
# 读取输入
s = input()

# 定义正则表达式来匹配整数和浮点数以及运算符
pattern = re.compile(r'(\d+\.\d+|\d+|[-+*/()\^])')

# 解析token
tokens = pattern.findall(s)

# 符号栈和输出队列
op_stack = []
output_queue = []

# 优先级字典
priority = {"(": 0, "+": 1, "-": 1, "*": 2, "/": 2, "^": 3}

for token in tokens:
    if token in "-+*/^":
        if token == "^":
            # 单独考虑右结合运算符
            while len(op_stack) > 0 and priority[op_stack[-1]] > priority[token]:
                output_queue.append(op_stack.pop())
        else:
            # 左结合，不低于就可以弹出
            while len(op_stack) > 0 and priority[op_stack[-1]] >= priority[token]:
                output_queue.append(op_stack.pop())
        op_stack.append(token)
    elif token == "(":
        op_stack.append("(")
    elif token == ")":
        # 弹出栈直到遇到"("
        while op_stack[-1] != "(":
            output_queue.append(op_stack.pop())
        # 弹出右括号
        op_stack.pop()
    else:
        # 加入操作数
        output_queue.append(int(token))
# 将剩余操作符送入输出队列中
while len(op_stack) > 0:
    output_queue.append(op_stack.pop())

# 打印一下逆波兰表达式
print(" ".join([str(token) for token in output_queue]))

# 计算逆波兰表达式的值
num_stack = []
while len(output_queue) > 0:
    # 依次出队
    token = output_queue.pop(0)
    if isinstance(token, str):
        # 这边是运算符，这里的运算符都是双目的因此都可以先提两个操作数
        a = num_stack.pop()
        b = num_stack.pop()
        if token == "+":
            num_stack.append(b + a)
        elif token == "-":
            num_stack.append(b - a)
        elif token == "*":
            num_stack.append(b * a)
        elif token == "/":
            num_stack.append(int(b/a))
        elif token == "^":
            num_stack.append(b**a)
        print(" ".join([str(num) for num in num_stack]) + " " + " ".join([str(token) for token in output_queue]))
    else:
        # 操作数直接压栈
        num_stack.append(token)

彩蛋：做一个简易计算器

用括号和定义的符号优先级计算中缀表达式，对人类来说是很容易理解和掌握的，但对于计算机来说却不是。如果没有逆波兰表达式作为桥梁，随着运算符号的增多，很难想象需要多么复杂而且难以扩展的递归来实现这些行为。为了加深对这个算法的理解，我决定自己用Python做一个简易的计算器。这个简易的计算器对输入的中缀表达式转为后缀表达式，最后计算后缀表达式得出结果。

项目地址：SimpleCalculator

现在应该支持了带括号的四则运算、幂运算和取余运算。以后可能会实现更多的算子，比如单目的负号（对，现在还不支持单目负号，所以输入负数需要输入"0-{这个数的绝对值}"。这种蹩脚问题的原因是我还没想好怎么去优雅地区分单目负号和双目减号）、阶乘等。如果有时间的话，甚至可以尝试支持一下函数的运算。