逆波兰表达式

一直觉得递归还是很好理解的，看得懂，会用，原来我一直用的不够熟练，还可以用得这么巧妙啊。。。

逆波兰表达式是一种把运算符前置的算术表达式，例如普通的表达式
2 + 3的逆波
兰表示法为
+ 2 3。逆波兰表达式的优点是运算符之间不必有优先级关系，也不必用括号
改变运算次序，例如(2 + 3) * 4的逆波兰表示法为
* + 2 3 4。本题求解逆波兰表达式的值，
其中运算符包括 + -* /四个。


输入数据


输入为一行，其中运算符和运算数之间都用空格分隔，运算数是浮点数


输出要求


输出为一行，表达式的值。


176



输入样例




* + 11.0 12.0 + 24.0 35.0


输出样例




1357.000000


解题思路


这个问题看上去有些复杂，如果只是简单地模拟计算步骤不太容易想清楚，但是如
果用递归的思想就非常容易想清楚。让我们根据逆波兰表达式的定义进行递归求解。在
递归函数中，针对当前的输入，有五种情况：
1）输入是常数，则表达式的值就是这个
常数；2）输入是
’+’，则表达式的值是再继续读入两个表达式并计算出它们的值，然后
将它们的值相加；
3）输入是
’-’；4）输入是
’*’； 5）输入是
’/’；后几种情况与
2）相同，
只是计算从
’+’变成’-’，’*’，’/’。


参考程序

1. #include <stdio.h> 
2. #include<math.h> 
3. double exp(){ 
4. char a[10]; 
5. scanf("%s", a); 
6. switch(a[0]){ 
7. case'+': return exp( ) + exp( ); 
8. case'-': return exp( ) - exp( ); 
9. case'*': return exp( ) * exp( ); 
10. case'/': return exp( ) / exp( ); 
11. default: return atof(a); 
12. } 
13. } 
14. void main() 
15. { 
16. double ans; 
17. ans = exp(); 
18. printf("%f", ans); 
19. } 

实现中常见的问题


问题一：不适应递归的思路，直接分析输入的字符串，试图自己写进栈出栈的程序，
写得逻辑复杂后，因考虑不周出错；


问题二：不会是用
atof()函数，自己处理浮点数的读入，逻辑复杂后出错。

评论

1 楼 qingfeng200468 2013-07-01  

【2 + 3的逆波兰表示法为+ 2 3。】这句写错了，应该是波兰表示法