从数学表达式创建二叉树

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

  + / \ 2 + / \ 1 1 

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

Answer 1

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

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

     '（'开放的parantheses
    '11'号码
    '+'运营商等 

2. 将表达式转换为postfix （或前缀，如果需要）表示法。 可以做到这一点的一种算法叫做Shunting 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 ++代码 。