HDU 1237 简单计算器（后缀式+栈）

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
",SS.top());  
  
    }  
    return 0;  
}