我们从小学习算术的时候便知道「四则(加、减、乘、除)运算」的规则,也就是「先乘除、后加减,以及括号先算」。那么如果我们要撰写一个可以支持算式输入且能够按照四则运算规则求出结果的程序,该怎么做呢?

在开始撰写程序前,要先来介绍一下前序(Prefix Notation)、中序(Infix Notation)和后序(Postfix Notation)的算式,它们差别是在操作符(operator,如 +、-、*、/)和操作数(operand,如 12、-3)的放置顺序。我们脑袋习惯使用的是中序算式,例如「1 加 2」,写作 1 + 2。若是要用前序算式来表示「1 加 2」,要写成 + 1 2;若是要用后序算式来表示「1 加 2」,要写成 1 2 +。

顺序整理如下:

前序:操作符 操作数 操作数
中序:操作数 操作符 操作数
后序:操作数 操作数 操作符

之所以会在中序之外又多了前序和后序,是为了方便电脑程序进行运算,因为前序和后序不像中序这样有操作符优先权以及括号内的算式要先算的问题。前序只要从右边算到左边,而后序更只要单纯从左边算到右边就好了。

前序式又称 Polish Notation (PN) 或 Normal Polish Notation (NPN);后序式又称 Reverse Polish Notation (RPN)。

前序式、中序式、后序式的运算方式

前序式的运算

对于前序式,我们要从右边往左边看。

以 - + 2 * 3 1 9 这个前序式来举例。

首先要从右往左边找到连续的两个操作数和一个操作符,将它们做运算。- + 2 * 3 1 9,会先看到 * 3 1,将其作「三乘一」的运算(注意这边不是「一乘三」)后放回原本的前序式取代掉 * 3 1,所以此时待计算的前序式会变成 - + 2 3 9。

接着以同样的方式,再从右往左看,找到连续的两个操作数和一个操作符,将它们做运算。- + 2 3 9,会先看到 + 2 3,将其作「二加三」的运算(注意这边不是「三加二」)后放回原本的前序式取代掉 + 2 3,所以此时待计算的前序式会变成 - 5 9。

然后还是以同样的方式,再从右往左看,找到连续的两个操作数和一个操作符,将它们做运算。由于只剩下 - 5 9,将其作「五减九」的运算(注意这边不是「九减五」)后就是答案(-4)了。

中序式的运算

对于中序式,我们要从左边往右边看,从括号内往括号外看,且先乘除后加减。

以 2 * (3 + 1) - 5 * 3 这个中序式来举例。

其实大家如果有念过小学的话应该都知道要怎么算中序式,这边就不再鸡婆多做介绍了。以下是 2 * (3 + 1) - 5 * 3 的计算过程:

#{{{
\begin{alignedat}{2}
2 &{}\times{}&& (3 + 1) - 5 \times 3 \\
&{}={}&& 2 \times 4 - 5 \times 3 \\
&{}={}&& 8 - 5 \times 3 \\
&{}={}&& 8 - 15 \\
&{}={}&& -7
\end{alignedat}
}}}#
后序式的运算

对于后序式,我们要从左边往右边看。

以 2 3 1 * + 9 - 这个后序式来举例。

首先要从左边往右边找到连续的两个操作数和一个操作符,将它们做运算。2 3 1 * + 9 -,会先看到 3 1 *,将其作「三乘一」的运算后放回原本的后序式取代掉 3 1 *,所以此时待计算的后序式会变成 2 3 + 9 -。

接着以同样的方式,再从左往右看,找到连续的两个操作数和一个操作符,将它们做运算。2 3 + 9 -,会先看到 2 3 +,将其作「二加三」的运算后放回原本的后序式取代掉 2 3 +,所以此时待计算的后序式会变成 5 9 -。

然后还是以同样的方式,再从左往右看,找到连续的两个操作数和一个操作符,将它们做运算。由于只剩下 5 9 -,将其作「五减九」的运算后就是答案(-4)了。

前序式、中序式、后序式的转换

前序、中序和后序算式是可以互相转换的。

