在 Java 中将算术表达式解析为树结构

从算术表达式创建自定义树可能是一项具有挑战性的任务，特别是在确保树结构时准确反映表达式的操作和优先级。

要实现这一点，一种有效的方法是使用堆栈。以下是该过程的逐步描述：

1. 初始化：从空堆栈开始。

2. 处理令牌：迭代表达式中的每个标记：

   • 如果标记是左括号，则压入它
   • 如果 token 是整数，则创建一个包含该整数的新叶子节点并将其压入堆栈。

   • 如果 token 是运算符，则检查其优先级：

     • 如果运算符的优先级高于堆栈中当前的优先级（初始为0），则将其压入堆栈stack.
     • 如果运算符的优先级低于或等于当前优先级，则计算表达式，直到运算符的优先级高于当前优先级。
3. 求值：当运算符优先级较高时，对栈顶两个节点进行运算，创建一个新节点结果。将新节点压入堆栈。
4. 括号处理：如果遇到右括号，则从堆栈中弹出节点，直到找到相应的左括号。在继续之前执行任何挂起的操作。
5. 最终结果：处理完所有令牌后，评估堆栈上的所有剩余节点。生成的节点将表示表达式树的根。

通过执行以下步骤，您可以构造一个准确反映给定算术表达式的表达式树，包括支持表示为“5 ( -2)”。基于堆栈的方法可以有效地处理运算符优先级和括号，从而产生正确的树结构。