南阳理工-35-程序员宅基地

http://acm.nyist.net/JudgeOnline/problem.php?pid=35

#include<iostream>
#include<cstdio>
#include<cstring>
#include<stack>
#include<algorithm>

using namespace std;
const int maxn=10007;
char a[maxn], b[maxn];
stack<char> S;
stack<double> S1;

int Priority(char ch)
{
    int i;
    switch(ch)
    {
    case '+':
    case '-':
        i=1;
        break;
    case '*':
    case '/':
        i=2;
        break;
    default :
        i=-1;
        break;
    }
    return i;
}
///中缀表达式转后缀表达式
void ToPoland()
{
    int i=0, j=0;
    int len=strlen(a);
    S.push('@');
    while(i < len-1)
    {
        if(a[i]=='(')
        {
            S.push(a[i]);
            i++;
        }
        else if(a[i]==')')
        {
            while(S.top()!='(')
            {
                b[j++]=S.top();
                b[j++]=' ';
                S.pop();
            }
            S.pop();
            i++;
        }
        else if(a[i]=='+' || a[i]=='-' || a[i]=='*' || a[i]=='/')
        {
            while(Priority(a[i]) <= Priority(S.top()))
            {
                b[j++]=S.top();
                b[j++]=' ';
                S.pop();
            }
            S.push(a[i]);
            i++;
        }
        else
        {
            while((a[i]>='0'&&a[i]<='9') || a[i]=='.')
            {
                b[j++]=a[i++];
            }
            b[j++]=' ';
        }
    }
    while(S.top()!='@')
    {
        b[j++]=S.top();
        b[j++]=' ';
        S.pop();
    }
    S.pop();
}
///求逆波兰表达式的值
double Count_Poland()
{
    double p, q, u, v;
    for(int i=0; b[i]; i++)
    {
        p=q=0;
        if((b[i]>='0'&&b[i]<='9') || b[i]=='.')
        {
            while((b[i]>='0'&&b[i]<='9') || b[i]=='.')
            {
                if(b[i]=='.')
                {
                    i++;
                    double x=1;
                    while(b[i]>='0'&&b[i]<='9')
                    {
                        x*=0.1;
                        q=q+(b[i]-'0')*x;
                        i++;
                    }
                }
                else
                {
                    p=p*10+(b[i]-'0');
                    i++;
                }
            }
            S1.push(p+q);
        }
        else
        {
            if(b[i]=='+')
            {
                u=S1.top();
                S1.pop();
                v=S1.top();
                S1.pop();
                S1.push(v+u);
            }
            else if(b[i]=='-')
            {
                u=S1.top();
                S1.pop();
                v=S1.top();
                S1.pop();
                S1.push(v-u);
            }
            else if(b[i]=='*')
            {
                u=S1.top();
                S1.pop();
                v=S1.top();
                S1.pop();
                S1.push(v*u);
            }
            else if(b[i]=='/')
            {
                u=S1.top();
                S1.pop();
                v=S1.top();
                S1.pop();
                S1.push(v/u);
            }
        }
    }
    return S1.top();
}
int main()
{
    int n;
    scanf("%d", &n);

    while(n--)
    {
        scanf("%s", a);
        ToPoland();
        printf("%.2f\n", Count_Poland());
    }
    return 0;
}