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

调度场算法是一种用于解析中缀表达式的算法——处理1+2*3这种形式的输入，并得到其中各个运算符的关系。它可以用于输出后缀表达式或生成代码树（抽象代码树，AST）。它的一个变种出现在项目OPParser中，下面我们将它一层一层拨开，看看它是如何工作的。

中缀表达式

首先来说说中缀表达式。中缀表达式是我们~~喜闻乐见~~习以为常的以传统方式书写的表达式，它包含这样几类主要元素：

上面提到了优先级，优先级对于中缀表达式而言是一个很特别的概念。说它“特别”，其一是前缀、后缀表达式中不必规定运算符的优先级，唯独中缀表达式需要它，其二……为了这个优先级，我们需要做一些特别折腾的事，比如使用括号，也比如这篇文章所说的调度场算法。

我们来看看这个例子：

1+2*3

如果没有优先级之别，直接从左往右计算，那么它的结果是9。但我们通常会给予乘法运算更高的优先级，或者说让它更容易和左右的数字（或者常量、变量等）结合，也更早地进行运算。这就相当于：

(1+(2*3))

结果是7。

一个稍复杂一点的情况是，单目运算符也可能参与“争抢”数字（不禁感叹，数字MM简直就和某高校软妹纸学院的妹纸一样受欢迎……可是数字有很多的呀，又不像妹纸那么少TAT）：

-2.5!

然后还有一个问题——结合的方向。对于优先级相同的符号，甚至同一个符号，我们应该先从左边开始结合还是先从右边开始结合？

比如：

1-1-1

如果右侧的减号是优先结合的，那么结果就是1，这是违反我们使用数学表达式时的直觉的。我们一般规定正、负号从左向右进行结合。然而，乘方符号却约定俗成地从右向左进行结合。

这还会导致一些更复杂的问题，比如，如果同时存在优先级相同的左结合运算符和右结合运算符，那么我们应该如何处理它们之间的冲突呢？因此，我们在表达式的设计中通常会尽力避免这种情况发生。

Abstract Syntax Tree，抽象代码树。我们看到的代码，大部分都可以用AST来表示。

仍然以1+2*3为例，它可以构成一棵二叉树：

1 Root   +
2      /   \
3     1     *
4          / \
5         2   3
6 
7     1 + 2 * 3

~~加号没有垂直对齐，强迫症们对不起咯～哦哈哈哈～~~

为什么它是二叉树呢？

典型的中缀表达式有一个重要的特征——两个运算符之间最多隔着一个数字（常量、变量……）——还记得之前说的，运算符大叔是怎样抢占数字MM的么？

另一方面，我们可以将一对括号如(2*3)看成一个新的数字，假设它为x（x=6），那么1+(2*3)就成了1+x。我们知道，x和(2*3)在树中都可以作为一个节点下的子树。

于是，从中缀表达式到AST的过程，可以理解为：运算符争抢数字，结合，产生新的“数字”，再继续参与结合……最后只留下一个数字，就是计算结果。

那么，单目运算符又该如何处理呢？我们有两种理解方式：

考虑：

-2.5!

填上nil：

nil-2.5!nil

如果我们规定阶乘的优先级较高，它可以做如下结合：

(nil-(2.5!nil))

画成树就是：

1 Root    -
2       /   \
3     nil    !
4          /   \
5        2.5   nil

去掉nil得到：

另外，数字或常量、变量本身，可以理解为左右两侧都加上nil的运算符。

如果用上面对单目运算符的第二种理解方式，我们将结合能力标注为o，将被结合能力标注为x（我不是故意的=w=），那么：

1 1+2*3
2 x1x o+o x2x o*o x3x
3 x1x o+o x(2*3)x
4 x(1+(2*3))x
5 
6 -2.5!
7 x-o x2.5x o!x
8 x-o x(2.5!)x
9 x(-(2.5!))x

到这里，中缀表达式转换为AST的问题已经解决了大半，还差一点：我们如何来执行这个~~ooxx~~结合过程。

而对优先级、结合方向的处理，便是调度场算法的主要任务。在本文的中篇，我们会先用一些简单的办法解决优先级的问题。而调度场算法则在下篇中介绍。