0%

前、中及後序 Preorder, Inorder and Postorder

研究所開學前想把一些比較簡單的內容寫完,
然後正式邁入下個階段,要學的東西還很多……

這篇文章需要堆疊與佇列的基本知識,請參考 堆疊與佇列 Stack and Queue

運算子與運算元

在開始介紹之前,可能要先提到運算子跟運算元。

運算子(operator)通俗的意思是「符號」,像是 + - * / 之類的;
而運算元(operand)意思是「數字」或「代數」,像是 1, 2, 3,… 或 x, y, z, …等都是運算元。

本篇文章使用的運算子包含:

  • 加 +
  • 減 -
  • 乘 *
  • 除 /
  • 冪 ^
  • 左括號 (
  • 右括號 )

共 7 種運算子,而運算元則可以是任意數字。

中序表示法

中序表示法(Infix order)就是一般常見的數學式,運算格式為「運算元 運算子 運算元」;
像是「1 + 1」、「3 * 2」、「3 ^ 3」等等皆屬中序表示,另外含括號的類型也是,
比如「5 / ( 2 + 1 )」,因為「2 + 1」可以運算後變成「5 / 3」,也是中序表示法。

要特別說明的是,電腦運算通常不使用中序表示,而使用前、後序表示;
因為資料常常從左讀取至右,前、後序都有隱含運算順序的能力,可以省去許多資料處理上的麻煩。

前序表示法

前序表示法是將運算子放到所有運算元之前的表示法,格式為「運算子 運算元 運算元」;
像是「+ 1 1」、「* 3 2」、「^ 3 3」就是前序表示法。

由於前序表示已經隱含了運算順序,所以前序表示不需要括號也可以判斷運算順序。
像是「/ 5 + 2 1」就是先做「+ 2 1」再做「/ 5 3」。

不需要括號,不代表不能顯式寫出,比方說「/ 5 ( + 2 1 )」也是可以的。

後序表示法

後序表示法是將運算子放置到所有運算元之後的表示法,格式為「運算元 運算元 運算子」;
像是「1 1 +」、「3 2 *」、「3 3 ^」就是後序表示法。

與前序表示一樣,後序表示法隱含了運算順序,所以不需要括號,
像是「5 2 1 + /」就是先做「2 1 +」再做「5 3 /」。

不需要括號,不代表不能顯式寫出,比方說「5 ( 2 1 + ) /」也是可以的。

中序轉前後序

先考慮中序轉換成前序,若以「1 + 2 * ( 3 - 4 ) / 5」為例,
其對應前序為「+ 1 / * 2 - 3 4 5」,後序轉換概念與前序一致。

我們觀察該式,如果電腦由左至右掃描,那麼經過轉換的式子,運算元應該對應順序不變。

但電腦掃到「1 + 2」時,不能直接轉換成「+ 1 2」,
因為尚未確定「1 + 2」之後的運算子,需要掃描到「1 + 2 *」才有足夠的資訊處理。

我們透過 2 個堆疊可以將中序轉換成前序,一個保留運算元資訊,另一個紀錄運算子。
詳細步驟稍後解釋,逐步的轉換步驟如下,掃描到的字元以顏色表示:

