Decode360's Blog

业精于勤而荒于嬉 QQ:150355677 MSN:decode360@hotmail.com

  BlogJava :: 首页 :: 新随笔 :: 联系 ::  :: 管理 ::
  302 随笔 :: 26 文章 :: 82 评论 :: 0 Trackbacks
前/中/后缀表达式的转换
 
 
    自然表达式转换为前/中/后缀表达式,其实是很简单的。首先将自然表达式按照优先级顺序,构造出与表达式相对应的二叉树,然后对二叉树进行前/中/后缀遍历,即得到前/中/后缀表达式。
 
    举例说明将自然表达式转换成二叉树:
 
    a×(b+c)-d
 
    ① 根据表达式的优先级顺序,首先计算(b+c),形成二叉树
    tree1.JPG
   
    然后是a×(b+c),在写时注意左右的位置关系
    tree2.JPG
 
    最后在右边加上 -d
    tree3.JPG
 
 
    然后最这个构造好的二叉树进行遍历,三种遍历的顺序分别是这样的:
 
    ① 前序遍历:根-左-右
    中序遍历:左-根-右
    后序遍历:左-右-根
 
    所以还是以刚才的这个例子,在最终二叉树的基础上可以得出:
 
    前缀表达式:-*a+bcd
    中缀表达式:a*b+c-d
    后缀表达式:abc+*d-
 
 
 
    一些其他的遍历原则:
 
    1、深度优先遍历:
 
    首先访问出发点V,并将其标记为已访问过;然后依次从V出发搜索V的每个邻接点W。若W未曾访问过,则以W为新的出发点继续进行深度优先遍历,直至图中所有和源点V有路径相通的顶点(亦称为从源点可达的顶点)均已被访问为止。若此时图中仍有未访问的顶点,则另选一个尚未访问的顶点作为新的源点重复上述过程,直至图中所有顶点均被访问为止。
 
    2、广度优先遍历:
 
    首先访问出发顶点V,然后访问与顶点V邻接的全部未被访问过的顶点W0,W1,...WK-1;接着再依次访问与顶点W0,W1,...WK-1邻接的全部未被访问过的顶点,以此类推,直至图的所有顶点都被访问到,或出发顶点V所在的连通分量的全部顶点都被访问到为止。
 
    注:对于树来说,深度优先就是从左到右,从上到下;广度优先就是从上到下,从左到右。
 




-The End-

posted on 2009-05-21 22:41 decode360-3 阅读(7468) 评论(3)  编辑  收藏 所属分类: Exam

评论

# re: 前/中/后缀表达式的转换 2012-09-02 14:18 captivated
LZ: 你怎么根据中缀表达式构建你的二叉树先.

二叉树构建出来后, 前序遍历就是前缀表达式, 中序遍历就是中缀表达式, 后序遍历就是逆波兰式 -- 问题是, 你需要先把二叉树构建出来.

事实上, 这样的二叉树, 需要先将中缀表达式转换为逆波兰式, 然后才能构建出来(别的方法 -- 我反正没试过也不知道). 中缀表达式转换为逆波兰式倒不是太麻烦, 用栈. 逆波兰式表达式构建出二叉树也是用栈, 都不是很麻烦.

所以前提是需要通过栈将中缀表达式转换为逆波兰式. 另外, 以一个简单的计算器程序为例, 这个程序要能够计算形如
1.23 * (3.2 + 5.6) / 5 + 4.0 ( 5.8 - 2.4)
这种表达式的结果. 要求通过上面提及的转换来写(嗯, 有别的更简单的方法来写这种计算器程序. 比如递归).
LZ提过转换很简单明了, 不过我建议LZ不妨编码试试.

-----------------------------------------------------

不得不说. 其实我自己常对这样的转换过程本身感到非常恼火, 觉得自己的大脑常常因为这种转换过程本身而宕机(关于那个计算器程序, 我用过三种方法编码完成过).

-----------------------------------------------------

  回复  更多评论
  

# re: 前/中/后缀表达式的转换 2013-11-22 16:22 刘涛
转换过程一般在实际当中什么时候要用。  回复  更多评论
  

# re: 前/中/后缀表达式的转换 2013-11-22 16:23 刘涛
问题@刘涛
  回复  更多评论
  


只有注册用户登录后才能发表评论。


网站导航: