2叉树

20080030成电

要计算1*(2+3),先转成逆波兰123+*,在利用栈就可以得到答案了。
树的后缀遍历就得到逆波兰式。有什么方法可以把1*(2+3)转成
2叉树？

福瑞哈哥

请使用bison。

20080030成电

我对CU感到失望了


斑竹 如何注销ID？

yangyufeng507

你对做人失望吗，小帅哥

lenovo

干嘛要转化成二叉树才能计算呢？

MMMIX

原帖由 20080030成电 于 2007-7-25 19:33 发表
我对CU感到失望了


斑竹 如何注销ID？

直接不登录就完了。

局内人

原帖由 20080030成电 于 2007-7-25 15:21 发表
要计算1*(2+3),先转成逆波兰123+*,在利用栈就可以得到答案了。
树的后缀遍历就得到逆波兰式。有什么方法可以把1*(2+3)转成
2叉树？

这个跟中缀转后缀是类似的。

以 a+(b+c)*d  为例子，你用两个栈，一个装符号，一个装指向二叉树的指针

1. 
   
2. a b c
   
3. + ( +              <-- )
   

复制代码

此时弹出 +, 并与 b c 结合，合并成二叉树 (+ b c)，然后把指向这棵树的指针压回数据栈，得到

1. 
   
2. a (+ b c)
   
3. + (                 <--)
   

复制代码

象中缀转后缀那样继续

1. 
   
2. a (+ b c) f
   
3. + *
   

复制代码

现在串已经扫描完毕，做最后的处理

1. 
   
2. a (* (+ b c) f)
   
3. +
   

复制代码

1. 
   
2. (+ a (* (+ b c) f))
   

复制代码

done.

[ 本帖最后由 局内人 于 2007-7-27 09:00 编辑 ]

Jiangge

看看编译原理是怎么处理的，你就知道了。

简单点说：

就是从左->右扫描字符串，为操作数建树节点（即叶子节点）、为操作符建立树节点（非叶子节点），同时考虑算术符号的优先级，即可建立2X树。