在Java 中將算術表達式解析為樹結構

從算術表達式創建自定義樹可能是一項具有挑戰性的任務，特別是在確保樹結構時準確反映表達式的操作和優先順序。

要實現這一點，一種有效的方法是使用堆疊。以下是該過程的逐步描述：

1. 初始化：從空堆疊開始。

2. 處理代幣：迭代表達式中的每個標記：

   • 如果標記是左括號，則壓入它
   • 如果token 是整數，則建立一個包含該整數的新葉子節點並將其壓入堆疊。

   • 如果token 是運算符，則檢查其優先權：

     • 如果運算子的優先權高於堆疊中目前的優先權（初始為0），則將其壓入堆疊stack.
     • 如果運算子的優先權低於或等於目前優先權，則計算表達式，直到運算子的優先權高於目前優先權。
3. 求值：當運算子優先順序較高時，對棧頂兩個節點進行運算，建立一個新節點結果。將新節點壓入堆疊。
4. 括號處理：如果遇到右括號，則從堆疊中彈出節點，直到找到對應的左括號。在繼續之前執行任何掛起的操作。
5. 最終結果：處理完所有代幣後，評估堆疊上的所有剩餘節點。產生的節點將表示表達式樹的根。

透過執行下列步驟，您可以建構一個準確反映給定算術表達式的表達式樹，包括支援表示為「5 ( -2)」。基於堆疊的方法可以有效地處理運算子優先權和括號，從而產生正確的樹結構。