Infix Expression to Expression Tree

中序表達式轉後序表達式。

主要想處理的功能是：把算式多餘的 Parentheses（括號）給移除，例如：1+(2+3) 可變成：1+2+3；1*(2+3) 則不變。

剛開始看感覺還好，開始做了之後才發現好像遠沒想像的簡單，用一般字串處理，頂多搭配個 Stack 來做，好像很多情況沒有辦法做到，因此有個想法，將 Infix 的表達式（就是我們一般看四則運算的方式）轉成 Postfix，因為 Postfix 就不含括號。

但轉換完 Postfix 後，要怎麼轉回來又是另外一個問題了！因為要加上括號：

Postfix +12 的 Infix 形式為 1+2，而 Postfix 123+* 要轉成 Infix 1*(2+3) 要加上括號，怎麼直接從字串的 123+* 判斷什麼時候要加括號，著實不容易，於是就想到畫出這棵 Expression Tree

   *
 /   \
1     +
     / \
    2   3

因此只要判斷 * 下方的 Operator 是不是優先級比自己低即可，低的話就下面加括號。

總而言之，整個流程大略上是將「四則運算算式」轉換成「Expression Tree」，再轉換回來

每一步的細節其實蠻多的，但大方向是這樣，只要轉成的 Tree 正確，轉回來的過程不加多餘括號，這個問題就解決了。

將 Infix expression 轉成 tree

重要名詞

• Infix, Prefix, Postfix
• Precedence - 優先級
• Associative property - 結合律
• Operand - 運算元（被運算的單元，例如 1+2 中的數字）
• Operator - 運算子（運算什麼，例如 1+2 中的 +）

先轉成 Postfix（without parentheses）

1. 遇到 Operand 就輸出至 Postfix 的結果
2. 遇到 Operator，看 Stack 最頂元素
   2.1. 如果 Stack 的頂元素 Precedence 較高（例如頂元素 * > 現在元素 -），則 Pop 頂元素至 Postfix 的結果
   2.2. 反之，如果 Stack 的頂元素 Precedence 較低、等於或是 Stack 為空，則 Push 此元素至 Stack
   （大方向，Stack 中的元素，越上面的元素 Precedence 一定比較高，且不會等於）
3. Traverse Infix 元素至盡頭，則 Pop Stack 的元素

A + B * C - D * E
i                   Stack:       Postfix: A            --> 1    Add  A to Postfix
  i                 Stack: +     Postfix: A            --> 2.2  Push + to Stack
    i               Stack: +     Postfix: AB           --> 1    Add  B to Postfix
      i             Stack: +*    Postfix: AB           --> 2.2  Push * to Stack
        i           Stack: +*    Postfix: ABC          --> 1    Add  C to Postfix
          i         Stack: +     Postfix: ABC*         --> 2.1  Pop  * to Postfix
          i         Stack:       Postfix: ABC*+        --> 2.1  Pop  + to Postfix
          i         Stack: -     Postfix: ABC*+        --> 2.2  Push - to Stack
            i       Stack: -     Postfix: ABC*+D       --> 1    Add  D to Postfix
              i     Stack: -*    Postfix: ABC*+D       --> 2.2  Push * to Stack
                i   Stack: -*    Postfix: ABC*+DE      --> 1    Add  E to Stack
                i   Stack: -     Postfix: ABC*+DE*     --> 3    Pop  * to Postfix
                i   Stack:       Postfix: ABC*+DE*-    --> 3    Pop  - to Postfix
A + B * C - D * E

先轉成 Postfix（with parentheses）

和有 Prentheses 的情況比，多了以下粗體字的規則

