调度场算法（Shunting-yard Algorithm）（下篇）
2014-03-07
中篇中，我们看到了两种简单的中缀表达式处理方法，但是它们或多或少存在缺点——第一种需要反复地扫描表达式，而第二种难以处理有大量不同优先级的状况；并且，它们都没有考虑到结合性的问题。
于是当年，在那遥远的河南荷兰，正在为实现ALGOL 60而忙碌的Dijkstra大神再也忍不住了。终于，他提出了调度场算法。
调度场算法
我们回到上篇，再次梳理一下问题。
这里只讨论关键的处理优先级、结合方向的部分，一个理想的算法应该能做到：
- 能处理优先级。
- 允许同一优先级的运算符从左向右或从右向左结合。
- 处理的耗时、内存占用（即时间、空间复杂度）与表达式长度趋向于正比。
- 可以接受较多的优先级、运算符个数，而复杂度不会显著增加。
另外，我们可以再加上两条：
- 尽可能只扫描表达式一遍。
- 允许在解析时，适度地动态添加运算符和规则。
好，继续观察例子：
1+(2+3)*4+5
首先需要注意，调度场算法是一种从左向右处理表达式、自底向上产生AST的算法。
考虑到AST中数字就是各个叶节点（最末端的节点），并且没有任何顺序变化，我们可以随时按需取用。因此，建立一个堆栈，遇到数字就直接放入。
输入：+(2+3)*4+5 数字堆栈：1
接下来，我们回想一下之前说到的朴素的算法，可以发现，优先级较低的运算符可能需要较晚地被处理：
- 在第一种算法中，第二轮扫描中才能处理乘法，第三轮扫描中才能处理加法。
- 第二种算法在处理过程中虽然不涉及顺序，但是在之后的计算中，优先级越低的运算符周围的括号越多，它们的执行被放在了递归外层，因此较晚。
调度场算法给出的解法是，建立一个堆栈，先行存储暂时还不需要处理的运算符：
输入：(2+3)*4+5 数字堆栈：1 符号堆栈：+
题外话，这个符号堆栈就是所谓的“调度场”。
“调度场”，是一个来自铁路的术语，又叫“编组站”。作为一个外行的我的理解下，调度场是一种主要用于货运调度、兼可以负责各种技术向的任务（比如维修）的车站。
左括号先压着，以等待右括号的到来：
输入：2+3)*4+5 数字堆栈：1 符号堆栈：+ (
继续：
输入：+3)*4+5 数字堆栈：1 2 符号堆栈：+ (
输入：3)*4+5 数字堆栈：1 2 符号堆栈：+ ( +
输入：)*4+5 数字堆栈：1 2 3 符号堆栈：+ ( +
好，看到右括号了。它会把左括号之后的一切弹出：
输入：*4+5 数字堆栈：1 2 3 符号堆栈：+ 弹出：+
括号对的使命结束，弹出的是一个加号。
对于双目符号的弹出操作，我们首先从数字堆栈取出两个数，执行计算，放回一个数：
输入：*4+5 数字堆栈：1 5 符号堆栈：+
继续，看到乘号。此时，符号堆栈顶端是一个加号，加号优先级较低，我们直接压入乘号：
输入：4+5 数字堆栈：1 5 符号堆栈：+ *
压入数字：
输入：+5 数字堆栈：1 5 4 符号堆栈：+ *
然后，调度场算法的关键步骤来了——下一个是加号——加号比乘号的优先级低，因此弹出乘号：
输入：5 数字堆栈：1 5 4 符号堆栈：+ 弹出：* 待压入：+
加号和堆栈内的加号具有相同的优先级，因此弹出堆栈内的加号：
输入：5 数字堆栈：1 20 弹出：+ 待压入：+
输入：5 数字堆栈：21 弹出：+ 待压入：+
现在可以压入了：
输入：5 数字堆栈：21 符号堆栈：+
之后，输入5，输入结束：
数字堆栈：21 5 符号堆栈：+
我们弹出符号堆栈中的符号：
数字堆栈：26
于是得到结果。
可以发现，如果在上面的过程中不执行计算，直接将数字和出栈的符号依次输出，我们就会得到后缀表达式；而如果计算时不是进行数学运算，而是生成一个二叉树节点，以符号为父节点，取出两个数字堆栈的成员为子节点并压回数字堆栈，我们就会得到AST。
我们可以体会到，调度场算法的核心就在于用堆栈暂存符号以备“调度”，比较新符号和栈顶原有的符号，选择其中更容易结合的（根据优先级、结合方向）出栈——更容易结合就意味着更早地参与计算。理解这点以后，调度场算法就仿佛显而易见、理所当然地存在了。
OPParser中出现的变种
OPParser中，我原本打算直接使用调度场算法。但是考虑到语法中一些复杂细节的处理，为了方便编写代码，对调度场算法做了一些改变。
改变的关键点在于：
- 数字、括号，其实可以看作运算符，只是数字出栈比所有运算符更优先。
- 运算符向左、向右的优先级可以不同。
在头文件中，定义了如下的优先级：
1 const Level levelConst = 4095;
2 const Level levelAcceptAll = 0;
3 const Level levelFlushAll = 1;
4 const Level levelAddSubL = 255;
5 const Level levelAddSubR = 256;
6 const Level levelMulDivL = 511;
7 const Level levelMulDivR = 512;
8 const Level levelIMulL = 639;
9 const Level levelIMulR = 640;
10 const Level levelPwrL = 769;
11 const Level levelPwrR = 768;
12 const Level levelFacL = 1023;
13 const Level levelFuncR = 1280;左括号左侧、右括号右侧，使用与数字相同的优先级；左括号右侧和表达式开头（栈底）的优先级最低，表达式右侧和表达式结尾的优先级仅高于前者。
参照着这些定义，我们可以对表达式进行标注：
1 1+(2+3)*4+5
2
3 begin[0]
4 [4095]1[4095] [255]+[256] [4095]([0]
5 [4095]2[4095] [255]+[256] [4095]3[4095]
6 [1])[4095] [511]*[512] [4095]4[4095] [255]+[256] [4095]5[4095]
7 [1]end这样，我们就可以用同一套规则处理数字、运算符和括号了。
然后，从左到右压栈，比较栈顶符号的右侧优先级和新符号的左侧优先级，弹出较高的符号……不必多说，直接单步运行一遍吧：
1 begin[0] [4095]1[4095] [255]+[256] ...
2 Stack ^ Input
3
4 begin[0] [4095]1[4095] [255]+[256] [4095]([0] ...
5 Stack ^ Input
6
7 begin[0] [***********] [255]+[256] [4095]([0] ...
8 Stack ^ Input Output: 1
9
10 begin[0] [255]+[256] [4095]([0] ...
11 Stack ^ Input Output: 1
12
13 begin[0] [255]+[256] [4095]([0] [4095]2[4095] ...
14 Stack ^ Input Output: 1
15
16 begin[0] [255]+[256] [4095]([0] [4095]2[4095] [255]+[256] ...
17 Stack ^ Input Output: 1
18
19 begin[0] [255]+[256] [4095]([0] [4095]2[4095] [255]+[256] [4095]3[4095] ...
20 Stack ^ Input Output: 1
21
22 begin[0] [255]+[256] [4095]([0] [***********] [255]+[256] [4095]3[4095] ...
23 Stack ^ Input Output: 1 2
24
25 begin[0] [255]+[256] [4095]([0] [255]+[256] [4095]3[4095] ...
26 Stack ^ Input Output: 1 2
27
28 begin[0] [255]+[256] [4095]([0] [255]+[256] [4095]3[4095] [1])[4095] ...
29 Stack ^ Input Output: 1 2
30
31 begin[0] [255]+[256] [4095]([0] [255]+[256] [4095]3[4095] [1])[4095] [511]*[512] ...
32 Stack ^ Input Output: 1 2
33
34 begin[0] [255]+[256] [4095]([0] [255]+[256] [***********] [1])[4095] [511]*[512] ...
35 Stack ^ Input Output: 1 2 3
36
37 begin[0] [255]+[256] [4095]([0] [*********] [1])[4095] [511]*[512] ...
38 Stack ^ Input Output: 1 2 3 +
39
40 begin[0] [255]+[256] [4095]([0] [1])[4095] [511]*[512] ...
41 Stack ^ Input Output: 1 5
42
43 begin[0] [255]+[256] [*******************] [511]*[512] [4095]4[4095] ...
44 Stack ^ Input Output: 1 5
45
46 begin[0] [255]+[256] [511]*[512] [4095]4[4095] [255]+[256] [4095]5[4095] [1]end
47 Stack ^ Input Output: 1 5
48
49 begin[0] [255]+[256] [511]*[512] [4095]4[4095] [255]+[256] [4095]5[4095] [1]end
50 Stack ^ Input Output: 1 5
51
52 begin[0] [255]+[256] [511]*[512] [4095]4[4095] [255]+[256] [4095]5[4095] [1]end
53 Stack ^ Input Output: 1 5
54
55 begin[0] [255]+[256] [511]*[512] [***********] [255]+[256] [4095]5[4095] [1]end
56 Stack ^ Input Output: 1 5 4
57
58 begin[0] [255]+[256] [*********] [255]+[256] [4095]5[4095] [1]end
59 Stack ^ Input Output: 1 5 4 *
60
61 begin[0] [255]+[256] [255]+[256] [4095]5[4095] [1]end
62 Stack ^ Input Output: 1 20
63
64 begin[0] [*********] [255]+[256] [4095]5[4095] [1]end
65 Stack ^ Input Output: 1 20 +
66
67 begin[0] [255]+[256] [4095]5[4095] [1]end
68 Stack ^ Input Output: 21
69
70 begin[0] [255]+[256] [4095]5[4095] [1]end
71 Stack ^ Input Output: 21
72
73 begin[0] [255]+[256] [4095]5[4095] [1]end
74 Stack ^ Input Output: 21
75
76 begin[0] [255]+[256] [***********] [1]end
77 Stack ^ Input Output: 21 5
78
79 begin[0] [*********] [1]end
80 Stack ^ Input Output: 21 5 +
81
82 begin[0] [1]end
83 Stack ^ Input Output: 26最后得到答案。
补充一点，括号还有一种更简单的处理方式——我们设一个变量x，每遇到一个左括号就将它加上一个大数，遇到右括号则减去那个大数，然后对每个符号的左、右优先级，分别加上x即可。
经过上中下三篇至此，本文终于接近尾声了。
我们应当能体会到，调度场算法的解析能力有一定的局限性。现在常见的编程语言通常具有更复杂的语法，因此通常会使用由以Yacc为代表的“编译器的编译器”自动生成的LR Parser。不过，调度场算法易于理解，也很适合手工编写，不失为一个居家旅行杀人灭口学习编程的好工具。
>>> 调度场算法（Shunting-yard Algorithm）（下篇）
>>>> 调度场算法（Shunting-yard Algorithm）（中篇）
http://hczhcz.github.io - © 2014 hcz - Powered by Jekyll - Posts released under CC BY-SA 4.0