Problem 3122 --等价表达式

3122: 等价表达式

"
Time Limit $1$ 秒/Second(s) Memory Limit $512$ 兆字节/Megabyte(s)
提交总数 $6$ 正确数量 $2$
裁判形式 标准裁判/Standard Judge 我的状态 尚未尝试
难度 分类标签

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

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

这个选择题中的每个表达式都满足下面的性质:

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个字符,而且保证选项中总有表达式和题干中的表达式是等价的。


数据规模:

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

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

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


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


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

推荐代码 查看3122 所有题解 上传题解视频得图灵币

本题记录 用 户(点击查看用户) 运行号(点击购买题解) 时 间
算法最快[$447 $ms] 计爱玲 559888 2019-12-29 11:37:54
内存最少[$0 $KB] 计爱玲 559888 2019-12-29 11:37:54
第一AC 计爱玲 559888 2019-12-29 11:37:54
第一挑战 计爱玲 559888 2019-12-29 11:37:54

赛题来源/所属竞赛 NOIP全国联赛提高组 2005年NOIP全国联赛提高组 N/A

竞赛编号 竞赛名称 竞赛时间 访问比赛