1696:逆波兰表达式

总时间限制:

1000ms

内存限制:

65536kB

描述

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

输入

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

输出

输出为一行，表达式的值。
可直接用printf("%f\n", v)输出表达式的值v。

样例输入

* + 11.0 12.0 + 24.0 35.0

样例输出

1357.000000

提示

可使用atof(str)把字符串转换为一个double类型的浮点数。atof定义在math.h中。
此题可使用函数递归调用的方法求解。

来源

计算概论05

(非递归)

 1 #include<cstdio>
 2 #include<cstring>
 3 #include<cstdlib>
 4 using namespace std;
 5 void px(double ans[],int t,int oo)
 6 {
 7     for(int l=t;l<oo;l++)
 8     {
 9         double p=ans[l+1];
10         ans[l]=p;
11         ans[l+1]=0;
12     }
13 }
14 int main()
15 {
16     char s[110],k[110];
17     gets(s);
18     double ans[110];
19     int len=strlen(s),i=0,n=0,lens=0,lenans=0;
20     while(i<len)
21     {
22         if(s[i]>=‘0‘&&s[i]<=‘9‘||s[i]==‘.‘)
23         {
24         while(s[i]>=‘0‘&&s[i]<=‘9‘||s[i]==‘.‘)
25         {
26             k[n]=s[i];
27             i++;n++;
28         }
29         ans[lenans]=atof(k);
30         lenans++;
31         memset(k,0,sizeof(k));
32         n=0;
33         }
34         else i++;
35         
36     }
37     for(int j=len-1;j>=0;j--)
38     {
39         if(s[j]==‘ ‘&&s[j+1]!=‘+‘&&s[j+1]!=‘-‘&&s[j+1]!=‘/‘&&s[j+1]!=‘*‘)
40         {
41             lens++;
42         }
43         else 
44         {
45             if(s[j]==‘+‘||s[j]==‘-‘||s[j]==‘/‘||s[j]==‘*‘)
46             {
47                 switch(s[j])
48                 {
49                     case ‘+‘:ans[lenans-lens]+=ans[lenans-lens+1];px(ans,lenans-lens+1,lenans-1);break;
50                     case ‘-‘:ans[lenans-lens]-=ans[lenans-lens+1];px(ans,lenans-lens+1,lenans-1);break;
51                     case ‘*‘:ans[lenans-lens]*=ans[lenans-lens+1];px(ans,lenans-lens+1,lenans-1);break;
52                     case ‘/‘:ans[lenans-lens]/=ans[lenans-lens+1];px(ans,lenans-lens+1,lenans-1);break;
53                 }
54             }
55         }
56     }
57     printf("%lf",ans[0]);
58     return 0;
59 }

 

(递归)

 1 #include<cstdio>
 2 #include<cstdlib>
 3 using namespace std;
 4 double js()
 5 {
 6     char t[20];
 7     scanf("%s",t);
 8     switch(t[0])
 9     {
10         case ‘+‘:return js()+js();
11         case ‘-‘:return js()-js();
12         case ‘*‘:return js()*js();
13         case ‘/‘:return js()/js();
14         default :return atof(t);
15     }
16 }
17 int main()
18 {
19     printf("%lf",js());
20     return 0;
21 }