c# - 从数学表达式创建二叉树

Question

我有这样的表达((2+8)*8)-(5*(5+2)) Or + 2 + 1 1。我想在其中制作一棵二叉树。

  +
 / \
2   +
   / \
  1   1

我怎样才能制作这个二叉树？

Answer 1

我有一个类似的项目，我就是这样做的：

1. 标记字符串。看看每个符号是什么。例如，该列表可能包含：

   '(' 打开括号
   '11' 号码
   '+' 运算符等

2. 将表达式转换为后缀（或前缀，如果需要）表示法。可以做到这一点的一种算法称为Shutting Yard 算法。后缀表示法的优点是您可以使用基于堆栈的方法（或二叉树，如果需要）更容易地评估表达式。

3. 计算后缀表达式。您可以通过两种方式进行操作，二叉树和堆栈。

堆栈评估：

您以后缀表示法转换的示例表达式将如下所示：

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 个弹出项目的父节点。然后将节点推回堆栈。

这种方法的缺点是您有一个额外的步骤：创建树。

最后的笔记

这是我会使用的方法。也许有比这更有效的方法，但这就是我的做法。

Answer 2

这是用于从中缀字符串创建二进制表达式树的 C++ 代码。