仿 SQL 查詢分析器的 C# 計算器（九）：語法分析核心原理——優先級與「高出低入」堆疊演算法

上篇介紹透過詞法分析將運算式轉成 TokenRecord 物件清單。第一篇提到用樹狀結構表示運算式，再從下層節點取值計算。如何將清單分析成一棵樹？

仍以例子說明，如 3*7+56/8-2*5，分析成 TokenRecord 清單：

分析成樹如下：

依實際算術規則，優先級高的運算子先計算，低優先級運算子再調用其結果。樹狀圖上表現為：高優先級節點是低優先級節點的下層，優先級越高位置越接近葉子。因採用統一物件表示所有元素，TokenValue 也有優先級。分析樹狀圖發現所有 TokenValue 皆處於葉子位置，故 TokenValue 優先級最高。

需用代碼實現。使用 TokenRecord 的 Priority 屬性與堆疊。同樣用迴圈依次分析各 TokenRecord。拿上述清單分析，粗體字代表當前分析的 TokenRecord。分析過程遵循一個原則叫「高出低入原則」：

「高出低入原則」

1. 棧頂 TokenRecord 優先級高於當前 TokenRecord 優先級，則將棧頂 TokenRecord 彈棧（高出）到暫存變數。
   1. 若堆疊為空，將暫存變數中的 TokenRecord 加入當前 TokenRecord 的 ChildList，然後將當前 TokenRecord 壓棧（低入）。
   2. 若堆疊不為空，找出棧頂 TokenRecord 和當前 TokenRecord 中優先級高的一個（相同則按棧頂高算），將暫存變數中的 TokenRecord 加入高優先級 TokenRecord 的 ChildList。再用「高出低入原則」處理棧頂和當前 TokenRecord。
2. 棧頂 TokenRecord 優先級低於當前 TokenRecord 優先級，則將當前 TokenRecord 直接壓棧。