写在前边的话:你的支持是我写作的动力,有帮助到你的话麻烦点赞加收藏呦。感激不尽!如有错误也请留言指正
别用移动括号的方法了,画树它不香么
中缀表达式转换为后缀表达式可以分为两种方法,一种是利用栈(后文有视频和文字讲解),另一种是画树。题目中没有要求的话,最好不要用栈。强烈推荐画树法。
换出来树,前缀表达式,后缀表达式只需要根据前序遍历和后续遍历即可得到,方便的很
目录
一、画树法
二、利用栈
例题:将中缀表达式a+b-a*((c+d)/e-f)+g转换为等价的后缀表达式ab+acd+e/f-*-g+。【2012年全国试卷试题2 一部分】
画树法是将表达式按照 “+-” 分为几个部分,将 a+b-a*((c+d)/e-f)+g 划分后 a + b - a*((c+d)/e-f) + g,从后向前,以第一个 “+-” 号为根,左边作为左子树,右边作为右子树。
此时,左子树仍然是一个表达式,继续按照上述规则拆分,画树
对于绿色子树,继续按照规则划分子树。对于黄色子树,最外层没有 “+-” 号,按照 “*/” 号划分子树,把括号包起来的当做一个整体
对蓝色子树继续按照规则划分
对橙色子树继续划分
对最后生成的树进行后续遍历,即可得到后缀表达式 ab+acd+e/f-*-g+
对最后生成的树进行前序遍历,即可得到前缀表达式+-+ab*a-/+cdefg
利用栈就是从左向右遍历表达式 a+b-a*((c+d)/e-f)+g,
表达式 | 栈 | 输出 |
---|---|---|
a +b-a*((c+d)/e-f)+g | a | |
a + b-a*((c+d)/e-f)+g | + | |
a+ b -a*((c+d)/e-f)+g | a b | |
a+b - a*((c+d)/e-f)+g | - | a b + |
a+b- a *((c+d)/e-f)+g | a b + a | |
a+b-a * ((c+d)/e-f)+g | -* | |
a+b-a* ( (c+d)/e-f)+g | -*( | |
a+b-a*( ( c+d)/e-f)+g | -*(( | |
a+b-a*(( c +d)/e-f)+g | a b + a c | |
a+b-a*((c + d)/e-f)+g | -*((+ | |
a+b-a*((c+ d )/e-f)+g | a b + a c d | |
a+b-a*((c+d ) /e-f)+g | -*( | a b + a c d + |
a+b-a*((c+d) / e-f)+g | -*(/ | |
a+b-a*((c+d)/ e -f)+g | a b + a c d + e | |
a+b-a*((c+d)/e - f)+g | -*(- | a b + a c d + e / |
a+b-a*((c+d)/e- f )+g | a b + a c d + e / f - | |
a+b-a*((c+d)/e-f ) +g | -* | |
a+b-a*((c+d)/e-f) + g | + | a b + a c d + e / f - * - |
a+b-a*((c+d)/e-f)+ g | a b + a c d + e / f - * - g |
将栈依次弹出,即可获得后缀表达式:ab+acd+e/f-*-g+
附一个此题过程的视频,B站链接https://www.bilibili.com/video/BV1pZ4y1g7Qs/
利用栈将中表达式转换为后缀表达式