|
以文本方式查看主题 - 中文XML论坛 - 专业的XML技术讨论区 (http://bbs.xml.org.cn/index.asp) -- 『 计算机考研交流 』 (http://bbs.xml.org.cn/list.asp?boardid=67) ---- [DS]表达式树转中缀表达式的非递归算法 (http://bbs.xml.org.cn/dispbbs.asp?boardid=67&rootid=&id=41566) |
|
-- 作者：Smilingface -- 发布时间：12/24/2006 7:45:00 PM -- [DS]表达式树转中缀表达式的非递归算法 今年的一道课后思考题，没想出来，也没Google到，期盼有高手出招！ Thank you!! |
|
-- 作者：telejax -- 发布时间：12/25/2006 2:50:00 PM -- 后序可以吗？ |
|
-- 作者：Smilingface -- 发布时间：12/26/2006 5:16:00 PM -- 不能吧，得中缀表达式只能用中序周游吧，或者你说说看怎么做？
|
|
-- 作者：mxf3306 -- 发布时间：12/26/2006 11:33:00 PM -- 前面不是有递归算法吗，把它转为非递归应该就可以了吧。具体实现可能较困难，但我觉得这是最直观解法。 |
|
-- 作者：binaryluo -- 发布时间：12/30/2006 7:04:00 PM --
这个问题应该就是求“树的中序遍历的非递归算法”啊——只要中序遍历表达式树就可以得到中缀表达式了。 树的中序遍历非递归算法在清华大学出版的《数据结构 （C语言版）》P130有。
|
|
-- 作者：teng_t1986 -- 发布时间：12/30/2006 11:05:00 PM -- 其实很简单啊，不过是括号不好加吧，呵呵：） 不妨告诉你我的方案：（我是指括号处理） 1.只有在父节点（下设F）为“*”或“/”或“-”时才有可能出现括号问题，以下简便起见就拿F="*",子节点（S1左，S2右）为“+”为例吧； 2.关键：在中序遍历到F时判断是否符合加括号的条件，如果要加括号，直接在中缀序列中加“（”，并且把“）”压栈（当然，是在F之后压栈）； 3.右边节点一样处理，即弹出F时再判断F和S2是否符合添括号的条件，如果要添括号，先在中缀序列中输入“（”，再将“）”压栈。 就是这样…… |
|
W 3 C h i n a ( since 2003 ) 旗 下 站 点 苏ICP备05006046号《全国人大常委会关于维护互联网安全的决定》《计算机信息网络国际联网安全保护管理办法》 |
46.875ms |