Tuesday, November 6, 2012

NOIP 2005 等价表达式

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

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

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

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

代码如下: