在软件工程课中，有一个经典的作业题：实现一个小学四则运算器。当然，它有不少变种，比如要求学生预先生成合规的四则运算题目。但不论如何变形，此类问题都绕不开 Dijkstra 提出的调度场算法。
回顾问题
对于中国人来说，可能从小学学会四则运算开始，这件事情就变成了深入骨髓的本能。类似的问题，可能还有：人脸识别、性别判断等等。对于计算机而言，似乎有这样一个悖论：有一些对人而言非常自然和简单的事情，想要用有效的算法表示出来，就不那么容易。
比如，对于一个四则运算式子
1 | 1 + 2 * (3 + (4 + 5 - 6) * 2) |
对于人来说，可能一眼扫过去，就知道应该怎样运算。可是，当被问及下面这个问题的时候，人们就很难回答了：怎样让计算机理解你使用的算法，并有足够的通用性去解决普遍的四则运算问题（带括号）。但不论如何，我们还是要回到这个问题本身，尝试理清一下，我们究竟是怎样在大脑里处理四则运算的。
- 首先，我们定义了「先乘除、后加减」的优先级规则，所有的运算都应该遵循这个规则。
- 其次，对于有括号的式子，我们会找到括号层次最深的部分（在这里就是
4 + 5 - 6），按照上述规则进行计算，逐层脱去括号。等到没有括号的时候，再依据基本的规则计算最终结果。
有人可能会说：你看，其实还是很简单的嘛，几句话就说清楚了。其实不然，原因有几个：
- 对于人来说，可以一观全貌，因此可以轻易地找到括号嵌套最深的部分。但是对于计算机而言，必须逐个 token (numbers and operators) 地读入，经过一系列的判断才能确定嵌套最深的部分。
- 对于人来说，可以一观全貌，因此可以轻松地判断是否还有括号。但对于计算机而言，每次脱去一层括号的时候，都需要完整地将式子扫描一遍（或者将记录扫描一遍），才能确定这个问题。
稍有算法分析和设计经验的人，可能会很敏感地发现：这事儿复杂度很高。其实不光是算法复杂度很高，用程序设计语言描述算法这件事情本身就很复杂——你试过就知道，你需要写一大堆的 if-else 才能完成这一任务。甚至，还有我们未曾考虑的问题：如何判断确定式子的合法性（比如括号是否成对）。
人类的习惯与计算机的习惯
通过上面的说明，不难发现，这一件人类看起来相当简单的问题，对计算机来说不那么好处理。这话有些耳熟不是吗？哦，原来，在制作计算机之处，人们就发现用电路表示十进制运算，很困难。当然，这个问题早就解决了，因为人们发现，电路的通断很自然地就对应了二进制的 0 和 1。因此，在计算机内部，运算都是以二进制的形式展现的，只有到了呈现给人看的时候，才转换成十进制。这就引出了一个问题：十进制运算对人来说很自然，这是人类的习惯（因为人有十个手指，可能？），但是计算机看不懂；同时，二进制对于计算机来说很自然，这是计算机的习惯，但是人类读起二进制的 01 串，就费劲得很。
这件事情应该于我们有启发：处理带括号的四则运算这件事情，在计算机看来很复杂，究竟是因为问题本身困难？还是因为问题的形式不好？答案似乎是显而易见的——如果问题本身困难，那么人类也就无法快速学会四则运算了。所以，我们需要寻找问题的另一种展现形式。
中缀表达式与后缀表达式
之前我们举过例子，给了一个简单的四则运算式子。这个式子，还有我们过去见过的大部分数学式子，都是用中缀表达式呈现的。有这些例子打底，顾名思义，不难理解何谓中缀表达式：将操作符（加减乘除符号）置于操作数中间的算式表示法，就是中缀表示法；对应的算式就是中缀表达式。
刚才说到，中缀表达式在人类看起来很简单和直观，但是对于计算机而言就不那么方便处理了。为此，我们需要引入另一种算式的表示方法：后缀表达式（逆波兰表达式）。它的特点有：
- 操作符置于被操作数的后面；
- 不需要括号，也不需要定义优先级，只需从左到右依次计算即可。
显而易见，操作符置于什么地方本身并不能解决痛点，但是省略了括号和优先级，就能正确计算结果，才是对计算机来说最重要的特性。就刚才的式子来说，转换成后缀表达式应该是：
1 | 1 2 3 4 5 + 6 - 2 * + * + |
对计算机来说，它只需要从左向右扫描后缀表达式，每当遇到操作符的时候，就停下来，取出刚才读入的合适数量的操作数进行计算。而后它需要将计算结果放回序列，再重复整个步骤，直到完成计算就可以了。
现在的问题是，我们要如何快速有效地将中缀表达式转换成后缀表达式，以便计算机能够顺利处理。
调度场算法
理想的算法是怎样的？
事情总是从易到难，慢慢解决的。我们先看一个简单的例子，它不包含括号这种恼人的东西。
1 | 1 + 2 * 3 / 4 - 5 |
我们希望，一个完美的算法，能够从左往右扫描中缀表达式，然后就能得到等价的后缀表达式。虽然我们暂时不知道这个算法长什么样，不过我们可以先扫描试试看。
- 读入操作数
1，将它放在结果序列中 - 读入操作符
+，将它暂时保存在某个地方
尽管这个式子里，没有括号，但是仍然有操作符的优先级问题。现在，我们读入了操作符 +，问题就来了：我们不知道在 + 的后面，是否有优先级更高的操作符，会和它「争抢」操作数（也就是优先进行运算）。因此，我们不能将它直接放在结果序列中。因为，在后缀表达式中，操作符执行的顺序只取决于操作符在表达式中的顺序为止；如果我们将 + 直接放在结果序列中，那么即使后续有优先级更高的操作符出现，按照规则也只能先执行 +。因此，我们需要将 + 暂时保存在某个地方。
- 读入操作数
2，将它放在结果序列中 - 读入操作符
*，将它与那个地方最后的操作符+比较后，发现当前操作符的优先级更高
现在遇到了操作符 *，和「某个地方」最后的操作符 + 相比，* 的优先级更高。因此，在运算时，我们必须先执行 * 再执行 +。这毫无疑问。不过，尽管 * 的优先级更高，我们也依然无法保证后面是否会有更高优先级的运算符出现。因此我们仍然将 * 暂存。
- 读入操作数
3，将它放在结果序列中 - 读入操作符
/，将它与那个地方最后的操作符*比较后，发现二者优先级一致
现在我们遇到了 /，它的优先级与「那个地方」最后的操作符一致。我们知道 * 和 / 都是左结合的，也就是说，应该按顺序从左向右计算。所以，应该先计算 * 再计算 /。因此我们
- 将那个地方最后的运算符
*取出，放入结果序列 - 紧接着，将
/放入那个地方 - 读入操作数
4，将它放在结果序列中 - 读入操作符
-，与那个地方最后的操作符/比较，发现当前操作符的优先级更低
显而易见，当前操作符优先级低，就应该先进行 / 的计算。因此
- 将那个地方最后的运算符
/取出，放入结果序列 - 将当前操作符
-与那个地方最后的操作符+比较，发现二者优先级一致（遇到了熟悉的情况） - 将那个地方最后的运算符
+取出，放入结果序列 - 紧接着，将
-放入那个地方 - 读入操作数
5，放入结果序列 - 读入完毕，将那个地方剩余的操作符
-取出，于是得到
1 | 1 2 3 * 4 / + 5 - |
完美！总结一下，我们不难发现整个流程有以下一些特点：
- 每次遇到操作数，都直接放入结果序列；
- 每次遇到操作符，都要与那个地方做比较，当
a. 当前操作符优先级较高，则将当前操作符放进那个地方；否则，
b. 将那个地方最后的操作符取出并放入结果序列，并将当前操作符放进那个地方 - 结果序列是顺序填充的，一旦填充就确定位置不会更改；
- 那个地方挺神秘的，不过
a. 任意时刻，那个地方先进去的操作符总是在优先级上低于后进去的操作符；因此
b. 在从那个地方取出操作符的时候，总是先取出后进去的操作符
不难发现，「那个地方」所具有的性质，就是一个栈所具有的性质。因此，我们说，在这套流程里，我们需要一个栈作为辅助的数据结构，而作为结果序列，则只需要一个顺序表即可。我们将整个过程整理如下。
| 输入 | 动作 | 输出 | 操作符栈 | 说明 |
|---|---|---|---|---|
| 1 | 将操作数加入输出队列 | 1 | ||
| + | 操作符压栈 | 1 | + | |
| 2 | 将操作数加入输出队列 | 1 2 | + | |
| \* | 操作符压栈 | 1 2 | + \* | 当前操作符优先级高于栈顶 |
| 3 | 将操作数加入输出队列 | 1 2 3 | + \* | |
| / | 操作符弹栈入列 | 1 2 3 \* | + | 当前操作符优先级与栈顶相等 |
| 操作符压栈 | 1 2 3 \* | + / | 当前操作符优先级高 | |
| 4 | 将操作数加入输出队列 | 1 2 3 \* 4 | + / | |
| - | 操作符弹栈入列 | 1 2 3 \* 4 / | + | 当前操作符优先级低于栈顶 |
| 操作符弹栈入列 | 1 2 3 \* 4 / + | 当前操作符优先级与栈顶相等 | ||
| 操作符压栈 | 1 2 3 \* 4 / + | - | ||
| 5 | 将操作数加入输出队列 | 1 2 3 \* 4 / + 5 | - | |
| EOL | 弹栈入列至空 | 1 2 3 \* 4 / + 5 - |
又有来自 Wikipedia 的图解（类似但不完全相同的问题）
由 Salix alba - 自己的作品，CC BY-SA 3.0，链接
从图解中不难看出，操作符栈的行为，与供火车检修用和调度用的调度场非常相似，所以这个算法得名「调度场算法（Shunting Yard Algorithm）」.
算法描述
经过了上面的分析，你应该已经对调度场算法有了大致的了解。剩余的内容，就是如何将括号，以及右结合的操作符纳入考量范围的过程了。不过，有了上面详细的分析，这些都不难。因此，这里就直接给出算法描述。
- 读入一个记号，直到无记号可读
- 如果记号是操作数，则加入输出队列
- 如果记号是操作符，记作 $O_c$
- 若 $O_c$ 是左结合的且优先级不高于栈顶，或者 $O_c$ 是右结合的且优先级低于栈顶，则弹栈入列，直到条件被打破；
- $O_c$ 压栈
- 如果记号是左括号，则压栈
- 如果记号是右括号，则
- 弹栈入列，直到遇见左括号
- 弹栈，丢弃左括号
- 若遇见左括号之前，栈为空，则括号不匹配（右括号多）
- 无记号可读时
- 弹栈入列，直至栈空
- 若栈空之前遇见左括号，则括号不匹配（左括号多）
