从数学表达式创建二叉树

Question

我有一个表达式，类似于((2+8)*8)-(5*(5+2)) Or + 2 + 1 1。我想在其中创建一棵二叉树。

  +
 / \
2   +
   / \
  1   1

我该如何构建这个二叉树？

- Moiz

---

好的，那么在 C# 中，如果我传递这个表达式，我怎样才能创建一个二叉树数据结构呢？ - Moiz

我有这个链接http://www.smokycogs.com/blog/an-implementation-of-a-binary-tree-in-c-sharp/，但不知道如何传递字符串参数。 - Moiz

正如pst所说，考虑方程的前缀表示法（而不是中缀表示法），一旦你知道如何构建树，它就应该变得很明显了。 - ravuya

Answer 1

我有一个类似的项目，这是我完成它的方法:

1. 将字符串进行分词处理，查看每个符号。例如，列表可能包含以下内容:

   '('：左括号
   '11'：数字
   '+'：运算符等

2. 将表达式转换为后缀（或前缀，如果需要）。可以使用称为Shunting Yard algorithm的算法来完成此操作。后缀表示法的优点是您可以使用基于栈的方法（或二叉树，如果需要）更轻松地对表达式进行求值。

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个元素，但不进行计算，而是创建一个带有该操作符的节点，并将其设置为弹出元素的父节点。然后将该节点推回到栈中。

这种方法的缺点是需要额外的步骤来创建树。

最后的注意事项

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

- Tibi

Answer 2

这里是从中缀字符串创建二叉表达式树的C++代码。

- Kurt Krueckeberg