2013
11-10

Lazy Math Instructor

A math instructor is too lazy to grade a question in the exam papers in which students are supposed to produce a complicated formula for the question asked. Students may write correct answers in different forms which makes grading very hard. So, the instructor needs help from computer programmers and you can help.

You are to write a program to read different formulas and determine whether or not they are arithmetically equivalent.

The first line of the input contains an integer N (1 <= N <= 20) that is the number of test cases. Following the first line, there are two lines for each test case. A test case consists of two arithmetic expressions, each on a separate line with at most 80 characters. There is no blank line in the input. An expression contains one or more of the following:
• Single letter variables (case insensitive).
• Single digit numbers.
• Matched left and right parentheses.
• Binary operators +, – and * which are used for addition, subtraction and multiplication respectively.
• Arbitrary number of blank or tab characters between above tokens.

Note: Expressions are syntactically correct and evaluated from left to right with equal precedence (priority) for all operators. The coefficients and exponents of the variables are guaranteed to fit in 16-bit integers.

Your program must produce one line for each test case. If input expressions for each test data are arithmetically equivalent, “YES”, otherwise “NO” must be printed as the output of the program. Output should be all in upper-case characters.

3
(a+b-c)*2
(a+a)+(b*2)-(3*c)+c
a*2-(a+c)+((a+c+e)*2)
3*a+c+(2*e)
(a-b)*(a-b)
(a*a)-(2*a*b)-(b*b)


YES
YES
NO


//* @author:
import java.util.Scanner;
import javax.script.ScriptEngine;
import javax.script.ScriptEngineManager;
import javax.script.ScriptException;

public class Main{

ScriptEngineManager factory = new ScriptEngineManager();
ScriptEngine engine = factory.getEngineByName("JavaScript");
Scanner cin=new Scanner(System.in);

int[] num=new int[60];
void init()
{
for(int i=1;i< 59;i++)
num[i]=i+9997;
}
void solve() throws ScriptException
{
int numCase=cin.nextInt();
String s1,s2;
s1=cin.nextLine();
for(int k=1;k<=numCase;k++)
{
s1=cin.nextLine();
s2=cin.nextLine();
for(int i=0;i< 52;i++)
{
s1=s1.replace(String.valueOf((char)(i+'a')), String.valueOf(num[i+1]));
s2=s2.replace(String.valueOf((char)(i+'a')), String.valueOf(num[i+1]));

}
Object o1= engine.eval(s1);
Object o2= engine.eval(s2);
if(o1.toString().endsWith(o2.toString()))
System.out.println("YES");
else
System.out.println("NO");
}
}
public static void main(String[] args) throws ScriptException {
Main jason=new Main();
jason.init();
jason.solve();
}
}

1. 5.1处，反了；“上一个操作符的优先级比操作符ch的优先级大，或栈是空的就入栈。”如代码所述，应为“上一个操作符的优先级比操作符ch的优先级小，或栈是空的就入栈。”

2. 我还有个问题想请教一下，就是感觉对于新手来说，递归理解起来有些困难，不知有没有什么好的方法或者什么好的建议？

3. 第23行：
hash = -1是否应该改成hash[s ] = -1

因为是要把从字符串s的start位到当前位在hash中重置

修改提交后能accept，但是不修改居然也能accept

4. 给你一组数据吧：29 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 1000。此时的数据量还是很小的，耗时却不短。这种方法确实可以，当然或许还有其他的优化方案，但是优化只能针对某些数据，不太可能在所有情况下都能在可接受的时间内求解出答案。