poj 1472(递归模拟)

题意：就是让你求出时间复杂度。

分析：由于指数最多为10次方，所以可以想到用一个数组保存各个指数的系数，具体看代码实现吧！

代码实现：

#include<cstdio>

#include<cstring>

#include<iostream>

#include<algorithm>

using namespace std;

char str[][];

char key[];

int num;

struct node{

    int sum[];

    void init()

    {

        memset(sum,,sizeof(sum));

    }

};

void init()//把字符串提取出来

{

    int i,t=,num=;

    scanf("%s",key);

    while(t)

    {

        scanf("%s",key);

        strcpy(str[num++],key);

        if(key[]=='E')

            t--;

        else if(key[]=='L')

            t++;

    }

}

struct node xiangcheng(struct node a,struct node b)//相乘

{

    int i,j;

    struct node res;

    res.init();

    for(i=;i<=;i++)

     for(j=;j<=;j++)

      res.sum[i+j]=res.sum[i+j]+a.sum[i]*b.sum[j];

    return res;

}

struct node add(struct node a,struct node b)//相加

{

    int i;

    for(i=;i<=;i++)

     a.sum[i]+=b.sum[i];

    return a;

}

struct node dfs()

{

    int i=;

    struct node a;

    a.init();

    while()//碰到END才结束

    {

        i=;

        if(str[num][]=='L')

        {

            num=num+;

            struct node b;

            b.init();

            if(str[num][]=='n')

              b.sum[]++;

            else

            {

              int k=;

              i=;

              while(str[num][i]!='\0')

              {

                k=k*+str[num][i]-'';

                i++;

              }

              b.sum[]=b.sum[]+k;

            }

            num=num+;

            b=xiangcheng(b,dfs());

            a=add(a,b);

        }

        else if(str[num][]=='O')

        {

            num=num+;

            if(str[num][]=='n')

             a.sum[]++;

            else

            {

              int k=;

              i=;

              while(str[num][i]!='\0')

              {

                k=k*+str[num][i]-'';

                i++;

              }

              a.sum[]=a.sum[]+k;

            }

        }

        else if(str[num][]=='E')

           return a;

        num++;

    }

}

int main()

{

    int T;

    int i,j,flag;

    struct node a;

    scanf("%d",&T);

    getchar();

    for(j=;j<=T;j++)

    {

        num=;

        init();

        a=dfs();

        printf("Program #%d\nRuntime = ",j);

        i=;flag=;

        while(a.sum[i]==) i--;

        for(;i>;i--)

        {

             if(a.sum[i]==)

              continue;

             if(flag==)

             {

               if(a.sum[i]>)

                 printf("%d*",a.sum[i]);

               printf("n^%d",i);

               flag++;

             }

             else

             {

               printf("+");

               if(a.sum[i]>)

                 printf("%d*",a.sum[i]);

               printf("n^%d",i);

             }

        }

        if(a.sum[])

        {

            if(flag)

            printf("+");

            if(a.sum[]>)

             printf("%d*",a.sum[]);

            printf("n");

            flag++;

        }

        if(a.sum[])

        {

          if(flag)

           printf("+");

          printf("%d",a.sum[]);

          flag++;

        }

        if(flag==)

         printf("");

        printf("\n\n");

    }

    return ;

}