中序式转后序式

按照四则运算顺序,将中序式的所有操作符和其两侧的操作数用括号括起来。例如 a + b * c - d / e,会变成 ( ( a + ( b * c ) ) - ( d / e ) )。

接着从最外层括号开始,将右括号取代为括号中间的操作符,移除原来的操作符,并消除原本右括号对应的左括号。完整步骤如下:

( ( a + ( b * c ) ) - ( d / e ) )
  ( a + ( b * c ) )   ( d / e ) -
    a   ( b * c ) +   ( d / e ) -
    a     b   c * +   ( d / e ) -
    a     b   c * +     d   e / -

如此一来,中序式 a + b * c - d / e 就转成后序式 a b c * + d e / - 了!

后序式转中序式

从左边开始寻找不在括号内的操作符,将找到的操作符移动到其左边的两个操作数(或者已被括号的子算式)中间,并加上括号,直到式子已看到最右边了。以 a b c * + d e / - 来举例,完整步骤如下:

    a     b   c * +     d   e / -
    a   ( b * c ) +     d   e / -
  ( a + ( b * c ) )     d   e / -
  ( a + ( b * c ) )   ( d / e ) -
( ( a + ( b * c ) ) - ( d / e ) )

如此一来,后序式 a b c * + d e / - 就转成中序式 ( ( a + ( b * c ) ) - ( d / e ) ) 了!

中序式转前序式

按照四则运算顺序,将中序式的所有操作符和其两侧的操作数用括号括起来。例如 a + b * c - d / e,会变成 ( ( a + ( b * c ) ) - ( d / e ) )。

接着从最外层括号开始,将左括号取代为括号中间的操作符,移除原来的操作符,并消除原本左括号对应的右括号。完整步骤如下:

( ( a + ( b * c ) ) - ( d / e ) )
- ( a + ( b * c ) )   ( d / e )  
- + a   ( b * c )     ( d / e )  
- + a   * b   c       ( d / e )  
- + a   * b   c       / d   e    

如此一来,中序式 a + b * c - d / e 就转成前序式 - + a * b c / d e 了!

前序式转中序式

从右边开始寻找不在括号内的操作符,将找到的操作符移动到其右边的两个操作数(或者已被括号的子算式)中间,并加上括号,直到式子已看到最左边了。以 - + a * b c / d e 来举例,完整步骤如下:

- + a   * b   c       / d   e    
- + a   * b   c       ( d / e )  
- + a   ( b * c )     ( d / e )  
- ( a + ( b * c ) )   ( d / e )  
( ( a + ( b * c ) ) - ( d / e ) )

如此一来,前序式 - + a * b c / d e 就转成中序式 ( ( a + ( b * c ) ) - ( d / e ) ) 了!

后序式转前序式

从左边开始寻找不在括号内的操作符,将找到的操作符移动到其左边的两个操作数(或者已被括号的子算式)之前,并加上括号,直到式子已看到最右边了,把所有括号移除掉。以 a b c * + d e / - 来举例,完整步骤如下:

        a     b  c * +     d e / -
        a ( * b  c ) +     d e / -
(     + a ( * b  c ) )     d e / -
(     + a ( * b  c ) ) ( / d e ) -
( - ( + a ( * b  c ) ) ( / d e ) )
  -   + a   * b  c       / d e    

如此一来,后序式 a b c * + d e / - 就转成前序式 - + a * b c / d e 了!

前序式转后序式

从右边开始寻找不在括号内的操作符,将找到的操作符移动到其右边的两个操作数(或者已被括号的子算式)之后,并加上括号,直到式子已看到最左边了,把所有括号移除掉。以 - + a * b c / d e 来举例,完整步骤如下:

- + a * b c         / d e        
- + a * b c         ( d e / )    
- + a ( b c * )     ( d e / )    
- ( a ( b c * ) + ) ( d e / )    
( ( a ( b c * ) + ) ( d e / ) - )
    a   b c *   +     d e /   -  

