NOIP2005 等价表达式

#include<stdio.h>
#include<stdlib.h>
#include<string.h>
#define STACK_SIZE 50
#define CHECK_TIMES 10
typedef int* Ptr;
typedef struct CharStack{
    Ptr top;
    Ptr base;
}CharStack;
typedef CharStack* SPtr;
SPtr stack;
SPtr InitStack(){
    SPtr s=(SPtr)malloc(sizeof(CharStack));
    s->base=(Ptr)malloc(sizeof(long long)*STACK_SIZE);
    s->top=s->base;
    return s;
}
void FreeStack(SPtr s){
    if(!s)return;
    free(s->base);
    free(s);
}
int isEmpty(SPtr s){
    return (s->base==s->top);
}
void Push(SPtr s,long long e){
    if(s->top-s->base>=STACK_SIZE)return;
    *(s->top)=e;
    (s->top)++;
}
int Pop(SPtr s){
    int e;
    e=(int)*(s->top-1);
    (s->top)--;
    return e;
}
long long Pop_(SPtr s){
    long long e;
    e=*(s->top-1);
    (s->top)--;
    return e;
}
int precedence(char op1,char op2){
    if(op1=='(')return -1;
    switch(op1){
        case '+':
        case '-':op1=0;break;
        case '*':
        case '/':op1=1;break;
        case '^':op1=2;break;
        case '(':op1=3;break;
    }
    switch(op2){
        case '+':
        case '-':op2=0;break;
        case '*':
        case '/':op2=1;break;
        case '^':op2=2;break;
        case '(':op2=3;break;
    }
    return op1-op2;
}
int isOp(char c){
    return (c=='+'||c=='-'||c=='*'||c=='/'||c=='^')?1:0;
}
void toPostFix(char *InFix,char *PostFix){
    int i,n=strlen(InFix);
    char c,e;
    for(i=0;i<n;i++){
        c=*(InFix+i);
        if(c==' ')continue;
        else if(c=='('){
            Push(stack,c);
        }else if(c==')'){
            while(stack->top>stack->base && (e=Pop(stack))!='(')*(PostFix++)=e;
        }else if(!isOp(c)){
            *(PostFix++)=c;
        }
        else if(isEmpty(stack))Push(stack,c);
        else {
            while(stack->top > stack->base && precedence(*(stack->top-1),c)>=0)*(PostFix++)=Pop(stack);
            Push(stack,c);
        }
    }
    while(stack->top>stack->base)*(PostFix++)=Pop(stack);
    *PostFix='\0';
}
int sA[50];
long long power(long long a,int x){
    int i;
    long long r=1;
    for(i=0;i<x;i++)r*=a;
    return r;
}
long long compute(char *PostFix,int a){
    int n=strlen(PostFix),num,offset=0;
    long long val,op1,op2;
    Ptr j;
    SPtr nstack=InitStack();
    while(offset<n){
        if(*(PostFix+offset)=='a'){Push(nstack,a);}
        else if(*(PostFix+offset)>='A' && *(PostFix+offset)<='Z'){num=sA[*(PostFix+offset)-'A'];Push(nstack,num);}
        else if(isOp(*(PostFix+offset))){
            op1=Pop_(nstack);
            op2=Pop_(nstack);
            switch(*(PostFix+offset)){
                case '+':val=(op1+op2);break;
                case '-':val=(op2-op1);break;
                case '*':val=(op1*op2);break;
                case '/':val=(op2/op1);break;
                case '^':val=power(op2,op1);break;
            }
            Push(nstack,val);
        }
        else {Push(nstack,num);}
        offset++;
    }
    val=*(nstack->base);
    FreeStack(nstack);
    return val;
}
long long result[28][CHECK_TIMES];
int result_no=0;
void input(){
    char In[100];
    char al='A';
    char nIn[100];
    int i,j,n=0,c=0,start,end;
    char Post[100];
    gets(In);
    for(i=0;i<strlen(In);i++){
        if(In[i]>='0' && In[i]<='9'){
            if(n==0)start=i+1;
            n=n*10+In[i]-'0';
            if(i==strlen(In)-1){
                end=i+1;
                In[start-1]=al+c;
                for(j=start;j<end;j++)In[j]='~';
                sA[c++]=n;
                n=0;
            }
        }else if(n!=0){
            end=i;
            In[start-1]=al+c;
            for(j=start;j<end;j++)In[j]='~';
            sA[c++]=n;
            n=0;
        }
    }
    c=0;
    for(i=0;i<strlen(In);i++){
        if(In[i]!=' '&& In[i]!='~')nIn[c++]=In[i];
    }
    nIn[c]='\0';
    stack=InitStack();
    toPostFix(nIn,Post);
    for(i=0;i<CHECK_TIMES;i++){
            result[result_no][i]=compute(Post,rand()%40);
    }
    result_no++;
}
int main(){
    int M,i,choice_c=0,j,flag;
    char choices[27];
    input();
    scanf("%d",&M);
    getchar();
    for(i=0;i<M;i++)input();
    for(i=1;i<=M;i++){
        flag=1;
        for(j=0;j<CHECK_TIMES;j++)if(result[i][j]!=result[0][j]){
            flag=0;
            break;
        }
        if(flag)choices[choice_c++]='A'+i-1;
    }
    for(i=0;i<choice_c;i++)printf("%c",choices[i]);
    FreeStack(stack);
    return 0;
}

