调度场算法

在软件工程课中,有一个经典的作业题:实现一个小学四则运算器。当然,它有不少变种,比如要求学生预先生成合规的四则运算题目。但不论如何变形,此类问题都绕不开 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 -

完美!总结一下,我们不难发现整个流程有以下一些特点:

  1. 每次遇到操作数,都直接放入结果序列;
  2. 每次遇到操作符,都要与那个地方做比较,当
    a. 当前操作符优先级较高,则将当前操作符放进那个地方;否则,
    b. 将那个地方最后的操作符取出并放入结果序列,并将当前操作符放进那个地方
  3. 结果序列是顺序填充的,一旦填充就确定位置不会更改;
  4. 那个地方挺神秘的,不过
    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$ 压栈
    • 如果记号是左括号,则压栈
    • 如果记号是右括号,则
      • 弹栈入列,直到遇见左括号
      • 弹栈,丢弃左括号
      • 若遇见左括号之前,栈为空,则括号不匹配(右括号多)
  • 无记号可读时
    • 弹栈入列,直至栈空
    • 若栈空之前遇见左括号,则括号不匹配(左括号多)

您的鼓励是我写作最大的动力

俗话说,投资效率是最好的投资。 如果您感觉我的文章质量不错,读后收获很大,预计能为您提高 10% 的工作效率,不妨小额捐助我一下,让我有动力继续写出更多好文章。


撰写评论

写了这么多年博客,收到的优秀评论少之又少。在这个属于 SNS 的时代也并不缺少向作者反馈的渠道。因此,如果你希望撰写评论,请发邮件至我的邮箱并注明文章标题,我会挑选对读者有价值的评论附加到文章末尾。