研究所開學前想把一些比較簡單的內容寫完,
然後正式邁入下個階段,要學的東西還很多……
這篇文章需要堆疊與佇列的基本知識,請參考 堆疊與佇列 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 | 運算元堆疊頂端元素即為解 |
從這個列表,我們可以歸納出下面這些結論:
- 掃描到運算元,直接加入運算元堆疊
- 掃描到運算子,若其優先度高於運算子堆疊頂端元素,則直接加入運算子堆疊
- 掃描到運算子,若其優先度低於運算子堆疊頂端元素,則「清理堆疊」直到滿足第 2 點
- 掃描到運算子,若為「)」則「清理堆疊」直到運算子堆疊中「(」取出為止
- 掃描完畢後「清理堆疊」直到運算元堆疊只剩下 1 個元素
至於「清理堆疊」的方法為:
- 從運算子堆疊取出 1 個元素
- 從運算元堆疊取出 2 個元素
- 組合放回運算元堆疊
從這裡可以發現,中序表示轉換成前序或後序,是由清理堆疊的第 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)) | 運算元堆疊頂端元素即為解 |
同樣地,可以歸納出下面這些結論:
- 前序轉中序時,反向掃描(因為要先掃到運算元)
- 後序轉中序時,正向掃描(因為要先掃到運算元)
- 掃描到運算元時,加入運算元堆疊
- 掃描到運算子時,執行「清理堆疊」
至於「清理堆疊」的方法為:
- (掃描到的)運算子
- 從運算元堆疊取出 2 個元素
- 組合放回運算元堆疊(可以加入括號)
不難發現,前序、後序表示運算的方法,就是轉換成中序的方法:將每一步清理堆疊的「組合」變成「計算」即可。