从数学表达式创建二叉树

Question

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

  +
 / \
2   +
   / \
  1   1

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

Answer 1

我有一个类似的项目,这就是我做的方式:

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

   '(' Open parantheses
   '11' Number
   '+' Operator etc

2. 将表达式转换为postfix(或前缀,如果需要)表示法.可以做到这一点的一种算法叫做Shunting Yard算法.后缀表示法的优点是,您可以使用基于堆栈的方法(或二进制树,如果需要)更轻松地评估表达式.

3. 评估后缀表达式.您可以通过两种方式执行此操作,即二叉树和堆栈.

堆栈评估:

以postfix表示法转换的示例表达式如下所示:

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

这种方法的缺点是你还有一个额外的步骤:创建树.

最后的笔记

这是我将使用的方法.也许有比这更有效的方法,但这就是我要做的.