首页 > 代码库 > 前缀表达式求解
前缀表达式求解
问题描述:
前缀表达式也叫波兰表达式,是将操作符前置的一种写法。
中缀到前缀示例:
( 4 + 2 ) * ( 3 + 6 ) => * + 4 2 + 3 6
(3 + 4 / 2) - 5 => - + 3 / 4 2 5
思路1(递归):
1. 从左向右扫描
2. 因为前缀表达式里都是双目运算符,且没有括号,所以遇到操作符可以递归求解,例如遇到乘号:
case ‘*‘:
return exp() * exp();
思路2(栈):
1. 维护数字栈
2. 从右向左扫描,遇到数字则入栈,遇到符号则出栈两个数字,计算后再入栈新数字,前缀表达式与后缀表达式求法对称,所以直接按后缀法相反方向求解即可。
转载请注明引用自:
http://www.cnblogs.com/breakthings/p/4051773.html
前缀表达式求解
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。