[NOIP2005]等价表达式

成绩 0 开启时间 2013年01月15日 星期二 11:45
折扣 0.8 折扣时间 2013年01月15日 星期二 11:45
允许迟交 关闭时间 2013年01月15日 星期二 11:45
输入文件 equal.in 输出文件 equal.out

【问题描述】

     明明进了中学之后,学到了代数表达式。有一天,他碰到一个很麻烦的选择题。这个题目的题干中首先给出了一个代数表达式,然后列出了若干选项,每个选项也是一个代数表达式,题目的要求是判断选项中哪些代数表达式是和题干中的表达式等价的。

    这个题目手算很麻烦,因为明明对计算机编程很感兴趣,所以他想是不是可以用计算机来解决这个问题。假设你是明明,能完成这个任务吗?

    这个选择题中的每个表达式都满足下面的性质:
    1. 表达式只可能包含一个变量‘a’。
    2. 表达式中出现的数都是正整数,而且都小于10000。
    3. 表达式中可以包括四种运算‘+’(加),‘-’(减),‘*’(乘),‘^’(乘幂),以及小括号‘(’,‘)’。小括号的优先级最高,其次是‘^’,然 后是‘*’,最后是‘+’和‘-’。‘+’和‘-’的优先级是相同的。相同优先级的运算从左到右进行。(注意:运算符‘+’,‘-’,‘*’,‘^’以及 小括号‘(’,‘)’都是英文字符)
    4. 幂指数只可能是1到10之间的正整数(包括1和10)。
    5. 表达式内部,头部或者尾部都可能有一些多余的空格。
    下面是一些合理的表达式的例子:
((a^1) ^ 2)^3,a*a+a-a,((a+a)),9999+(a-a)*a,1 + (a -1)^3,1^10^9……

【输入文件】

    输入文件 的第一行给出的是题干中的表达式。第二行是一个整数 n ( 2 <= n <= 26 ),表示选项的个数。后面 n 行,每行包括一个选项中的表达式。这 n 个选项的标号分别是 A , B , C , D ……

    输入中的表达式的长度都不超过 50 个字符,而且保证选项中总有表达式和题干中的表达式是等价的。

【输出文件】

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

【输入样例】

( a + 1) ^2
3
(a-1)^2+4*a
a + 1+ a
a^2 + 2 * a * 1 + 1^2 + 10 -10 +a -a

【输出样例】

AC

【数据规模】

对于30%的数据,表达式中只可能出现两种运算符‘+’和‘-’;

对于其它的数据,四种运算符‘+’,‘-’,‘*’,‘^’在表达式中都可能出现。

对于全部的数据,表达式中都可能出现小括号‘(’和‘)’。