首页 > 代码库 > 波兰、逆波兰表达式
波兰、逆波兰表达式
软考习题里遇到了这样一道题,给出了一个逆波兰式,让求它对应的中缀表达式。
逆波兰式:ab-cd+* ,它的中缀表达式是(a-b)*(c+d)
思考:
这让我蒙圈了,这是为什么呢。怎么得到的呢,应该有什么规律的吧。
首先我们要知道:
波兰式:前缀表达式
逆波兰式:后缀表达式
了解这三个表达式之前,我们需要知道
表达式 | 解释 | 例子 |
前缀 | 不含括号的的算数表达式,将运算符写在前面,操作数写在后面 | *+ 2 1 3 |
中缀 | 必须含括号,操作符处于操作数的中间 | (2+1)*3 |
后缀 | 不含括号,运算符放在两个运算对象的后面。 | 3 2 + 3 * |
这三个表达式的重点就是他们之间的转换,学会转换,对这三个表达式也就了解的差不多了,那么到底怎么转换的呢?
给出一个中缀表达式,转化为前缀和后缀表达式。
例如我们做的这道题,中缀表达式答案是(a-b)*(c+d),我们看来验证一下他正确不。
步骤:
第一步:按照运算符的优先级,对所有的运算单位加括号。
((a-b)*(c+d))
第二步转换:
转换为前缀:把运算符号移动到对应的括号前面,然后去掉括号。
“*”移最前面;“-”移到 -(ab);“+”移到+(cd)
得到:*-(ab)+(cd)去括号后:*-ab+cd
转换为后缀:
“*”移到最后;“-”移到(ab)-;“+”移到(cd)+
得到:(ab)-(cd)+*去括号后:ab-cd+*
以上方法适用于较为简单的选择题,对于真正的算法题我觉得就给多想想了。
对于前缀、中缀和后缀的知识不仅是是他们的转化,还有很多知识,以后会再了解的。
而对于逆波兰式,冲着这么好听的名字,也得明白他是什么吧,其实就是波兰逻辑学家的一个人发明的一种表示表达式的方式。这种表示法的优点就是根据运算对象和算符的出现次序进行计算,便于用栈实现求值。
只学会了简单的转换,对于这方面的认识还远远不够,其实中缀表达式转化为后缀表达式也是数据结构里的一个算法题。逆波兰表达式只用于两种简单操作,入栈和出栈。按顺序扫描逆波兰表达式,如果当前字符是变量或者数字就压栈,如果是运算符,则将栈顶两个元素弹出想想运算,结果再入栈,最后当表达式扫描完后,栈里就是结果。
个人理解的不是很深刻,具体到算法题估计还是有一定的困难,不过走一步算一步,能理解多少是多少。这个算法会不会考也不知道,不总结就更不认识了。先总结了再说,有什么错误请大家指点,互相交流。
波兰、逆波兰表达式