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

 

思路：

　　递归大模拟（代码直白如话）；

 

来，上代码：

#include
      
       #include
       
        #include
        
         using namespace std;int len,now=0;char str[100001];double search(char type){    while((str[now]!='*'&&str[now]!='/'&&str[now]!='-'&&str[now]!='+')&&(str[now]<'0'||str[now]>'9'))    {        now++;    }    double a=0,b=0;    if(str[now]=='*'||str[now]=='-'||str[now]=='/'||str[now]=='+') a=search(str[now++]);    else    {        bool if_=true;        double now_=1;        while((str[now]>='0'&&str[now]<='9')||str[now]=='.')        {            if(str[now]=='.')            {                if_=false;                now++;                continue;            }            if(if_)            {                a=a*10+str[now]-'0';                now++;            }            else            {                now_*=10;                a+=(str[now]-'0')/now_;                now++;            }        }    }    while((str[now]!='*'&&str[now]!='/'&&str[now]!='-'&&str[now]!='+')&&(str[now]<'0'||str[now]>'9'))    {        now++;    }    if(str[now]=='*'||str[now]=='-'||str[now]=='/'||str[now]=='+') b=search(str[now++]);    else    {        bool if_=true;        double now_=1;        while((str[now]>='0'&&str[now]<='9')||str[now]=='.')        {            if(str[now]=='.')            {                if_=false;                now++;                continue;            }            if(if_)            {                b=b*10+str[now]-'0';                now++;            }            else            {                now_*=10;                b+=(str[now]-'0')/now_;                now++;            }        }    }    if(type=='*') return a*b;    if(type=='/') return a/b;    if(type=='+') return a+b;    if(type=='-') return a-b;}int main(){    gets(str);    len=strlen(str);    printf("%.6lf",search(str[now++]));    return 0;}