概念
前缀表达式(Prefix Notation)是指将运算符写在前面操作数写在后面的不包含括号的表达式,而且为了纪念其发明者波兰数学家Jan Lukasiewicz,所以前缀表达式也叫做“波兰表达式”
后缀表达式(Postfix Notation)与之相反,是指运算符写在操作数后面的不包含括号的算术表达式,也叫做逆波兰表达式
中缀表达式(Infix Notation)就是常用的将操作符放在操作数中间的算术表达式。前缀表达式和后缀表达式相对于中缀表达式最大的不同就是去掉了表示运算符优先级的括号
与二叉树关系
前缀表达式对应于二叉树的前序遍历
中缀表达式对应于二叉树的中序遍历
后缀表达式对应于二叉树的后序遍历
表达式转换
中缀转后缀
首先介绍一个人工转换的方法,假设有一个中缀表达式a+b*c-(d+e)
1首先将这个中缀表达式的所有运算加括号((a+(b*c))-(d+e))
2然后将所有运算符放到括号后面,这样就变成了((a(bc)* )+ (de)+ )-
3把所有括号去掉abc*+de+-,最后得出的结果就是后缀表达式
上面这个方法可以在比如做题分析的时候用人脑的时候使用,接下来介绍用程序实现将中缀转换成后缀表达式的思路
1 建立一个栈,然后从左至右的遍历中缀表达式
2 如果碰到了操作数,则直接将其输出,如果碰到了操作符,这个时候则需要进行优先级的比较,如果栈为空或者栈顶的操作符的优先级比当前的低,则将当前的操作符Push入栈,如果栈顶操作符比当前的操作符的优先级高或者相同,则POP操作符并输出,直到出现前一种情况为止
3 需要注意的是对于括号需要另外注意一下,如果是’(’,则直接入栈,如果是)则要找到对应的’(’为止,并且当两者同时出现时则同时删除
下面模拟程序对a+b*c-(d+e)求中缀表达式,首先对其进行扫描
输出 a 栈底 栈顶
输出 a 栈底 + 栈顶
输出 a b 栈底 + 栈顶
输出 a b 栈底 + * 栈顶
输出 a b c 栈底 + * 栈顶
输出 a b c * 栈底 + 栈顶
输出 a b c * + 栈底 - 栈顶
输出 a b c * + 栈底 - ( 栈顶
输出 a b c * + d 栈底 - ( 栈顶
输出 a b c * + d 栈底 - ( + 栈顶
输出 a b c * + d e 栈底 - ( + 栈顶
输出 a b c * + d e + 栈底 -( 栈顶
输出 a b c * + d e + - 栈底 栈顶
中缀转前缀
1 转换后缀表达式由于符号是要在操作数后面出现,所以操作数入栈,扫描顺序是从左向右,转换前缀表达式的话操作符需要在操作数前面出现,那么扫描顺序就应该是从右向左。
2 操作符的具体处理方式和转换到后缀表达式略有不同
3 括号的操作也是’)’直接入栈,’(’则配对’)’后一起出栈
如: 2*3/(2-1)+5*(4-1)转化后为+/*23-21*5-41
// 中缀转前缀/*
参考算法
1)求输入串的逆序。
2)检查输入的下一元素。
3)假如是操作数,把它添加到输出串中。
4)假如是闭括号,将它压栈。
5)假如是运算符,则
i)假如栈空,此运算符入栈。
ii)假如栈顶是闭括号,此运算符入栈。
iii)假如它的优先级高于或等于栈顶运算符,此运算符入栈。
iv)否则,栈顶运算符出栈并添加到输出串中,重复步骤5。
6)假如是开括号,栈中运算符逐个出栈并输出,直到遇到闭括号。闭括号出栈并丢弃。
7)假如输入还未完毕,跳转到步骤2。
8)假如输入完毕,栈中剩余的所有操作符出栈并加到输出串中。
参考资料:
http://blog.csdn.net/wzy_1988/article/details/11179281#
http://www.cnblogs.com/MichaelYin/archive/2012/05/02/2479248.html
http://blog.renren.com/share/289954979/9182682231