NOIP 2005 等价表达式

题目大意：输入多个代数表达式（其中只有'+','-','*','^',0~10000的整数，以及一个未知数a），要求输出与第一行表达式等价的表达式的序号。

显然，要电脑做表达式展开是不太可能的。但是，我们可以指定a的值，代入表达式计算，若结果相等，就认为两个表达式是等价的。当然，这样做是有误判风险的，因此可以对a取不同的值，依次带入。两个表达式相等当且仅当对所有测试的a值它们的结果都相等。

最关键的部分就是表达式求值了，方法是先把表达式转换成后序表达式，然后带入a的值求结果，这两个操作都涉及到栈的使用。具体原理和方法，读者可以参考本人的这篇文章。

此外，输入表达式中没有除号，而直接计算结果可能会超出long的范围，因此可以利用同余的性质，避免高精度。

代码如下：

C语言: 高亮代码由发芽网提供

#include <stdio.h>
#include <stdlib.h>
#include <string.h>

const long MOD = 10007;

int N;
char str[30][100];
long t[30] = {1,3,13,17,5,22,97,31,55,19};    //values of a
int equal[30];
int rank[255];   //the priority of operators

void trans(char *a,char *b)
{
   static char stack[100];
   int top = 0;
   for(;*a;a ++)
   {
       if(*a == 'a')
       {
           *b = *a;
           b ++;
       }
       else if(*a <= '9' && *a >= '0')
       {
           while(*a <= '9' && *a >= '0')
           {
               *b = *a;
               b ++;a ++;
           }
           *b = '@';  //add a separator
           b ++;
           a --;  //notice
       }
       else if(*a == '(')
           stack[++top] = *a;
       else if(*a == ')')
       {
           while(stack[top] != '(')   //pop until meet '('
           {
               *b = stack[top];
               b ++;top --;
           }
           top --;
       }
       else if(top == 0 || rank[(int)*a] > rank[(int)stack[top]])
           stack[++top] = *a;
       else
       {
           while(stack[top] != '(' && top > 0 && rank[(int)stack[top]] >= rank[(int)*a])
           {
               *b = stack[top];
               b ++;top --;
           }
           stack[++top] = *a;
       }
   }
   while(top > 0)
   {
       if(stack[top] != '(')
       {
           *b = stack[top];
           b ++;
       }
       top --;
   }
}

long calc(char *s,long x)
{
   //fprintf(stderr,"%s = ",s);
   static long ns[100];
   int top = 0;
   long a,b,c;
   for(;*s;s ++)
   {
       if(*s == '*')
       {
           a = ns[top--];b = ns[top--];
           c = (a * b) % MOD;
           ns[++top] = c;
       }
       else if(*s == '+')
       {
           a = ns[top--];b = ns[top--];
           c = (a + b) % MOD;
           ns[++top] = c;
       }
       else if(*s == '-')
       {
           a = ns[top--];b = ns[top--];
           c = (b - a + MOD) % MOD;
           ns[++top] = c;
       }
       else if(*s == '^')
       {
           a = ns[top--];b = ns[top--];
           c = power(b,a);
           if(c < 0)    c += MOD;
           ns[++top] = c;
       }
       else if(*s == 'a')
       {
           ns[++top] = x % MOD;
       }
       else
       {
           a = 0;
           while(*s <= '9' && *s >= '0')
           {
               a *= 10;
               a += (int)(*s - '0');
               s ++;
           }
           ns[++top] = a % MOD;
       }
   }
   //fprintf(stderr,"%ld\n",ns[top]);
   return ns[top];
}

inline void remove_space(char *s)
{
   int i,j;
   for(i = j = 0;s[i];i ++)
   {
       if(s[i] == ' ' || s[i] == '\n')    continue;
       s[j ++] = s[i];
   }
   s[j] = 0;
}

inline void init_rank()
{
   rank[(int)'^'] = 10;
   rank[(int)'*'] = rank[(int)'/'] = 8;
   rank[(int)'+'] = rank[(int)'-'] = 5;
}

inline long power(long base,long x)
{
   long res = 1;
   while(x --)
       res = (res * base) % MOD;
   return res;
}

inline void readinput(char *s)
{
   static char tmp[100];
   fgets(tmp,100,stdin);
   remove_space(tmp);
   trans(tmp,s);
}

int main()
{
   freopen("equal.in","r",stdin);
   freopen("equal.out","w",stdout);
   init_rank();
   readinput(str[0]);
   scanf("%d\n",&N);
   int i,j;
   for(i = 1;i <= N;i ++)
   {
       readinput(str[i]);
       //fprintf(stderr,"ori:%s\nrev:%s\n",tmp,str[i]);
       equal[i] = 1;
   }
   long v;
   for(i = 0;i < 10;i ++)
   {
       v = calc(str[0],t[i]);
       for(j = 1;j <= N;j ++)
           if(calc(str[j],t[i]) != v)    equal[j] = 0;
   }
   for(i = 1;i <= N;i ++)
       if(equal[i])    printf("%c",'A' + i - 1);
   printf("\n");
   fclose(stdout);
   return 0;
}