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）
- 遇到 Operand 就輸出至 Postfix 的結果
- 遇到 Operator，看 Stack 最頂元素 2.1. 如果 Stack 的頂元素 Precedence 較高（例如頂元素 * > 現在元素 -），則 Pop 頂元素至 Postfix 的結果 2.2. 反之，如果 Stack 的頂元素 Precedence 較低、等於或是 Stack 為空，則 Push 此元素至 Stack （大方向，Stack 中的元素，越上面的元素 Precedence 一定比較高，且不會等於）
- 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 的情況比，多了以下粗體字的規則
- 遇到 Operand 就輸出至 Postfix 的結果
- 遇到 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 出來 - 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; // 右子樹
}- 遇到 Operand 就產生一個節點 Push 到 ExprStack
- 遇到 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 出來 - 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 BExpression 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
- 遇到 Operand 直接印出來
- 遇到 Operator
2.1. 子節點也是 Operator，且 Precedence 比較低的話，幫他們前後加上括號
2.2. 如果 Operator 是
-或/，判斷其右節點是否和自己 Precedence 一樣，一樣的話也幫他們節後加上括號- E.g.,
2-(3-4)或2-(3+4)括號都要保留
- E.g.,
Traverse 範例
以 Inorder 的方式 Traverse 整棵樹
- 子節點為 Operand 則直接輸出至 Infix 結果
- 子節點為 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 - 不用包，等等情況需要考慮。