1. 遇到 Operand 就輸出至 Postfix 的結果
2. 遇到 Operator，看 Stack 最頂元素 （頂元素如果為 ( 則視為空的）
   2.1. 如果 Stack 的頂元素 Precedence 較高（例如頂元素 * > 現在元素 -），則 Pop 頂元素至 Postfix 的結果
   2.2. 反之，如果 Stack 的頂元素 Precedence 較低、等於或是 Stack 為空，則 Push 此元素至 Stack
   （大方向，Stack 中的元素，越上面的元素 Precedence 一定比較高，且不會等於）
   2.3. 如果現在元素是 (，Push 至 Stack
   2.4. 如果現在元素是 )，Pop Stack 的元素直到第一個 ( 被 Popped 出來
3. Traverse Infix 元素至盡頭，則 Pop Stack 的元素

( ( A + B ) * C - D * E )
i                          Stack: (      Postfix:            --> 2.3   Push ( to Stack
  i                        Stack: ((     Postfix:            --> 2.3   Push ( to Stack
    i                      Stack: ((     Postfix: A          --> 2.3   Add  A to Postfix
      i                    Stack: ((+    Postfix: A          --> 2.2   Push + to Stack
        i                  Stack: ((+    Postfix: AB+        --> 2.1   Add  B to Postfix
          i                Stack: ((     Postfix: AB+        --> 2.4   Pop  + to Postfix
          i                Stack: (      Postfix: AB+        --> 2.4   Pop  )
            i              Stack: (*     Postfix: AB+        --> 2.2   Push * to Stack
              i            Stack: (*     Postfix: AB+C       --> 2.1   Add  C to Postfix
                i          Stack: (      Postfix: AB+C*      --> 2.4   Pop  * to Postfix
                i          Stack: (-     Postfix: AB+C*      --> 2.2   Push - to Stack
                  i        Stack: (-     Postfix: AB+C*D     --> 2.1   Add  D to Postfix
                    i      Stack: (-*    Postfix: AB+C*D     --> 2.2   Push * to Stack
                      i    Stack: (-*    Postfix: AB+C*DE    --> 2.1   Add  E to Postfix
                        i  Stack: (-     Postfix: AB+C*DE*   --> 2.4   Pop  * to Postfix
                        i  Stack: (      Postfix: AB+C*DE*-  --> 2.4   Pop  - to Postfix
                        i  Stack:        Postfix: AB+C*DE*-  --> 2.4   Pop  )
( ( A + B ) * C - D * E )

從 Infix 轉成 Expression Tree

開始進入到正題，將直接印出來成 Postfix 的行為，換成樹的資料結構。

要產生一個 Expression Tree，我們還需要另一個 Stack 存每個 Sub-Expression。例如 (a+b)*c 就會被切成 (a+b) 這個 Expression 乘以 c。

所以從原本的 Stack 切成兩種：OpStack (Operator Stack) 和 ExprStack (Expression Stack)，其中 ExprStack 存的就是 Tree 的 Node，在此要先定義一下 TreeNode：

TreeNode {
  String value;   // 節點的 Operand
  TreeNode left;  // 左子樹
  TreeNode right; // 右子樹
}

1. 遇到 Operand 就產生一個節點 Push 到 ExprStack
2. 遇到 Operator，看 OpStack 最頂元素（頂元素如果為 ( 則視為空的）
   2.1. 如果 OpStack 的頂元素 Precedence 較高（例如頂元素 * > 現在元素 -），則
   —– Pop OpStack 的頂元素，產生新節點
   —– Pop 兩次 ExprStack 得到兩個 Expression，將新節點的 right 接到第一個 popped 的 Expression，left 接第二個
   —– 將新節點 Push 回 ExprStack
   2.2. 反之，如果 OpStack 的頂元素 Precedence 較低、等於或是 OpStack 為空，則 Push 此元素至 OpStack
   （大方向，OpStack 中的元素，越上面的元素 Precedence 一定比較高，且不會等於）
   2.3. 如果現在元素是 (，Push 至 OpStack
   2.4. 如果現在元素是 )，Pop OpStack 的元素（並照 2.1 的流程，將新 Expression Push 進 ExprStack），直到第一個 ( 被 Popped 出來
3. Traverse Infix 元素至盡頭，則 Pop Stack 的元素

( A + B ) * C
i                OpStack:(      ExprStack:
  i              OpStack:(      ExprStack: A
    i            OpStack:(+     ExprStack: A
      i          OpStack:(+     ExprStack: AB
        i        OpStack:(      ExprStack: [A+B]
        i        OpStack:       ExprStack: [A+B]
          i      OpStack:*      ExprStack: [A+B]
            i    OpStack:*      ExprStack: [A+B]C
            i    OpStack:       ExprStack: [[A+B]*C]

最後得到一棵 Expression Tree
     *
   /   \
  +     C
 / \
A   B

Expression Tree to Infix Expression

如果要把 Expression Tree 給印出來的話，就要考慮加括號這件事了。

     *
   /   \
  +     C
 / \
A   B

以上面這棵樹來看，如果做 Inorder 的走訪可以直接印出 A+B*C，但顯然不是正確的結果，應該要輸出成 (A+B)*C 才對。

所以要在走到 Opertor 時做條件判斷，這邊的做法是走訪時把 Parent Node 的 Precedence 傳下去，例如 * 的左節點是 +，顯然 * 的 Precedence 較高，那麼輸出 [A+B] 這個 Expression 時就要前後加上括號。

另外一種情況是減法或除法，例如 A-(B-C) 或 A/(B/C) 這兩種情況的括號是不能拿掉的，因為 A-(B-C) != A-B-C，我們把減法的這棵 Expression Tree 畫出來看看

   -
 /   \
A     -
     / \
    B   C

所以這邊要判斷 - 的右節點是否為 -、/ 的右節點是否為 /，如果是的話就要將右節點輸出時括號括起來。那如果在左邊呢？例如 (A-B)-C，就不需要特別判斷了，因為 (A-B)-C == A-B-C，四則運算的結合率都是從左到右的。

規則總結

整體做 Inorder traversal

1. 遇到 Operand 直接印出來
2. 遇到 Operator
   2.1. 子節點也是 Operator，且 Precedence 比較低的話，幫他們前後加上括號
   2.2. 如果 Operator 是 - 或 /，判斷其右節點是否和自己 Precedence 一樣，一樣的話也幫他們節後加上括號
   • E.g., 2-(3-4) 或 2-(3+4) 括號都要保留

Traverse 範例

以 Inorder 的方式 Traverse 整棵樹

1. 子節點為 Operand 則直接輸出至 Infix 結果
2. 子節點為 Operator
   2.1. 子節點 Precedence 比現節點低，輸出 (，遞迴 Function 後輸出 )
   2.2. 反之，繼續 Traverse

Postfix: AB+CD+*
        *(1)
    /       \
   +(2)      *(5)
  /  \      /  \
 A(3) B(4) C(6) D(7)

1 - 子節點 +，Precedence 較低，用括號包住 (234)
2 - 子節點 A B 皆為 Operands，印出來 A+B
1 - 左子樹跑完，得到 (A+B)*，跑右子樹
5 - 子節點 C D 皆為 Operands，印出來 C*D
最後得到(A+B)*C*D

其它注意事項

以上的解法都是基於 Operator 只有 +, -, *, / 以及 (, ) 來做的。四則運算的部分都是所謂 Binary 的，意思就是一個 Operator 配合兩個 Operand。

但假設現在多了一個 - Operator 是 Unary 的，也就是取負值這個 Operator，我們就得加上其 Precedence（理論上要比四則運算都高，但又小於括號），而且這棵 Expressoin Tree 就可能會有只有一個子節點的節點了。

例如 2+(-1)，畫成 Tree 就會長成

   +
 /   \
2     -(Unary)
     /
    1

此時整個樹在做 Inorder 時要處理例外條件，遇到 Unary - 時得先印 -，還要考慮何時需要把自己或子節點包起來。像是 5/(-1), 5-(-1) 兩種情況都要包嗎？還是 / 和 * 後的 Unary - 不用包，等等情況需要考慮。