调度场算法（Shunting-yard Algorithm）（中篇）

在上篇最后，我们提到，调度场算法主要负责在中缀表达式的解析过程中解决哪个运算符可以优先与数字结合的问题。

可以先想象一下，在“发明”调度场算法之前，程序员们会如何做。

朴素的算法 其一

考虑简单的情形，假设我们要计算的表达式中，只允许出现：

1. 数字；
2. 加法；
3. 乘法；
4. 括号对。

这里跑偏一下，从简化的版本开始解决问题是一种很有效的方式，数学家和物理学家深谙此道：

有一个农民发现自己养的鸡都出问题不下蛋了，找一个物理学家帮忙。物理学家做了一番计算之后宣布我已经找到了一个解！但是这个解只对真空农场中的球形鸡有效。

数学家受够了数学，打算换一行当消防队员。消防队长指着一个货栈问：“假设这里起火了，怎么办？”数学家回答：“我会把水管接在消防栓上，然后把火浇灭。”消防队长又问：“那么假设您看到货栈没有起火，怎么办？”数学家若有所思：“那我就把它点着。”

好。回来。

首先，括号的地位高于一切，我们可以先在表达式中查找括号对，并解析其中的内容。

例如：

1+(2+3)*4+5

从左到右扫描表达式，当我们遇到左括号时，寻找匹配的右括号，然后先行处理其中的内容，得：

1+?*4+5

?=2+3

顺便补充一下，寻找匹配右括号的一种简单粗暴的方法是：

1. 设变量x=1；
2. 从当前位置开始查找括号；
3. 如果遇到左括号，x=x+1；
4. 如果遇到右括号，x=x-1；
5. 当x=0时，找到匹配的右括号。

然后，将2+3递归，计算得到5，过程暂时略过：

1+5*4+5

括号全部处理完毕了，扫描优先级较高的乘法——从左到右扫描表达式，令乘号与左右的数字结合——计算：

1+20+5

乘法全部处理完毕了，扫描加法，计算：

21+5

继续：

26

加法也处理完毕了，得到结果。

朴素的算法 其二

换个思路，这回我们使用瞪眼观察法。

首先，我们是可以在表达式上标注“层次”编号的，像这样：

1 1+(2+3)*4+5
2 00 111 0000

编号是可以“提升”的，只要不打破原来的运算顺序就行：

1 1+[[(2+3)*4]]+5
2 00[[ 888 77]]00

那么，在考虑优先级以后，我们可以进一步标出层次编号：

1 1+(2+3)*4+5
2 11 333 2200

此时的“层次”是什么呢？没错，它对应着数字、符号在AST中的深度（数字的AST深度少计入一层），也对应着同一位置在括号补完的状态下被套入的括号对的个数。

 1 Root       +
 2            |\
 3            + \
 4           /|  \
 5          / *   \
 6         /  |\   \
 7        /   + \   \
 8       /   /|  |   |
 9      1+ (2+3)*4  +5 表达式
10      11  333 22  00 层次编号
11     (1+((2+3)*4))+5 括号完整的表达式

但是，目前我们并不能容易地标出这种层次编号，于是我们需要进行一些构造：

• 把所有数字用括号围住。
• 改变“提升”方式，让某些运算符的编号“对齐”（关于某数同余）。

1 (1)+((2)+(3))*(4)+(5)
2  3 1  6 4 6  2 3 1 3
3 
4 1+(2+3)*4+5
5 31 646 2313

然后我们就得到标注方法：

1. 从3开始；
2. 遇到数字，输出当前层次的数字；
3. 遇到加号，输出当前层次减二的加号；
4. 遇到乘号，输出当前层次减一的乘号；
5. 遇到左括号，层次加3；
6. 遇到右括号，层次减3。

这个过程稍稍抽象了一点。别忘了，“层次”可以理解成括号层数。我们把上面的过程翻译得生动形象一点：

1 print (((                       # 1
2 for x in input
3     if x is number: print x     # 2
4     if x is "+":    print ))+(( # 3
5     if x is "*":    print )*(   # 4
6     if x is "(":    print (((   # 5
7     if x is ")":    print )))   # 6
8 end for
9 print )))

第一次看到这个的时候……记得我当时真的被冷到了——呃——它确实能用。

且慢，还有一个问题。我们得到了上面程序中的print结果，应该如何使用呢？我们此时已经通过插入括号规避了优先级的问题，可以从左到右依次计算，遇到左括号时，将表达式之后的部分递归，遇到右括号或末尾则返回。

除了递归以外，还有另一种方式——堆栈（递归和堆栈本来就是一家人嘛）。具体怎么实现，留给各位读者思考吧。

//憋到现在，堆栈终于在舞台上第一次亮相，真是个可怜的孩纸。

经过之前如此多的铺垫，下篇中我们终于可以顺利地“得到”调度场算法了。