题目描述

逆波兰记法中，操作符置于操作数的后面。例如表达“三加四”时，写作“3 4 +”，而不是“3 + 4”。如果有多个操作符，操作符置于第二个操作数的后面，所以常规中缀记法的“3 - 4 + 5”在逆波兰记法中写作3 4 - 5 +”：先3减去4，再加上5。

使用逆波兰记法的一个好处是不需要使用括号。

想知道更多关于逆波兰式的知识的同学们可以移步百度百科

格式

输入

输入一个逆波兰表达式，其中数字不超过 1000 项，各项间用一个空格隔开，保证式子正确，运算符只包括加+、减-、乘*、除/。

输出

输出其运算结果，保留 2 位有效数字。

示例

输入数据 1

1 2 + 3 * 2 /

输出数据 1

4.50

限制

1s, 1024KiB for each test case.

所有浮点数值的绝对值均小于 10^10。

思路

题目说数有可能是浮点，那就一律按浮点做吧！

因为这种算式书写顺序的特殊性，我们不妨使用栈来做。

想知道更多关于栈的知识的同学们也可以移步百度百科

思考一下，弄一个存放数的栈就行了，读取到运算符我就弹栈运算。

我的具体思路如下图所示：

输入的一会是数一会是运算符，普通的读取方式显然不行，此时我们就要使用字符串了。

另外，题目说明了保证算式一定正确，我们就不用再考虑是否合法什么的了，不过为了装逼保证程序运行结果正确，我们还是要判一下输入的是否就是一个数。

bool Isanumber(char str[]){double ans=0,t=1;for(int i=strlen(str)-1;i>=0;i--){ans+=(str[i]-48)*t;t*=10;}if(ans==atof(str)) return true;//验证else return false;
}

这里用到了一个函数 atof()，它干的活就是把一个字符串转换成一个浮点数。

*atof()函数需要头文件库<stdlib.h>

比如说我有一个字符串char s[10]=“11451.4”，atof(s)的结果就是返回一个浮点数11451.4。

言归正传。

前面说过，输入的是个字符串，所以少不了处理亿下。

此处我的思路如下图所示：

代码：

double trans(int a){double ans=0;int cnt=0;char digits[900700]="";for(int i=a;str[i]!=' ';i++){digits[cnt]=str[i];cnt++;}ans=atof(digits);return ans;
}

也别忘了计算！

double calc(double a,double b,char opr){if(opr=='+') return a+b;else if(opr=='-') return a-b;else if(opr=='*') return a*b;else if(opr=='/') return a/b;
}

搞清楚了这些，就该加上栈了！

那么，最终的代码也就来了！

#include<bits/stdc++.h>
using namespace std;
char str[900700];
std::stack <double> stk;//定义栈
double trans(int a){double ans=0;int cnt=0;char digits[900700]="";for(int i=a;str[i]!=' ';i++){digits[cnt]=str[i];cnt++;}ans=atof(digits);return ans;
}
double calc(double a,double b,char opr){if(opr=='+') return a+b;else if(opr=='-') return a-b;else if(opr=='*') return a*b;else if(opr=='/') return a/b;
}
bool Isanumber(char str[]){double ans=0,t=1;for(int i=strlen(str)-1;i>=0;i--){ans+=(str[i]-48)*t;t*=10;}if(ans==atof(str)) return true;else return false;
}
int main(){cin.getline(str,900600);//读取算式（带有空格）if(Isanumber(str)==true){//判断输入的是否为单个数cout<<fixed<<setprecision(2)<<atof(str);return 0;}double tmp,a,b;for(int i=0;str[i];i++){if(str[i]>='0'&&str[i]<='9'){//读取数tmp=trans(i);stk.push(tmp);while (str[i]!=' ') i++;//从前向后读取，读到空格就结束}else if(str[i]=='+'||str[i]=='-'||str[i]=='*'||str[i]=='/'){//读到运算符，开始运算b=stk.top();//弹出第二个待运算数stk.pop();a=stk.top();//弹出第一个待运算数stk.pop();stk.push(calc(a,b,str[i]));//计算，并将结果压回栈里}}cout<<fixed<<setprecision(2)<<stk.top();return 0;
}

（这里的警告不用管他）