我們從小學習算術的時候便知道「四則(加、減、乘、除)運算」的規則,也就是「先乘除、後加減,以及括號先算」。那麼如果我們要撰寫一個可以支援算式輸入且能夠按照四則運算規則求出結果的程式,該怎麼做呢?



在開始撰寫程式前,要先來介紹一下前序(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,所以此時待計算的前序式會變成- 6 9

然後還是以同樣的方式,再從右往左看,找到連續的兩個運算子和一個運算元,將它們做運算。由於只剩下- 6 9,將其作「六減九」的運算(注意這邊不是「九減六」)後就是答案(-4)了。

中序式的運算

對於中序式,我們要從左邊往右邊看,從括號內往括號外看,且先乘除後加減。

2 * (3 + 1) - 5 * 3這個中序式來舉例。

其實大家如果有念過小學的話應該都知道要怎麼算中序式,這邊就不再雞婆多做介紹了。以下是2 * (3 + 1) - 5 * 3的計算過程:

#{{{
\begin{eqnarray}
2 &\times& (3 + 1) - 5 \times 3 \nonumber \\
&=& 2 \times 4 - 5 \times 3 \nonumber \\
&=& 8 - 5 \times 3 \nonumber \\
&=& 8 - 15 \nonumber \\
&=& -7
\end{eqnarray}
}}}#
後序式的運算

對於後序式,我們要從左邊往右邊看。

2 3 1 * + 9 -這個後序式來舉例。

首先要從左邊往右邊找到連續的兩個運算子和一個運算元,將它們做運算。2 3 1 * + 9 -,會先看到3 1 *,將其作「三乘一」的運算後放回原本的後序式取代掉3 1 *,所以此時待計算的後序式會變成2 3 + 9 -

接著以同樣的方式,再從左往右看,找到連續的兩個運算子和一個運算元,將它們做運算。2 3 + 9 -,會先看到2 3 +,將其作「二加三」的運算後放回原本的後序式取代掉2 3 +,所以此時待計算的前序式會變成6 9 -

然後還是以同樣的方式,再從左往右看,找到連續的兩個運算子和一個運算元,將它們做運算。由於只剩下6 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無法執行)。此時*的右邊子節點b就看完了,也就是說根節點+的右邊子節點*也看完了。走訪結束。

按照訪問過的節點順序,我們可以得到a + (b * c)這樣的中序式。VLR和LRV走訪方式也是依此類推,本質上它們都是屬於深度優先搜尋

參考以下程式碼來理解preorderinorderpostorder的差別:

把遞迴的preorderinorderpostorder函數改成迭代版本的方式,可以參考這篇文章:

https://magiclen.org/recursive-to-iterative/

程式實作

了解前序式、中序式和後序式的運算方式和轉換方式後,接下來就要探討程式的作法。

後序式的運算

根據後序式的運算方式,我們可以建立出一個堆疊(Stack)空間,來儲存(push)當從左往右看後序式時所遇到的運算元。如此一來,在遇到運算子的時候,只要pop出堆疊空間中(頂部)的兩個運算元,就可以讓它們做運算,並把運算結果再次push回堆疊空間中,接著再繼續往右看後序式的運算子和運算元。當算式看完了,最後在堆疊空間中剩下的元素就是答案了!

於是我們可以撰寫出以下程式:

前序式的運算

前序式運算的程式實作方式,只需要把原本後序式運算的程式碼之算式的讀取方向顛倒,再把從堆疊空間中pop出來的運算元反過來運算就好了。

於是我們可以撰寫出以下程式:

後序式轉前序式

如果不在乎輸出的結果會把運算子和運算元混在一起成為一個字串的話,後序式轉前序式的程式實作只需要一個堆疊空間就可以完成了。作法有點類似後序式運算那樣:看到運算元就把運算元push進堆疊空間中,看到運算子就從堆疊空間中pop出兩個運算元,進行字串的串接(串接成「運算子 運算元 運算元」)後,再把新字串push進堆疊空間中。當算式看完了,最後在堆疊空間中剩下的元素就是原後序式被轉換後的前序式了!