如此一来,前序式 - + a * b c / d e 就转成后序式 a b c * + d e / - 了!

二元树(Binary Tree)与前、中、后序式的转换

中序式 a + b 可以很容易地用二元树来表示。如下:

  +
 / \
a   b

更复杂的中序式,像是 a + b * c - d / e 的二元树长成以下这个样子:

        -
       / \
      /   \
     /     \
    +       /
   / \     / \
  a   *   d   e
     / \
    b   c

若您看不太懂 a + b * c - d / e 是怎么画出上面的二元树,不妨按照四则运算的顺序将它加上括号,使其变成 ( ( a + ( b * c ) ) - ( d / e ) )。一棵子树就是一组括号内的算式。

喔,二元树画出来了,然后呢?这有什么用?

有了这棵二元树,我们就可以利用不同的走访方式,来快速找出其等效的中序式、前序式和后序式。

走访二元树时,可以分为三种动作:L 表示往左边的子节点移动(从该节点进入);R 表示往右边的子节点移动;V 表示访问目前节点(取得目前节点的值)。所以在排列组合后,二元树会有六种走访方式:LVR、LRV、VLR、VRL、RVL、RLV,其中,LVR 其实就是中序式的顺序(inorder);VLR 是前序式的顺序(preorder);LRV 是后序式的顺序(postorder)。

用更简单的例子来解释:

  +
 / \
a   *
   / \
  b   c

从上树的根(root)节点 + 开始进行 LVR 走访的话,一开始会先进入根节点 + 的左边子节点 a (L+)。节点 a 没有左边子节点能进入(La 无法运行),直接开始访问节点 a (Va),然后节点 a 也没有右边子节点能进入(Ra 无法运行)。此时根节点 + 的左边子节点 a 就看完了,开始访问根节点 + (V+),然后进入右边的子节点 * (R+),节点 * 有左边子节点 b 能进入(L*)。节点 b 没有左边子节点能进入(Lb 无法运行),直接开始访问节点 b (Vb),然后节点 b 也没有右边子节点能进入(Rb 无法运行)。此时节点 * 的左边子节点 b 就看完了,开始访问节点 * (V*),然后进入右边的子节点 c (R*)。节点 c 没有左边子节点能进入(Lc 无法运行),直接开始访问节点 c (Vc),然后节点 c 也没有右边子节点能进入(Rc 无法运行)。此时 * 的右边子节点 c 就看完了,也就是说根节点 + 的右边子节点 * 也看完了。走访结束。

按照访问过的节点顺序,我们可以得到 a + (b * c) 这样的中序式。VLR 和 LRV 走访方式也是依此类推,本质上它们都是属于深度优先搜索。

参考以下代码来理解 preorder、inorder 和 postorder 的差别:

把递归的 preorder、inorder 和 postorder 函数改成迭代版本的方式,可以参考这篇文章:

程序实作

了解前序式、中序式和后序式的运算方式和转换方式后,接下来就要探讨程序的作法。

后序式的运算

根据后序式的运算方式,我们可以创建出一个堆栈(Stack)空间,来保存(push)当从左往右看后序式时所遇到的操作数。如此一来,在遇到操作符的时候,只要 pop 出堆栈空间中(顶部)的两个操作数,就可以让它们做运算,并把运算结果再次 push 回堆栈空间中,接着再继续往右看后序式的操作符和操作数。当算式看完了,最后在堆栈空间中剩下的元素就是答案了!

于是我们可以撰写出以下程序:

前序式的运算

前序式运算的程序实作方式,只需要把原本后序式运算的代码之算式的读取方向颠倒,再把从堆栈空间中 pop 出来的操作数反过来运算就好了。

于是我们可以撰写出以下程序:

后序式转前序式

如果不在乎输出的结果会把操作符和操作数混在一起成为一个字符串的话,后序式转前序式的程序实作只需要一个堆栈空间就可以完成了。作法有点类似后序式运算那样:看到操作数就把操作数 push 进堆栈空间中,看到操作符就从堆栈空间中 pop 出两个操作数,进行字符串的串接(串接成「操作符 操作数 操作数」)后,再把新字符串 push 进堆栈空间中。当算式看完了,最后在堆栈空间中剩下的元素就是原后序式被转换后的前序式了!

