運算式(Expression)有三種表示方式:`中序式(Infix)`、`前序式(Prefix)`、`後序式(Postfix)`。
一般我們算數學時看到的表達式 `A * (B + C) / D`,我們知道括號優先算,再來先乘除後加減,這樣的表達式叫(中序Infix)。對於電腦或編譯器來說,解析過於複雜的中序是有難度的,所以有了前序及後序。
`中序`如何轉換成`前序`或`後序`?記住兩個要點
1. 前序就是將運算元移動貼到==左括號==。例如`(A+B)` => `(+AB)`
2. 後序就是將運算元移動貼到==右括號==。例如`(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`
中序轉後序一樣概念,只是運算元放的位置變成貼近右括號。
:::spoiler 詳解
前序:+ + 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
現在有了中序了,根據第一題的概念去轉後序。
:::spoiler 詳解
中序:A * B + (C - D) / (E - F) + G
後序:A B * C D – E F - / + G +
:::