於是我們可以撰寫出以下程式:

如果輸出要將各個運算子和運算元分開,可以讓堆疊空間的每個元素去儲存字串陣列,而不是字串。程式修改如下:

前序式轉後序式

前序式轉後序式的程式實作方式,只需要把原本後序式轉前序式的程式碼之算式的讀取方向顛倒,再把從堆疊空間中pop出來的運算元反過來進行字串的串接(串接成「運算元 運算元 運算子」)。

於是我們可以撰寫出以下程式:

後序式轉中序式,前序式轉中序式

後序式轉中序式的程式實作方式,只需要把原本後序式轉前序式的程式碼的字串串接方式改成「左括號 運算元 運算子 運算元 右括號」就好了。

前序式轉中序式也是類似的方式,把原本前序式轉後序式的程式碼的字串串接方式改成「左括號 運算元 運算子 運算元 右括號」。

於是我們可以撰寫出以下程式:

中序式轉後序式

要實作中序式轉後序式的程式,我們需要先設定運算子的優先權。根據四則運算的「先乘除、後加減」的規則,可以設定加與減的優先權為0,乘、除的優先權為1,數值愈高表示優先權愈高。當然我們也要讓程式可以支援中序式使用括號來控制運算的順序。

我們前面介紹的中序式轉後序式的方式,其實不太容易使用程式實作出來。首先,光是要替中序式按照四則運算順序加上括號就是個大問題了,因為我們就是為了要解決四則運算順序的問題才會弄出後序式(和前序式)嘛!前面之所以會這樣介紹,是因為人腦可以輕易找出中序式的運算順序。但這對電腦來說,就有點困難了,所以我們要使用另一套演算法來將中序式轉成後序式。

重新觀察中序式和後序式的關係,先看看以下這個例子:

#{{{
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{eqnarray}
a + b - c &\rightarrow& a \text{ } b \text{ } + \text{ } c \text{ } - \nonumber \\
a + ( b - c ) &\rightarrow& a \text{ } b \text{ } c \text{ } - \text{ } +
\end{eqnarray}
}}}#

我們可以發現,把中序式轉成後序式之後,括號外的運算子並不會被插進括號形成的子算式中,括號形成的子算式中的運算子也不會跑到外面去。

也就是說,我們可以利用括號來分隔堆疊空間中的運算子。讓左括號必定能被放進堆疊,之後遇到要輸出堆疊空間的運算子之情況時,最多只要輸出到左括號就可以停止了。在中序式看到右括號就類似先前看到算式結尾那樣,也要將堆疊空間中的運算子輸出,但此時也是只要輸出到左括號的位置就好了,不過要記得把碰到的左括號移出堆疊。

最終的程式碼如下:

中序式轉前序式

中序式轉前序式的程式實作方式,不能只把原本中序式轉後序式的程式碼之算式的讀取方向顛倒,再把左括號改成右括號、右括號改成左括號,最後將輸出反轉。程式如下:

這樣的實作方式會讓中序式的基本計算順序變成由右向左。例如a - b - c就會變成(a - (b - c)),等同於a - b + c,會跟原算式不相等。所以如果寫出以上的程式那就錯了。(許多網站提供的程式碼或是網頁計算機就是這種有問題的)

那怎麼樣寫才是正確的呢?

其實應該也沒什麼比較好的方式,就先把中序式轉成後序式,再用前面介紹的方式轉成前序式吧!這也正是為什麼我們幾乎只會用後序式來做運算的原因(中序式比較不容易轉前序式)。

程式如下:

中序式的運算

看到這裡,各位應該也都知道要怎麼用程式去算中序式了。不錯,就是先將中序式轉成後序式後再用前面介紹的方式去做計算。

建立二元樹

用前序式和後序式建立二元樹的方式並不難。作法類似前序式和後序式的運算,只不過我們不是要算出值,而是要建立出樹的節點。

用後序式建立二元樹
用前序式建立二元樹
用中序式建立二元樹

先將中序式用前面介紹的方式轉成後序式後,再把後序式轉成二元樹。