仿 SQL 查詢分析器的 C# 計算器（一）：運算式解析與二元樹運算邏輯

計算器是許多編程初學者都做過的，從最簡單的控制台程式開始：輸入值、運算子、再輸入值、得到結果。帶介面的基本模仿 Windows 計算機，透過按鈕輸入值與運算子給出結果。能不能直接輸入運算式？能否對多個運算式計算？能否選擇運算式一部分計算？輸入錯誤能否指出錯誤位置？這類需求類似 MS SQL 查詢分析器，本系列將介紹如何實現這樣的計算器（內容涉及編譯原理，但非計算機專業出身，僅稍閱相關資料，專業術語如有限狀態機等不提，不敢稱專業）。

首先給出運算式 5*3+12/4，分析過程如下：

1. 乘法優先級高於後面的加法，先算乘法：乘號兩邊為 5 和 3，執行 5*3=15
2. 加法優先級低於後面的除法，先算除法：除號兩邊為 12 和 4，執行 12/4=3
3. 乘除完成後再做加法：加法只需知道兩邊計算後的值，乘法值 15，除法值 3，執行 15+3=18

在運算式後加一步：5*3+12/4-8，只多一步操作：

4. 加法完成後做減法：減號不需知道兩邊怎麼算，向兩邊請求值，得加法值 18，另一邊為數字 8，執行 18-8=10

再稍微改變：5*3+12/4-8/2，計算過程：

4. 加法完成準備做減法，但後面除法優先級高，先做除法：8/2=4
5. 執行減法：左邊為加法值 18，右邊為除法值 4，18-4=14

發現每個運算子可視為一個數值儲存單元，根據兩邊數值計算得出自身值，只關心兩邊值而不關心值如何得來。這就是二元樹的樣子：一個節點下可有兩個子節點。因此無論運算式多複雜，最終只有一個結果，這結果是最後一個運算子對兩邊值計算得出，最後一個運算子即根節點。下面將運算式按樹形分解：

減法為根節點，向下請求值並計算。下層節點同樣向下請求值，得出值後執行自身計算，存儲在自己的儲存單元，讓上層調用。最終由根節點計算下層值得到整個運算式值。最終計算完的樹結構如下：