如何在 Java 中從算術表達式解析並建立樹？

在Java 中解析算術表達式並從中建立樹

簡介

解析算術表達式並建立計算式樹是編譯器設計和語言處理的重要任務。本文將示範如何在 Java 中解析算術表達式並建立樹表示。

解析表達式

要解析表達式，我們可以使用堆疊 -基於演算法。當我們迭代表達式時：

• 將左括號壓入堆疊。
• 將數字和運算子壓入堆疊。
• 遇到右括號，計算透過彈出堆疊直到到達匹配的左括號，然後將結果壓入堆疊來產生子樹。

建構樹

解析表達式後，我們可以從堆疊中建立樹節點：

• 節點：整數成為LeafInt節點。
• 運算符節點：運算子成為具有 PlusOp、MinusOp、MultOp 或 DivOp 類別的節點及其子節點從堆疊中彈出。

範例

考慮表達式(5 2) *7:

<code class="java">Stack<Node> stack = new Stack<>();
stack.push(new LeafInt(5));
stack.push(new PlusOp());
stack.push(new LeafInt(2));
stack.push(new MultOp());
stack.push(new LeafInt(7));
while (stack.size() > 1) {
  Node right = stack.pop();
  Operator op = (Operator) stack.pop();
  Node left = stack.pop();
  stack.push(new OpNode(op, left, right));
}</code>

產生的樹將具有以下結構：

    *
   / \
  +   7
 / \
5   2

處理負數和括號

處理負數數字，將它們表示為5 (-2) 而不是5-2。負號始終具有一元優先權。同樣，括號強制執行運算順序。

驗證

為了確保正確性，請透過檢查來驗證表達式：

• 左括號有匹配右括號。
• 每個運算子都有正確數量的運算元。

結論

使用基於堆疊的演算法，它是可以直接解析算術表達式並建立其等效的樹表示。這種方法為進一步分析和操作 Java 中的算術表達式提供了可靠的基礎。

以上是如何在 Java 中從算術表達式解析並建立樹？的詳細內容。更多資訊請關注PHP中文網其他相關文章！