pku3645 Smeech (表达式计算)

题目:

题目意思是说：一个人发明了一种新的表达式，现给出这种表达式的规则，要求算出这种表达式的值。

表达式的规则如下：

1，单个整数是一个合法表达式，它的值就是该整数。

2，形如(p,e1,e2)的表达式，p是一个实数，且0<=p<=1，这个表达式的值为p*(x+y)+(1-p)*(x-y)。其中x,y分别为该表达式e1,e2的值。

这题有和我们求普通表达式的值其实是类似的。我的方法如下:

1,将读入的表达式串存起来。然后遍历。

2,如果遇到空格或左括号，则继续往后遍历。

3,如果遇到数,则将该数压入栈。

4,如果遇到右括号，则从栈中依次弹出3个数，它们分别为y,x,p,按p*(x+y)+(1-p)*(x-y)计算出新的值t，将t压入栈。

5,如果遇到串结束符。则输出栈中的数，即为结果。

my code:

 

#include<iostream>
using namespace std;
int main()
{
    double stack[20],ans,t,a1,a2,a3;
    int top,le,i,j,k;
    char exp[500],temp[20];
    while(gets(exp))
    {
        if(strcmp(exp,"()")==0) break;
        le=strlen(exp);top=0;
        if(isdigit(exp[0]))
        {
            ans=atof(exp);
            printf("%.2lf\n",ans);
            continue;
        }
        for(i=0;i<le;)
        {
            if(exp[i]==' ') i++;
            else if(exp[i]=='(')
            {
                for(j=i+1,k=0;exp[j]!=' '&&j<le;j++,k++)
                    temp[k]=exp[j];
                temp[k]='\0';
                t=atof(temp);
                stack[top++]=t;
                i=j;
            }
            else if(isdigit(exp[i])||exp[i]=='-')
            {
                for(j=i,k=0;!(exp[j]==' '||exp[j]==')')&&j<le;j++,k++)
                    temp[k]=exp[j];
                temp[k]='\0';
                t=atof(temp);
                stack[top++]=t;
                i=j;
            }
            else if(exp[i]==')')
            {
                a1=stack[--top];
                a2=stack[--top];
                a3=stack[--top];
                t=(a2+a1)*a3+(a2-a1)*(1-a3);
                stack[top++]=t;
                i++;
            }
        }
        printf("%.2lf\n",stack[0]);
    }
    return 0;
}

题中表达式的定义，是一种递归的形式定义，本来想着应该有一种递归的算法解决。但是没想出来，后在网上搜出这题的标程，是一段短小精悍的递归，看了半天没怎么看懂。。有空再看吧。感觉相当经典，但它的空间要比我的程序花的多。。

the code:

#include <cstdio>
#include <string>
using namespace std;

bool done;

double doit() {
  char ch;
  do {ch = getchar();} while (isspace(ch));
  if (ch == ')') exit(0);
  if (ch == '(') {
    double p;
    scanf("%lf", &p);
    return doit() + (p-(1-p)) * doit();
  } else {
    string s;
    while (!isspace(ch)) {s += ch; ch = getchar();}
    return atoi(s.c_str());
  }
}

main() {
  for(;;) {printf("%.2lf\n", doit()); fflush(stdout);}
}