NYOJ-128 前缀式的计算

先说明一下什么是中缀式：

如2+(3+4)*5这种我们最常见的式子就是中缀式。

而把中缀式按运算顺序加上括号就是：(2+((3+4)*5))

然后把运算符写到括号前面就是+(2 *( +(3 4) 5) )

把括号去掉就是：+ 2 * + 3 4 5

最后这个式子就是该表达式的前缀表示。

给你一个前缀表达式，请你计算出该前缀式的值。

比如：

+ 2 * + 3 4 5的值就是 37

输入

有多组测试数据，每组测试数据占一行，任意两个操作符之间，任意两个操作数之间，操作数与操作符之间都有一个空格。输入的两个操作数可能是小数，数据保证输入的数都是正数，并且都小于10，操作数数目不超过500。
以EOF为输入结束的标志。

输出

对每组数据，输出该前缀表达式的值。输出结果保留两位小数。

样例输入

+ 2 * + 3 4 5
+ 5.1 / 3 7

样例输出

37.00
5.53

花了近一个钟，写了个又丑又长的代码，思路是想把前缀式转换成后缀式，一大堆字符串处理、、、被搞晕了。转换成前缀式后就容易很多了。遇到数字就入栈，遇到符号就出栈两次运算后再入栈。

 
#include<stdio.h>
#include<stdlib.h>
#include<string.h>
#define SIZE 100
#define N 1000
typedef struct 
{
    float *pTop;
    float *pBase;
    int lenght;
}STK,*pSTK;
int InitStk(pSTK Stk)
{
    Stk->pTop=(float*)malloc(sizeof(float)*SIZE);
    if(Stk->pTop == NULL)
    {
        return 0;
    }
    Stk->pBase=Stk->pTop;
    Stk->lenght=0;
    return 1;
}
int Push(pSTK Stk,float x)
{
    if(Stk->lenght>=SIZE)
    {
        return 0;
    }
    *(Stk->pTop++)=x;
    Stk->lenght++;
    return 1;
}
int Pop(pSTK Stk,float *x)
{
    if(Stk->lenght==0)
    {
        return 0;
    }
    *x=*(--Stk->pTop);
    Stk->lenght--;
    return 1;
}
int main()
{
    STK Stk;
    InitStk(&Stk);
    char str[N],res[N];
    while((gets(str))!=NULL)
    {
        int i,j=0,len=strlen(str);
        for(i=len-1;i>=0;i--)
        {
            res[j++]=str[i];
        }
        res[j]=0;

        char *p=res,*q=res;
        while(q<&res[len-1])
        {
            while(*q!=' '&&*q!='+'&&*q!='-'&&*q!='*'&&*q!='/')
            {
                q++;
            }
            char *r1=p,*r2=q-1,ch;
            while(r1<r2)
            {
                ch=*r1;
                *r1=*r2;
                *r2=ch;
                r1++,r2--;
            }
            while(*q==' '||*q=='+'||*q=='-'||*q=='*'||*q=='/')
            {
                q++;
            }
            p=q;
        }
        float a,b,c;
        for(i=0;i<len;i++)
        {
            if(res[i]=='+')
            {
                Pop(&Stk,&a);
                Pop(&Stk,&b);
                c=a+b;
                Push(&Stk,c);
            }
            else if(res[i]=='-')
            {
                Pop(&Stk,&a);
                Pop(&Stk,&b);
                c=a-b;
                Push(&Stk,c);
            }
            else if(res[i]=='*')
            {
                Pop(&Stk,&a);
                Pop(&Stk,&b);
                c=a*b;
                Push(&Stk,c);
            }
            else if(res[i]=='/')
            {
                Pop(&Stk,&a);
                Pop(&Stk,&b);
                c=a/b;
                Push(&Stk,c);
            }
            else if(res[i]==' ')
            {
                NULL;
            }
            else
            {
                sscanf(&res[i],"%f",&a);
                Push(&Stk,a);
                while(res[i]!=' ')
                {
                    i++;
                }
            }
        }
        Pop(&Stk,&a);
        printf("%.2f\n",a);
    }
    return 0;
}