于是我们可以撰写出以下程序:

如果输出要将各个操作符和操作数分开,可以让堆栈空间的每个元素去保存字符串数组,而不是字符串。程序修改如下:

前序式转后序式

前序式转后序式的程序实作方式,只需要把原本后序式转前序式的代码之算式的读取方向颠倒,再把从堆栈空间中 pop 出来的操作数反过来进行字符串的串接(串接成「操作数 操作数 操作符」)。

于是我们可以撰写出以下程序:

后序式转中序式,前序式转中序式

后序式转中序式的程序实作方式,只需要把原本后序式转前序式的代码的字符串串接方式改成「左括号 操作数 操作符 操作数 右括号」就好了。

前序式转中序式也是类似的方式,把原本前序式转后序式的代码的字符串串接方式改成「左括号 操作数 操作符 操作数 右括号」。

于是我们可以撰写出以下程序:

中序式转后序式

要实作中序式转后序式的程序,我们需要先设置操作符的优先权。根据四则运算的「先乘除、后加减」的规则,可以设置加与减的优先权为 1,乘、除的优先权为 2,数值愈高表示优先权愈高。当然我们也要让程序可以支持中序式使用括号来控制运算的顺序。

我们前面介绍的中序式转后序式的方式,其实不太容易使用程序实作出来。首先,光是要替中序式按照四则运算顺序加上括号就是个大问题了,因为我们就是为了要解决四则运算顺序的问题才会弄出后序式(和前序式)嘛!前面之所以会这样介绍,是因为人脑可以轻易找出中序式的运算顺序。但这对电脑来说,就有点困难了,所以我们要使用另一套算法来将中序式转成后序式。

重新观察中序式和后序式的关系,先看看以下这个例子:

#{{{
a + b \rightarrow a \text{ } b \text{ } +
}}}#

把我们自己当作电脑,从左边开始读取中序式。一开始会看到 a,我们可以直接输出 a。接着看到 +,先不要输出 +,把 + 存在内存中。然后看到 b,直接输出 b。最后发现中序式看到结尾了,输出内存中的 +。

然后看看以下这个例子:

#{{{
a + b - c \rightarrow a \text{ } b \text{ } + \text{ } c \text{ } -
}}}#

从左边开始读取中序式,一开始会看到 a,我们可以直接输出 a。接着看到 +,先不要输出 +,把 + 存在内存中。然后看到 b,直接输出 b。接着看到 -,输出内存中的 +,把 - 存在内存中。再来看到 c,直接输出 c。最后发现中序式看到结尾了,输出内存中的 -。

再来看看以下这个例子:

#{{{
a + b \times c \rightarrow a \text{ } b \text{ } c \text{ } \times \text{ } +
}}}#

从左边开始读取中序式,一开始会看到 a,我们可以直接输出 a。接着看到 +,先不要输出 +,把 + 存在内存中。然后看到 b,直接输出 b。接着看到 *,先不要输出 *……咦?这边为什么跟上一个例子不一样?因为目前读到的操作符 * 之优先权比内存中上一个读到的 + 之优先权还要大嘛!后比前大,所以要再把这个 * 存进内存。再来看到 c,直接输出 c。最后发现中序式看到结尾了,输出内存中的 * 和 +,先进后出(堆栈)。

观察到这里想必聪明的各位脑中都大概有程序该如何实作的雏型了。

我们再看看下面这个例子:

#{{{
a + b \times c - d \rightarrow a \text{ } b \text{ } c \text{ } \times + \text{ } d \text{ } -
}}}#

