我有一个类似((2+8)*8)-(5*(5+2)) Or + 2 + 1 1的表达式。我想在里面做一个二叉树。
+
/
2 +
/
1 1
如何制作此二叉树？
我有一个类似的项目，我就是这样做的：
-
标记字符串。查看每个符号是什么。例如，列表可能包含：
'（'打开副题"11"编号'+'运算符等
-
将表达式转换为后缀（或前缀，如果需要）表示法。一种可以做到这一点的算法被称为调车场算法。后缀表示法的优点是，使用基于堆栈的方法（如果需要，可以使用二进制树），可以更容易地计算表达式。
-
计算后缀表达式。您可以通过两种方式来实现，一种是二进制树，另一种是堆栈。
堆栈评估：
用后缀表示法转换的示例表达式如下所示：
2 8 + 8 * 5 5 2 + * -
评估的工作原理是这样的：当你遇到一个数字时，把它推到堆栈上。当您遇到运算符时，从堆栈中弹出2个项目，进行计算，并将结果推送到堆栈上。最后，你应该留下最后的结果。
对于上面的例子，这就是我们要做的：
Push 2 [Stack content: 2]
Push 8 [2 8]
Pop 2 and 8 []
Push 2+8 [10]
Push 8 [10 8]
Pop 10 and 8 []
Push 10*8 [80]
Push 5 [80 5]
Push 5 [80 5 5]
Push 2 [80 5 5 2]
Pop 2 and 5 [80 5]
Push 2 + 5 [80 5 7]
Pop 7 and 5 [80]
Push 7 * 5 [80 35]
Pop 80 and 35 []
Push 80 - 35 [45]
Final result is 45.
二叉树
我就是这样做的：就像基于堆栈的方法一样，使用一个节点堆栈。当遇到运算符时，您会从堆栈中弹出2个项，但不是求值，而是使用运算符创建一个节点，并使其成为2个弹出项的父节点。然后将节点推回到堆栈上。
这种方法的缺点是有一个额外的步骤：创建树。
最后注释
这是我会使用的方法。也许还有比这更有效的方法，但我会这样做。
以下是用于从中缀字符串创建二进制表达式树的C++代码。