等价表达式明明进了中学之后,学到了代数表达式.有一天,他碰到一个很麻烦的选择题.这个题目的题干中首先给出了一个代数表达式,然后列出了若干选项,每个选项也是一个代数表达式,题目的
来源：学生作业帮助网 编辑：六六作业网 时间：2024/12/23 12:33:41
等价表达式明明进了中学之后,学到了代数表达式.有一天,他碰到一个很麻烦的选择题.这个题目的题干中首先给出了一个代数表达式,然后列出了若干选项,每个选项也是一个代数表达式,题目的
等价表达式
明明进了中学之后,学到了代数表达式.有一天,他碰到一个很麻烦的选择题.这个题目的题干中首先给出了一个代数表达式,然后列出了若干选项,每个选项也是一个代数表达式,题目的要求是判断选项中哪些代数表达式是和题干中的表达式等价的.
这个题目手算很麻烦,因为明明对计算机编程很感兴趣,所以他想是不是可以用计算机来解决这个问题.假设你是明明,能完成这个任务吗?
这个选择题中的每个表达式都满足下面的性质：
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……
Input
输入的第一行给出的是题干中的表达式.第二行是一个整数n（2
等价表达式明明进了中学之后,学到了代数表达式.有一天,他碰到一个很麻烦的选择题.这个题目的题干中首先给出了一个代数表达式,然后列出了若干选项,每个选项也是一个代数表达式,题目的
第四题 等价表达式-Equal
[问题分析]
这道题目拿到手后,一般可以想到的方法就是可不可以将所有的表达式全部转化为最简形式,这时,你就想到了一种一般的解决方案.即将所有的表达式全部化为最简,然后再计算,这种方法是一种准确的方法.但要在考场上实现,有一些麻烦,需要一些时间.这种方法的解决过程是：先将阶乘化乘,再展开.计算同时合并同类项,留下一个数组.然后比较每一个表达式的数组与题目数组是否相同,时间效率也并不高.那么怎么办呢?
[模型建立和实现]
我们这里介绍一种利用必要条件的解决方案.
即两个表达式如果等价,那么无论a为何值,两个表达式计算出的值都相等.这时,我们以不同的a值代入各式,可以快速排斥那些不同的表达式,留下的便是等价的了.
我们怎样取值呢?这里推荐几种有效的方法：
1>取随机函数生成的数列.这种方法比较有效,无规律.
2>取伪随机数列.这是一种比较便于人工控制的手段.
3>取实数.由于其他皆为整数,小数部分便成为判断的优越条件.
一般情况下取4~7组值便可通过极大部分情况,实数需要更小.如果取更多组的值,便可以通过几乎所有的情况（将两式连立,只有当取值都为方程的解时才会出现误判,显然这样的几率是极小的）.
补充：这道题可能会有选手在数据类型上选择不当,导致一些情况会出现溢出.
[表达式求值]
经过上面的叙述,难点落在了表达式求值上,在这里我们介绍一下最一般、最简单的方法,栈运算.
用栈实现表达式求值的方法：
首先,我们要给每一个符号一个优先级：
符号 + - * / ^ ( )
栈内级别 2 4 6 0 8
栈外级别 1 3 5 8 0
可以看到,优先级高的符号先算.为了方便起见,我们定义特殊符号#,它级别最低（赋-1）
先将它置栈底,然后依次读入每个字符,如果是数字则入数栈.如果是符号,就与栈顶符号比较优先级.如果相等,则退栈,读下一字符.如果栈外大,则入栈.如果栈内大,则取栈顶元素与数栈最顶2元素运算,结果入数栈.这个符号继续处理（再与栈顶比较）.直到读到最后符号#使栈底#出栈时.数栈顶即为表达式结果.
由此,本题已经变得清晰了,剩下的就是具体将我们的表述变成代码.