从左边开始读取中序式,一开始会看到 a,我们可以直接输出 a。接着看到 +,先不要输出 +,把 + 存在内存中。然后看到 b,直接输出 b。接着看到 *,先不要输出 *,把 * 存在内存中。再来看到 c,直接输出 c。接着看到 -,因为 - 的优先权没有比内存中上一个读到的 * 还要大(小于或等于),所以要输出内存中的 * 和 +,并把 - 存在内存中。继续看到 d,直接输出 d。最后发现中序式看到结尾了,输出内存中的 -。

写成程序如下:

以上程序用了堆栈来保存要被放进内存中的操作符。虽然我们实作了程序,但是,我们目前得出的算法其实是有问题的。

以下面这个例子来举例:

#{{{
a + b \times c \div d \rightarrow a \text{ } b \text{ } c \times d \text{ } \div \text{ } +
}}}#

试着用我们刚才得出的算法来看中序式。一开始会看到 a,我们可以直接输出 a。接着看到 +,先不要输出 +,把 + 存在内存中。然后看到 b,直接输出 b。接着看到 *,先不要输出 *,把 * 存在内存中。再来看到 c,直接输出 c。接着看到 /,因为 / 的优先权没有比内存中上一个读到的 * 还要大,所以要输出内存中的 * 和 +,并把 / 存在内存中……算法到这边就错了,因为 + 不能在此时被输出。也就是说,当我们遇到目前读到的操作符没有比内存中上一个读到的操作符还要大时,虽然确实是要按照先进后出的顺序去输出内存中的操作符没错,但是每次都要去判断目前读到的操作符之优先权是否比内存中正要被取出的操作符还大才行,如果是的话就停止输出,继续处理中序式的下一个操作符或是操作数。

若我们的操作符有三种以上的优先权的话(例如多了优先权比乘和除更高的乘幂 ^),原先的算法所产生的问题会更明显。

修正我们的算法后,代码如下:

再来我们要来处理中序式的括号了。我们都知道中序式的括号可以借由「分隔」子算式来改变运算顺序。看看以下的例子吧!

#{{{
\begin{alignedat}{2}
a + b - c &{}\rightarrow{}&& a \text{ } b \text{ } + \text{ } c \text{ } - \\
a + ( b - c ) &{}\rightarrow{}&& a \text{ } b \text{ } c \text{ } - \text{ } +
\end{alignedat}
}}}#

我们可以发现,把中序式转成后序式之后,括号外的操作符并不会被插进括号形成的子算式中,括号形成的子算式中的操作符也不会跑到外面去。

也就是说,我们可以利用括号来分隔堆栈空间中的操作符。让左括号必定能被放进堆栈,之后遇到要输出堆栈空间的操作符之情况时,最多只要输出到左括号就可以停止了。在中序式看到右括号就类似先前看到算式结尾那样,也要将堆栈空间中的操作符输出,但此时也是只要输出到左括号的位置就好了,不过要记得把碰到的左括号移出堆栈。

最终的代码如下:

中序式转前序式

中序式转前序式的程序实作方式,不能只把原本中序式转后序式的代码之算式的读取方向颠倒,再把左括号改成右括号、右括号改成左括号,最后将输出反转。程序如下:

这样的实作方式会让中序式的基本计算顺序变成由右向左。例如 a - b - c 就会变成 (a - (b - c)),等同于 a - b + c,会跟原算式不相等。所以如果写出以上的程序那就错了。(许多网站提供的代码或是网页计算机就是这种有问题的)

那怎么样写才是正确的呢?

其实应该也没什么比较好的方式,就先把中序式转成后序式,再用前面介绍的方式转成前序式吧!这也正是为什么我们几乎只会用后序式来做运算的原因(中序式比较不容易转前序式)。

程序如下:

中序式的运算

看到这里,各位应该也都知道要怎么用程序去算中序式了。不错,就是先将中序式转成后序式后再用前面介绍的方式去做计算。

创建二元树

用前序式和后序式创建二元树的方式并不难。作法类似前序式和后序式的运算,只不过我们不是要算出值,而是要创建出树的节点。

用后序式创建二元树
用前序式创建二元树
用中序式创建二元树

先将中序式用前面介绍的方式转成后序式后,再把后序式转成二元树。