首页 > 代码库 > 逆波兰表达式(后缀表达式)
逆波兰表达式(后缀表达式)
前/中/后缀表达式的转换
自然表达式转换为前/中/后缀表达式，其实是很简单的。首先将自然表达式按照优先级顺序，构造出与表达式相对应的二叉树，然后对二叉树进行前/中/后缀遍历，即得到前/中/后缀表达式。
举例说明将自然表达式转换成二叉树：
a×(b+c)-d
① 根据表达式的优先级顺序，首先计算(b+c)，形成二叉树
②然后是a×(b+c)，在写时注意左右的位置关系
③最后在右边加上 -d
然后最这个构造好的二叉树进行遍历，三种遍历的顺序分别是这样的：
① 前序遍历：根-左-右
② 中序遍历：左-根-右
③ 后序遍历：左-右-根
所以还是以刚才的这个例子，在最终二叉树的基础上可以得出：
前缀表达式：-*a+bcd
中缀表达式：a*b+c-d
后缀表达式：abc+*d-
转自 http://www.blogjava.net/wxqxs/archive/2009/05/21/277336.html
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。