運算式(Expression)有三種表示方式:中序式(Infix)
、前序式(Prefix)
、後序式(Postfix)
。
一般我們算數學時看到的表達式 A * (B + C) / D
,我們知道括號優先算,再來先乘除後加減,這樣的表達式叫(中序Infix)。對於電腦或編譯器來說,解析過於複雜的中序是有難度的,所以有了前序及後序。
中序
如何轉換成前序
或後序
?記住兩個要點
- 前序就是將運算元移動貼到左括號。例如
(A+B)
=> (+AB)
- 後序就是將運算元移動貼到右括號。例如
(A+B)
=> (AB+)
題目一:將 A + B * (C + D) + E / F
轉為前序及後序。
- 先把運算式所有隱藏的括號加上去,會得出
((A + ( B * ( C + D ))) + ( E / F ))
- 一個個括號接續處理,假如要轉換成前序,就是把願算元放到括號左邊
先從最內層的括號開始,(C + D) => (+ C D) ; (E / F) => (/ E F)
目前可以得出 ((A + ( B * ( + C D ))) + ( / E F ))
- 內層括號解完,開始慢慢往外解,( B * ( + C D )),乘號往前放,會得出
(* B ( + C D )),在這我會先把內層括號先去掉,看起來比較不會那麼亂 => (* B +CD)
- 再往外解一層(A + (*B+CD)) => (+ A (*B+CD)) => (+ A *B+CD)
- 接下來只剩下最後一個運算元了
- (+A*B+CD + /EF ),一樣+號往左邊放再去括號 => (+ +A*B+CD /EF ) => ++A*B+CD /EF,這個中序轉前序結果即
++A*B+CD/EF
中序轉後序一樣概念,只是運算元放的位置變成貼近右括號。
詳解
前序:+ + A * B + C D / E F
後序:A B C D + * + E F / +
題目二:將 + + * A B / - C D – E F G
轉為中序及後序
要點:一個運算子(符號)會搭配兩個運算元(符號左右兩個)
- 根據要點,把隱形括號給找出來,可以先把比較好找的括起來,看到一個符號搭配兩個運算元的那種先畫起來 => + + (* A B) / (- C D) (– E F) G
- 進階畫括號,已經被刮起來的,就把它視為一個運算元,可以得出
=> + + (* A B) ( / (- C D) (– E F) ) G
=> + ( + (* A B) ( / (- C D) (– E F) ) ) G
=> ( + ( + (* A B) ( / (- C D) (– E F) ) ) G )
- 符號放回去兩個運算元中間,例如(+ () ()) => (() + ()),可以得出
=> ( ( ( A * B ) + (( C - D ) / ( E - F ) ) ) + G )
=> 去掉不必要的括號,得出 A * B + ( C - D ) / ( E - F ) + G
現在有了中序了,根據第一題的概念去轉後序。
詳解
中序:A * B + (C - D) / (E - F) + G
後序:A B * C D – E F - / + G +