题目描述

明明进了中学之后，学到了代数表达式。有一天，他碰到一个很麻烦的选择题。这个题目的题干中首先给出了一个代数表达式，然后列出了若干选项，每个选项也是一个代数表达式，题目的要求是判断选项中哪些代数表达式是和题干中的表达式等价的。
这个题目手算很麻烦，因为明明对计算机编程很感兴趣，所以他想是不是可以用计算机来解决这个问题。假设你是明明，能完成这个任务吗？
这个选择题中的每个表达式都满足下面的性质：
1．表达式只可能包含一个变量‘a’。
2．表达式中出现的数都是正整数，而且都小于10000。
3．表达式中可以包括四种运算‘+’（加），‘-’（减），‘*’（乘），‘^’（乘幂），以及小括号‘(’，‘)’。小括号的优先级最高，其次是‘^’，然后是‘*’，最后是‘+’和‘-’。‘+’和‘-’的优先级是相同的。相同优先级的运算从左到右进行。（注意：运算符‘+’，‘-’，‘*’，‘^’以及小括号‘(’，‘)’都是英文字符）
4．幂指数只可能是1到10之间的正整数（包括1和10）。
5．表达式内部，头部或者尾部都可能有一些多余的空格。
下面是一些合理的表达式的例子：

输入描述:

第一行给出的是题干中的表达式。
第二行是一个整数，表示选项的个数。
后面n行，每行包括一个选项中的表达式。这n个选项的标号分别是A，B，C，D……输入中的表达式的长度都不超过50个字符，而且保证选项中总有表达式和题干中的表达式是等价的。

输出描述:

包括一行，这一行包括一系列选项的标号，表示哪些选项是和题干中的表达式等价的。选项的标号按照字母顺序排列，而且之间没有空格。

示例1

输入





输出
AC

备注

对于30%的数据，表达式中只可能出现两种运算符‘+’和‘-’；
对于其它的数据，四种运算符‘+’，‘-’，‘*’，‘^’在表达式中都可能出现。
对于全部的数据，表达式中都可能出现小括号‘(’和‘)’。

解答

1.读入数字时，压入数字栈；
2.读入符号时：
1.如果是运算符，当前栈顶的运算符优先级大于等于新运算符，则将栈顶运算符弹出，并将当前数字栈顶的两个数进行相应运算，弹出旧数，压入新结果。不停循环，直到栈里面没有符号或符号优先级低于当前新运算符。
 2.如果是(，直接压入栈。
 3.如果是），则依次将栈里面的符号弹出，并计算。直到遇到一个（。
给a赋一个特殊值，最好是比较大的质数，避免冲突的话可以多代几个。当然代数的时候有可能longlong存不下，所以需要mod一个比较大的质数。

注意： 
1.模质数的时候，做减法的时候有可能是负数，所以需要加上这个质数再mod一下。 
2.数据中有可能出现括号不匹配的情况，需要特殊判断。
#include<iostream>
#include<cstdio>
#include<cstring>
#define N 2147483647
#define MOD 32767
typedef long long LL;
using namespace std;
LL top,t=0,flag;
char stack_sign[100006],s[10006];
LL stack_num[100006];
int n;
LL ans1,ans2,m1,m2,ans3,m3;
LL pow(LL x,LL y)
{
    LL sum=1;
    for (int i=1;i<=y;i++)
        sum*=x;
    return sum;
}
//int get()
//{
//  int x=0,f=1;
//  char c;
//  c=getchar();
//  while (c<'0'||c>'9') {if (c=='-') f=-1;c=getchar();}
//  while (c>='0'&&c<='9') {x=x*10+c-'0';c=getchar();}
//  return x*f;
//} 
int level(char c)  //赋予每个符号一个优先级 
{
    if (c=='+'||c=='-') return 1;
    if (c=='*') return 2;
    if (c=='^') return 3;
    if (c=='(') return 0;
}
LL ksm(int a,int b,int c)
{
    int ans=1;
    a=a%c;
    while (b>0)
    {
        if (b&1) ans=(ans*a)%c;
        b=b/2;
        a=(a*a)%c; 
    }
    return ans%c;
}
int clac(int x,int y,char cc)
{
    int ans;
    if (cc=='+') ans=(x+y)%MOD;
    if (cc=='-') ans=(y-x+MOD)%MOD;
    if (cc=='*') ans=(x%MOD*y%MOD)%MOD;
    if (cc=='^') ans=ksm(y,x,MOD);
    return ans%MOD;
}
LL love()
{
    char c;
    int tmp;
    t=0;
    top=0;
    memset(stack_num,0,sizeof(stack_num));
    memset(stack_sign,'\0',sizeof(stack_sign));
    c=getchar();
    while(c=='\n'||c=='\r') c=getchar();   
    while (c!='\n'&&c!='\r')
    {
        if (c==' ') {c=getchar();continue;}
        if (c>='0'&&c<='9')
        {
            top++;
            stack_num[top]=c-'0';
            c=getchar();
            while ((c>='0'&&c<='9')||c==' ')
            {
                if (c==' ') {c=getchar();continue;}
                else 
                {
                    stack_num[top]=(stack_num[top]*10+c-'0')%MOD;
                    c=getchar();
                }
            }
            continue;
        }
        if (c=='a') {stack_num[++top]=13;c=getchar();continue;}  //特殊处理a，赋一个特殊值 
        if (c=='+'||c=='-'||c=='*'||c=='^') 
        {
            while (level(c)<=level(stack_sign[t])) 
            {
                tmp=clac(stack_num[top],stack_num[top-1],stack_sign[t]);
                stack_num[top]=0;
                top--;
                stack_num[top]=tmp;
                stack_sign[t]='\0';
                t--;
            }
            stack_sign[++t]=c;
            c=getchar();
            continue;
        }
        if (c=='(') {stack_sign[++t]=c;c=getchar();continue;}
        if (c==')')
        {
            while (stack_sign[t]!='('&&t>0)
            {
                tmp=clac(stack_num[top],stack_num[top-1],stack_sign[t]);
                stack_num[top]=0;
                top--;
                stack_num[top]=tmp;
                stack_sign[t]='\0';
                t--;
            }
            stack_sign[t]='\0';
            t--;
            c=getchar();
            continue;
        }
    }
    int tt=0;
    for (int i=1;i<=t;i++)
        if (stack_sign[i]!='('&&stack_sign[i]!=')')
            s[++tt]=stack_sign[i];
//  if (top!=0)
//  for (int i=1;i<=tt;i++)
//  {
//      tmp=clac(stack_num[i+1],stack_num[i],s[i]);
//      stack_num[i]=0;
//      stack_num[i+1]=tmp;
//      stack_sign[i]='\0';
//  }
    while (top!=0&&tt!=0)   //最后将栈里剩余元素处理 
    {
        tmp=clac(stack_num[top],stack_num[top-1],s[tt]);
        stack_num[top]=0;
        top--;
        stack_num[top]=tmp;
        s[tt]='\0';
        tt--;
    }
    return stack_num[1];        
}

int main()
{
    LL sum,ans;
    sum=love();
    scanf("%d",&n);
    for (int i=1;i<=n;i++)
    {
        //getchar();
        ans=love();
        if (ans==sum) printf("%c",'A'+i-1);
    }
}