是否可以构造一个后缀或前缀形式的树?
问题描述:
让我有一些表达为2*3/(2-1) +5*(4-1)
。这是中缀记法。当然,我可以为这个表达构建一个可以在图像上看到的树。 enter image description here是否可以构造一个后缀或前缀形式的树?
然后,让我们在后缀和前缀形式中编写此表达式。 后缀:2 3 * 2 1 -/5 4 1 - * +
前缀:+/* 2 3 - 2 1 * 5 - 4 1
,问题是:上面的表达式树将是相同的?如果没有,如何构建它?
答
下面是从该前缀表示构建树的草图(认为前缀符号数字和运营商的流):
preocedure buildTree(prefix):
c := first item of prefix
if c is a number then
return a tree node containing the number
else
create a tree node t with c (an operator in this case)
t.left := buildTree(rest of prefix)
t.right := buildTree(rest of prefix)
return t
你应该调用此方法与树的前缀表示。该方法将递归地从中构建子树。
您也可以编写一个类似的方法来从后缀表示中构建树。您需要调整此算法以从右端开始并首先构建正确的子树。
答
如何构建表达式树有大量的资源。 wiki这里有一个很好的参考。
这个想法是,当你遍历每个字符,例如,后缀表达式。
如果字符是一个操作数,然后你把它压入堆栈
如果字符是一个运营商,那么你弹出从栈两个元素,使它们成为当前运营商的童装,然后将操作员推入堆栈。
循环终止后,最终将以堆栈中的单个元素作为树的根。