HDU 1237 简单计算器（后缀式+栈）
最后更新于：2022-04-01 16:02:24
# 简单计算器
**Time Limit: 2000/1000 MS (Java/Others) Memory Limit: 65536/32768 K (Java/Others)
Total Submission(s): 16351 Accepted Submission(s): 5604**
Problem Description
读入一个只包含 +, -, *, / 的非负整数计算表达式，计算该表达式的值。
Input
测试输入包含若干测试用例，每个测试用例占一行，每行不超过200个字符，整数和运算符之间用一个空格分隔。没有非法表达式。当一行中只有0时输入结束，相应的结果不要输出。
Output
对每个测试用例输出1行，即该表达式的值，精确到小数点后2位。
Sample Input
~~~
1 + 2
4 + 2 * 5 - 7 / 11
0
~~~
Sample Output
~~~
3.00
13.36
~~~
1.将原表达式转为后缀式在求值
2.代码：
~~~
#include<cstdio>
#include<cstring>
#include<stack>
using namespace std;
char s[1000];
int ss[1000];
int a[1000];
char s1[100];
char s2[1000];
int hsh[300];
int e[10];
int main()
{
hsh['#']=-1;
hsh['+']=0;
hsh['-']=0;
hsh['*']=1;
hsh['/']=1;
e[0]=1;
e[1]=10;
e[2]=100;
e[3]=1000;
e[4]=10000;
e[5]=100000;
e[6]=1000000;
e[7]=10000000;
e[8]=100000000;
e[9]=1000000000;
while(gets(s))
{
if(strcmp(s,"0")==0)
break;
int len=strlen(s);
int pos=0;
stack<char> S;
S.push('#');
s[len]=' ';
int j=0;
int k=0;
int l=0;
for(int i=0; i<=len; i++)
{
if(s[i]>='0'&&s[i]<='9')
s1[j++]=s[i];
else if(s[i]==' ')
{
int x=0;
for(int jj=0; jj<j; jj++)
{
x+=(s1[jj]-'0')*e[j-1-jj];
}
if(j!=0)
a[l++]=x;
j=0;
}
else
s2[k++]=s[i];
}
s2[k]='#';
for(int i=0; i<=k+l; i++)
{
if(i%2==1)
{
while(!S.empty()&&hsh[S.top()]>=hsh[s2[i/2]])
{
if(S.top()!='#')
{
char cc=S.top();
if(cc=='+')
ss[pos++]=-1;
if(cc=='-')
ss[pos++]=-2;
if(cc=='*')
ss[pos++]=-3;
if(cc=='/')
ss[pos++]=-4;
};
S.pop();
}
S.push(s2[i/2]);
}
else
ss[pos++]=a[i/2];
}
stack<double> SS;
for(int i=0; i<pos; i++)
{
if(ss[i]>=0)
{
double x=(double)ss[i];
SS.push(x);
}
else
{
double sec=SS.top();
SS.pop();
double fir=SS.top();
SS.pop();
if(ss[i]==-1)
{
fir=fir+sec;
}
if(ss[i]==-2)
{
fir=fir-sec;
}
if(ss[i]==-3)
{
fir=fir*sec;
}
if(ss[i]==-4)
{
fir=fir/sec;
}
SS.push(fir);
}
}
printf("%.2lf\n",SS.top());
}
return 0;
}
~~~