(1000+24)^3*8*a*6^6*9*(3*a^2 + 4*9^2)*(a^2+12*9^2)
26
(2^10 * 4-(2048*2)-9+6^1)^3
9999 + 9999+9999+9999-(9999 + 9999+9999+9999)+6+ 5
(6 +1+5)*(6^2 +1^2+5^2-(1-2*6*1-1)+2*5*(6+1))
(6 +1)-6-3-8-( 1-(3 +8))-(9999   -9990)- 3
1-2*6^1+3*6^2-4*6^3+5*6^4-6^5*(6-7*6+8*6^2 -9*6^3)
(8+3)^4-(8*3^3*8+2^3*3*8^3)
(6^8+1)^2 -2*(1 + 6^8)
(6 +3*(1+5))*6^2+((1+5)*2*(1+5)+(1+5)^2)*6+(1+5)^3
(a^2 - 2*a*6+6^1*6^1)^5
((a+6)^2 - 4*a*6)^5 +(a -a)^10^7
(a^3-3*a*6*(a-6) - 6^3)^4^8 *(a^2-2*a*6+6^2)^2
9999+(6-9)*6
6^2^2-1
a^10^10 +2-1
6^2^2^2-1
a -a + 1 +(a -a)^10^9^8^7^6^5^4^3^2
(1-6)^2+2*6^2-4*6^3+5*6^4-6*6^5+7*6^6-8*6^7+9*6^8
8*8*8*8+3*3*3*3+4*3*8*(1-1-(3*3+8*8))+6*3*8*3*8
(8 - 3)*(3 -8)*(8 -3)*(8 -3)
2^5^6*(7*a*6^6*9*(3*a^2 + 4*9^2)*(a^2 + 12*9^2))
2^5^6*(4*a*6^6*9*(3*a^2 + 8*9^2)*(a^2 + 12*9^2))
2^5^6*(24*a^5*6^6*9+320*a^3*6^6*9^3+384*a*6^6*9^5)
2^5^6*(24*a^5*6^6*9+320*a^2*6^6*9^3+384*a*6^6*9^5)
2^5^6*2*a*6^3*(a^2+12*9^2)*4*6^3*9*(3*a^2 + 4*9^2)
2^5^6*4*a*6^3*(a^2+12*9^2)*2*6^3*9*(3*a^2 + 4*9^2)
2^5^6*2*a*6^3*(a^2+21*9^2)*4*6^3*9*(3*a^2 + 4*9^2)

VXY