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

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

在本文中，我們將深入研究解析算術表達式的複雜性算術表達式並用Java 建構它的樹表示。

簡介

首先，我們假設輸入表達式作為字串提供並符合遵循以下規則：

• 負數必須括在括號中。
• 括號必須保持一致。

建構樹

從算術表達式建構樹的核心涉及利用堆疊。當我們逐個字元解析表達式時，我們將運算子和數值壓入堆疊。運算子具有關聯的優先級，允許我們在遇到子表達式時對其求值和組合。

Approach

1. 初始化堆疊： 從空堆疊開始。
2. 解析式： 存取表達式字串中的每個字元。
3. 處理括號： 如果是括號遇到運算子時，要麼將其壓入堆疊，要麼計算括號內的子表達式。
4. 處理運算子：遇到運算子時，將其優先權與目前「最高優先權」進行比較堆疊。如果 current 低於 new 運算子的優先權，則將 new 運算子壓入堆疊。否則，計算堆疊上的運算符，直到新運算符的優先權更高或相等。
5. 處理數值：將數值直接壓入堆疊。
6. 評估堆疊：處理完所有字元後，從上到下評估堆疊上的剩餘運算符。

範例

考慮表達式：

(5+2)*7

我們將解析它如下：

Character	Action	Stack
(	Push (	(
5	Push 5	(, 5
	Push	(, 5,
2	Push 2	(, 5, , 2
)	Evaluate to 7, push 7	(, 7
*	Push *	(, 7, *
7	Push 7	7, *, 7

產生的樹將是：

(5+2)*7

結論

解析算術表達式並建立樹是電腦科學中的基本操作。本文提供了使用堆疊的逐步方法，並強調了優先規則和括號平衡的重要性。在 Java 中實現此演算法將使您能夠創建功能強大的應用程序，可以有效地處理和操作算術表達式。

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