運算式 分類 運算子堆疊 運算元堆疊 處理原因
1 + 2 * ( 3 - 4 ) / 5 運算元 1 運算元直接加入堆疊
1 + 2 * ( 3 - 4 ) / 5 運算子 + 1 運算子堆疊為空,直接加入堆疊
1 + 2 * ( 3 - 4 ) / 5 運算元 + 1 2 運算元直接加入堆疊
1 + 2 * ( 3 - 4 ) / 5 運算子 + * 1 2 * 優先度高於 + 故加入堆疊
1 + 2 * ( 3 - 4 ) / 5 運算子 + * ( 1 2 ( 優先度高於 * 故加入堆疊
1 + 2 * ( 3 - 4 ) / 5 運算元 + * ( 1 2 3 運算元直接加入堆疊
1 + 2 * ( 3 - 4 ) / 5 運算子 + * ( - 1 2 3 - 優先度高於 ( 加入堆疊
1 + 2 * ( 3 - 4 ) / 5 運算元 + * ( - 1 2 3 4 運算元直接加入堆疊
1 + 2 * ( 3 - 4 ) / 5 運算子 + * ( - 1 2 3 4 ) 需特殊處理
1 + 2 * ( 3 - 4 ) / 5 運算子 + * ( 1 2 - 3 4 運算子堆疊取出一個元素 - 檢查不為 (
運算元堆疊取出兩個元素 4 3
組合成 - 3 4 加回運算元堆疊
1 + 2 * ( 3 - 4 ) / 5 運算子 + * 1 2 - 3 4 運算子堆疊取出一個元素 ( 檢查為 ( 結束特殊處理
1 + 2 * ( 3 - 4 ) / 5 運算子 + 1 * 2 - 3 4 / 與 * 優先度相等
運算子堆疊取出一個元素 *
運算元堆疊取出兩個元素 - 3 4 2
組合成 * 2 - 3 4 加回運算元堆疊
1 + 2 * ( 3 - 4 ) / 5 運算子 + / 1 * 2 - 3 4 / 優先度高於 + 故加入堆疊
1 + 2 * ( 3 - 4 ) / 5 運算元 + / 1 * 2 - 3 4 5 運算元直接加入堆疊
1 + 2 * ( 3 - 4 ) / 5 運算元 + / 1 * 2 - 3 4 5 掃描完畢
1 + 2 * ( 3 - 4 ) / 5 運算元 + 1 / * 2 - 3 4 5 運算子堆疊取出一個元素 /
運算元堆疊取出兩個元素 5 * 2 - 3 4
組合成 / * 2 - 3 4 5 加回運算元堆疊
1 + 2 * ( 3 - 4 ) / 5 運算元 + 1 / * 2 - 3 4 5 運算子堆疊取出一個元素 +
運算元堆疊取出兩個元素 / * 2 - 3 4 5 1
組合成 + 1 / * 2 - 3 4 5 加回運算元堆疊
1 + 2 * ( 3 - 4 ) / 5 運算元 + 1 / * 2 - 3 4 5 運算元堆疊頂端元素即為解

從這個列表,我們可以歸納出下面這些結論:

  1. 掃描到運算元,直接加入運算元堆疊
  2. 掃描到運算子,若其優先度高於運算子堆疊頂端元素,則直接加入運算子堆疊
  3. 掃描到運算子,若其優先度低於運算子堆疊頂端元素,則「清理堆疊」直到滿足第 2 點
  4. 掃描到運算子,若為「)」則「清理堆疊」直到運算子堆疊中「(」取出為止
  5. 掃描完畢後「清理堆疊」直到運算元堆疊只剩下 1 個元素

至於「清理堆疊」的方法為:

  1. 從運算子堆疊取出 1 個元素
  2. 從運算元堆疊取出 2 個元素
  3. 組合放回運算元堆疊

從這裡可以發現,中序表示轉換成前序或後序,是由清理堆疊的第 3 步處理的。

運算子優先度接近其運算的優先度,列表如下:

運算子 優先度
+ 1
- 1
* 2
/ 2
^ 3
( 出堆疊時,優先度為 0(因為要阻止它離開堆疊,直到配對「)」為止)
進入堆疊時,優先度為 4(因為要強制加入堆疊中,等待「)」的配對)
) 特殊處理,不進入堆疊中(出現時,堆疊中必存在「(」,否則算式有誤)

優先度是透過大小關係運作的,亦即大小關係正確即可,實際數值可以自行調整。

前後序轉中序

與中序轉換成前後序不同,轉換回中序較簡單,
以前序為例,觀察下表,稍後整理步驟:

運算式 分類 運算元堆疊 處理原因
+ 1 / * 2 - 3 4 5 運算元 5 運算元直接加入堆疊
+ 1 / * 2 - 3 4 5 運算元 5 4 運算元直接加入堆疊
+ 1 / * 2 - 3 4 5 運算元 5 4 3 運算元直接加入堆疊
+ 1 / * 2 - 3 4 5 運算子 5 (3 - 4) 從運算元堆疊取出兩個元素 3 4
組合成 (3 - 4) 加回運算元堆疊
- 加入運算子堆疊
+ 1 / * 2 - 3 4 5 運算元 5 (3 - 4) 2 運算元直接加入堆疊
+ 1 / * 2 - 3 4 5 運算子 5 (2 * (3 - 4)) 從運算元堆疊取出兩個元素 2 (3 + 4)
組合成 (2 * (3 + 4)) 加回運算元堆疊
* 加入運算子堆疊
+ 1 / * 2 - 3 4 5 運算子 ((2 * (3 - 4)) / 5) 從運算元堆疊取出兩個元素 (2 * (3 - 4)) 5
組合成 ((2 * (3 - 4)) / 5) 加回運算元堆疊
/ 加入運算子堆疊
+ 1 / * 2 - 3 4 5 運算元 ((2 * (3 - 4)) / 5) 1 運算元直接加入堆疊
+ 1 / * 2 - 3 4 5 運算子 (1 + ((2 * (3 - 4)) / 5)) 從運算元堆疊取出兩個元素 1 ((2 * (3 - 4)) / 5)
組合成 (1 + ((2 * (3 - 4)) / 5)) 加回運算元堆疊
+ 加入運算子堆疊
+ 1 / * 2 - 3 4 5 運算元 (1 + ((2 * (3 - 4)) / 5)) 運算元堆疊頂端元素即為解

同樣地,可以歸納出下面這些結論:

  1. 前序轉中序時,反向掃描(因為要先掃到運算元)
  2. 後序轉中序時,正向掃描(因為要先掃到運算元)
  3. 掃描到運算元時,加入運算元堆疊
  4. 掃描到運算子時,執行「清理堆疊」

至於「清理堆疊」的方法為:

  1. (掃描到的)運算子
  2. 從運算元堆疊取出 2 個元素
  3. 組合放回運算元堆疊(可以加入括號)

不難發現,前序、後序表示運算的方法,就是轉換成中序的方法:將每一步清理堆疊的「組合」變成「計算」即可。