首頁 › 半導體、電子電路與資訊計算工具
逆波蘭表示法轉換工具
將中序式轉換為逆波蘭表示法(後序式),並以表格逐一字符顯示運算子何時推入堆疊、何時取出。同時顯示波蘭表示法(前序式)與語法樹,若替變數指定數值,還能確認使用堆疊計算的過程。也可以從逆波蘭表示法的式子,轉回括號最少的中序式。
轉換結果
逆波蘭表示法(後序式) –
波蘭表示法(前序式) –
中序式(括號最少) –
計算結果 –
語法樹
轉換過程(調度場演算法)
使用堆疊計算
運算子的優先順序以 ^ 最高,其次是 × ÷,最低是 + −。同順位的 + − × ÷ 由左往右計算,^ 則由右往左計算。÷ 在除不盡時也會以小數計算。
以圖表檢視
橫軸的輸入
縱軸的結果
其他輸入維持目前的值,只讓選擇的輸入在目前值的 1/4 到 4 倍之間變化時的結果。紅點是目前的值。
什麼是逆波蘭表示法
像平常寫的 A + B 這樣,把運算子放在兩個值之間的寫法稱為中序式。相對地,像 A B + 這樣把運算子放在值後面的是逆波蘭表示法(後序式),像 + A B 這樣放在前面的是波蘭表示法(前序式)。在逆波蘭表示法中,即使沒有運算子的優先順序與括號,計算順序也只有一種。例如 (A + B) × (C − D) 會變成 A B + C D − ×,括號就消失了。由於這個性質,它被用於計算機、程式語言的處理系統,以及堆疊 機器的指令序列等。
以堆疊計算
逆波蘭表示法的算式,只要由左往右依序讀取,並使用一個堆疊 就能計算。遇到數字或變數 就推入堆疊;遇到運算子就從頂端取出 2 個值計算,再把結果推入。要注意取出的 2 個值中,先取出的(原本在上方的)是右側的值。以 5 1 2 + 4 × + 3 − 為例,會依序計算 1 + 2 = 3、3 × 4 = 12、5 + 12 = 17、17 − 3 = 14,最後留在堆疊中的 14 就是答案。請選擇範例,在計算表中確認堆疊的變化。
從中序式轉換:調度場演算法
要把中序式改寫成逆波蘭表示法,可使用戴克斯特拉(Dijkstra)提出的調度場演算法。由左往右讀取算式,數字與變數 直接輸出。遇到運算子時,若堆疊 頂端有優先順序相同或較高的運算子,就先將其輸出再推入(像次方這種右結合的運算子,只輸出優先順序較高者)。左括號推入堆疊,遇到右括號時,把到左括號為止的運算子全部輸出。最後把堆疊中剩下的運算子輸出就完成了。在 A + B × C 中,× 的優先順序較高,因此會疊在 + 之上,結果為 A B C × +。
與語法樹的關係
算式可以表示成以運算子為節點、以數字或變數 為樹葉的語法樹(二元樹)。依「左子節點、右子節點、節點」的順序走訪這棵樹(後序走訪)就得到逆波蘭表示法,依「節點、左子節點、右子節點」的順序(前序走訪)得到波蘭表示法,依「左子節點、節點、右子節點」的順序(中序走訪)則得到中序式。編譯器會剖析原始碼中的算式並建立抽象語法樹 ,再走訪它來輸出堆疊 機器的指令或機器碼。考試中常見的題型有:由算式或樹寫出逆波蘭表示法,或是問樹的走訪方式名稱。
練習編譯器題目
A −9 B 6 C 9
查看答案與解析 正確答案:C. 9
推入3、4,以 + 取出並推入 3 + 4 = 7。接著推入2,以 * 推入 7 × 2 = 14。推入5,以 − 從先推入的14減去後推入的5,得到 14 − 5 = 9。後序式的運算順序由排列決定,因此不需要括號,相當於一般算式的 (3 + 4) × 2 − 5。−9 是弄反減法左右的值,6 則是不加括號讀成 3 + 4 × 2 − 5 的值。
A 根節點是 + 的節點,其右子節點是表示 3 * 4 的 * 節點 B 根節點是 * 的節點,其左子節點是表示 2 + 3 的 + 節點 C 2、3、4、+、* 這5個節點全部並列為根節點的直接子節點
查看答案與解析 正確答案:A. 根節點是 + 的節點,其右子節點是表示 3 * 4 的 * 節點
乘法的優先順序高於加法,所以此運算式會被解釋為 2 + (3 * 4)。在抽象語法樹 中,越先計算的運算會放在越下面,所以根節點是 +,其左子節點是2,右子節點是以3和4為子節點的 * 節點。若由下往上對樹求值,會先計算 3 * 4 = 12,再得到 2 + 12 = 14。根節點成為 * 的是寫成 (2 + 3) * 4 的情況,而把全部並列在根節點之下,則無法表示計算的順序。
A 連原始碼的括號與分隔符號都全部保留為節點 B 省略與語意無關的符號,並以樹狀結構表示運算子的優先順序 C 與CPU的指令一對一對應,可直接執行
查看答案與解析 正確答案:B. 省略與語意無關的符號,並以樹狀結構表示運算子的優先順序
語法分析 會依照文法規則產生連括號與分隔符號都包含在內的樹(具體語法樹),但其中含有許多後續處理不需要的資訊。抽象語法樹 則是只將程式語意所需的運算與敘述作為節點的樹,例如在(a + b) * c中,加法節點位於乘法節點之下,因此即使沒有括號也能得知運算的順序。與CPU指令對應的,是更後面的階段所產生的程式碼。
A 從字元序列中移除空白與註解,並切分為單字 B 找出經常執行的部分,並在執行時轉換為機器碼 C 依照文法檢視token序列,將程式的結構組成樹狀結構
查看答案與解析 正確答案:C. 依照文法檢視token序列,將程式的結構組成樹狀結構
語法分析 會檢查詞法分析 所得的token序列是否符合語言的文法,並將if敘述的條件與主體、運算式中各運算的組合等結構組成樹狀結構(語法樹)。漏寫分號或括號不成對等文法錯誤,會在這個階段被發現。移除空白並切分為單字的是詞法分析,在執行時轉換為機器碼的則是JIT編譯 。
常見問題
A − B − C 的逆波蘭表示法是什麼?
是 A B − C −。− 是由左往右計算的(左結合)運算子,因此意思與 (A − B) − C 相同。若是 A − (B − C),則為 A B C − −,結果會不同。
為什麼逆波蘭表示法不需要括號?
因為運算子出現時,一定會套用到它前面的 2 個值(或到目前為止的計算結果),所以哪些值彼此計算,只由書寫的順序就能決定。在中序式中,即使排列相同,計算順序也會因優先順序與括號而改變。
像 −A 這樣帶正負號的算式可以轉換嗎?
本工具只支援取 2 個值的運算子(二元運算子)。負號請寫成 (0 − A)。實際的處理系統會把單元負號當作另一個運算子處理。
考試中會怎麼出題?
在日本的基本資訊技術士考試等資訊類證照考試中,常見的題型有:選出中序式對應的逆波蘭表示法、求逆波蘭表示法算式的值,以及語法樹的走訪方式。請選擇範例,把表格中的動作與自己的步驟相互比較。