NYOJ 128

前缀式计算

时间限制：1000 ms  |  内存限制：65535 KB

难度：3

描述

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

如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

//NYOJ HDU均AC
#include <cstdio>
#include <cstring>
#include <stack>
#include <cstdlib>
using namespace std;
char str[3500];
int main()
{
    while(gets(str)!=NULL)
    {
        stack <char> num;
        stack <double> operand;
        while(!operand.empty())
            operand.pop();  

        int len=strlen(str);
        for(int i=len-1; i>=0; i--)
        {
            switch(str[i])
            {
                case ' ':
                if(!num.empty())
                {
                    double number = 0;
                    while(!num.empty() && num.top() != '.')
                    {
                        int t = num.top() - '0';
                        num.pop();
                        number = number * 10 + t;
                    }
                    if(!num.empty())
                    {
                        num.pop();//去掉点号
                        double index = 0.1;
                        while(!num.empty())
                        {
                            int t = num.top() - '0';
                            num.pop();
                            number = number + t * index;
                            index /= 10;
                        }
                    }
                    operand.push(number);
                }
                break;
                case '+':
                    double a, b;
                    a = operand.top(), operand.pop();
                    b = operand.top(), operand.pop();
                    a = a + b;
                    operand.push(a);
                    break;
                case '-':
                    a = operand.top(), operand.pop();
                    b = operand.top(), operand.pop();
                    a = a - b;
                    operand.push(a);
                    break;
                case '*':
                    a = operand.top(), operand.pop();
                    b = operand.top(), operand.pop();
                    a = a * b;
                    operand.push(a);
                    break;
                case '/':
                    a = operand.top(), operand.pop();
                    b = operand.top(), operand.pop();
                    a = a / b;
                    operand.push(a);
                    break;
                default:
                    num.push(str[i]);
            }
        }
        double result = operand.top();
        printf("%.2f\n", result);
        memset(str,0,sizeof(str));
     }
    system("pause");
    return 0;
}

//NYOJ AC,hdu re
#include <cstdio>
#include <cstring>
#include <stack>
#include <cctype>
#include <cmath>
#include <cstdlib>
using namespace std;
char str[3500];
int sign(char c)
{
    switch(c)
    {
        case '+': return 1;
        case '-': return 2;
        case '*': return 3;
        case '/': return 4;
		default : return 0;
    }
}
int main()
{
    int i,j,p,q;
    while(gets(str)!=NULL)
    {
        stack <float> s;
        int len=strlen(str);
        for(i=len-1;i>=0;i--)//或者用scanf从标一输入，不用移位
            str[i+1]=str[i];
        str[0]=' ';
        str[len+1]=' ';
        float temp1,temp2,temp;
		if(len==1)
			s.push((float)(str[1]-'0'));
		else
        for(i=len;i>=1;i--)
        {
            if(isdigit(str[i])&&str[i-1]==' '&&str[i+1]==' ')
                s.push((float)(str[i]-'0'));
            else if(str[i]=='.')
            {
                float e=0.1;
                temp1=temp2=0;
                temp1=(float)(str[i-1]-'0');
                for(q=i+1;str[q]!=' ';q++)
                {
                    temp2+=(str[q]-'0')*e;
                    e/=10;
                }
                temp=temp1+temp2;
                s.push(temp);
            }
            else if(str[i]=='+'||str[i]=='-'||str[i]=='*'||str[i]=='/')
            {
                int flag=sign(str[i]);
                switch(flag)
                {
                    case 1:{temp1=s.top();s.pop();temp2=s.top(),s.pop();temp=temp1+temp2;s.push(temp);break;}
                    case 2:{temp1=s.top();s.pop();temp2=s.top(),s.pop();temp=temp1-temp2;s.push(temp);break;}
                    case 3:{temp1=s.top();s.pop();temp2=s.top(),s.pop();temp=temp1*temp2;s.push(temp);break;}
                    case 4:{temp1=s.top();s.pop();temp2=s.top(),s.pop();temp=temp1/temp2;s.push(temp);break;}
					default : continue;
                }
            }
        }
        printf("%.2f\n",s.top());
        while(!s.empty())
            s.pop();
    }
    return 0;
}