一开始MLE，然后是TLE
。。。。。我的天，我快崩溃了。

然后我改了一个关键的地方，就是内存管理，我把释放的节点用一个RubLink储存，当需要再申请内存的时候，先检查RubLink是否有资源，有的话，就直接拿。140ms。
足以可见，计算机在分配内存的时候，需要耗费很多时间！！！！！！！

附代码：
#include <stdio.h >
#include <string.h>
#include <stdlib.h>
#define MAXSIZE 400
typedef struct stack{
    char arr[MAXSIZE];
    int  top;
}stack;
typedef struct expreNode{
    char   s[MAXSIZE];
    struct expreNode *next;
    char   r;//c refer to the latest operation in a node
}expreNode;
void push(stack *s,char c)
{
    (*s).arr[(*s).top++]=c;
}
char pop(stack *s)
{
    return (*s).arr[--(*s).top];
}
int empty(stack s)
{
    return s.top==0?1:0;
}
int biger(char c,char p)
{
    if((c=='*'||c=='/')&&(p=='+'||p=='-'))
    return 1;
    return 0;
}
int equal(char c,char p)
{
    if((c=='+'||c=='-')&&(p=='+'||p=='-'))return 1;
    else if( (c=='*'||c=='/')&&(p=='*'||p=='/') )return 1;
    return 0;
}
int main()
{
    stack op,dt;
    char  expre[MAXSIZE],add[5];
    int   i,j,k,l,n;
    char  c,temp,*s;
    expreNode *root;
    expreNode *RubLink,*RubHead;//用来处理垃圾内存
    expreNode *p,*t;
    //printf("%d\n",equal('-','*'));
    scanf("%d",&n);
    RubLink=(expreNode*)malloc(sizeof(expreNode));
    RubLink->next=NULL;
    RubHead=RubLink;
    for(i=0;i<n;i++)//将中缀表达式转换为前缀表达式
    {
        scanf("%s",expre);
        op.top=0,dt.top=0;
        for(j=strlen(expre)-1;j>=0;j--)
        {
            c=expre[j];
            if(c>='a'&&c<='z')
            {push(&dt,c);}//printf("push %c to dt \n",c);}
            else if(c=='+'||c=='-'||c=='*'||c=='/')
            {
                pro:if(empty(op)||op.arr[op.top-1]==')'||
                (biger(c,op.arr[op.top-1])||equal(c,op.arr[op.top-1]) ) )//伪代码
                push(&op,c);
                else
                {
                  temp=pop(&op);
                  push(&dt,temp);
                  goto pro;
                }
            }
            else if(c=='('||c==')')
            {
                if(c==')')push(&op,c);
                else{//左括号
                    while(op.arr[op.top-1]!=')'&&op.top>=0)push(&dt,pop(&op));
                    pop(&op); //丢弃右括号
                    continue;//丢弃左括号，即不对c作任何处理
                }
            }
        }
        while(!empty(op))push(&dt,pop(&op));//至此dt就是前缀表达式
        while(!empty(dt))push(&op,pop(&dt));//将前缀表达式翻转
        root=(expreNode*)malloc(sizeof(expreNode));
        root->next=NULL;
        while(!empty(op))
        {
            c=pop(&op);
            if(c>='a'&&c<='z')
            {
             if(RubHead->next!=NULL)
             {t=RubHead->next;RubHead->next=RubHead->next->next;}
             else t=(expreNode*)malloc(sizeof(expreNode));
             add[0]=c,add[1]='\0';
             strcpy(t->s,add);
             t->r='/';
             t->next=root->next;
             root->next=t; //用链表来模仿栈
            }
            else if(c=='+'||c=='-'||c=='*'||c=='/')
            {
              add[0]=c,add[1]='\0';
              if(biger(c,root->next->r)||biger(c,root->next->next->r)||c=='-'||c=='/')//需要添加括号的情况
              {
                  if(biger(c,root->next->r))
                  {
                   strcpy(expre,"("),strcat(expre,root->next->s),strcat(expre,")");
                   strcpy(root->next->s,expre);
                  }
                  if( biger(c,root->next->next->r)||(c=='-'&&equal(c,root->next->next->r))||
                     (c=='/'&&strlen(root->next->next->s)>1) )
                  {
                    strcpy(expre,"("),strcat(expre,root->next->next->s);
                    strcat(expre,")"),strcpy(root->next->next->s,expre);
                  }
                  strcat(root->next->s,add),strcat(root->next->s,root->next->next->s);
              }
              else{
               strcat(root->next->s,add),strcat(root->next->s,root->next->next->s);
              }
              p=root->next->next;
              root->next->next = p->next;
              root->next->r=c;
              p->next=RubHead->next;
              RubHead->next=p;
            }
        }
        printf("%s\n",root->next->s);
        free(root->next),free(root);
    }
    return 0;
}

• Re:拙劣的代码。估计没几个人看的明白 (106) StepByStepCnmLife 2015-05-10 22:47:47