Consider an expression like E:"123 * x + 456 * y * 12 - 200 / z" which follows the rules:
· may contain operands: +,-,*,/
· may contain variables (like 'x')
· may contain constants (like '123')
· does not contain parenthesis.
Write a set of Java classes to parse and "compile" expressions like E. Once the expression is "compiled"
it should be able to evaluated against a Map which would contain the value for the
variables. For example the expression "x + 2*y" would result to7 when evaluated against [x ->1, y ->3].
By "compiled" we mean that if the expression is to be evaluated against 1m inputs, the work of parsing
the expression into a set of Java classes should only be done once.
You should write a set of unit tests to show that your implementation is correct.
This is an Object Oriented Programing exercise. Focus should be put on good use of OOP principles
(encapsulation, good level of abstraction, low amount of duplicated code, design easy to extend, etc..)
and design patterns if necessary.
We recommend to use Maven, but you may use any other tool providing that you give sufficient
instruction to execute your code.
You may use generic libraries like Apache Common or Google Guava but you may not use scripting
libraries like JEXL, ANTLR or Grammatica.
强烈建议,先翻译完再过来,
http://itindex.net/detail/44416-fel-%E9%87%8F%E7%BA%A7-%E8%A1%A8%E8%BE%BE%E5%BC%8F
http://download.csdn.net/download/howareyoutodayyhz/5547709
有一个思路是把表达式及其子表达式均看作Expression对象，即"123 * x + 456 * y * 12 - 200 / z"是一个Expression，"123 * x" 也是一个Expression, "123" 也是一个Expression。
题中说的"Compile"即可解释为按照计算顺序（先除乘，后减加）建立一个树形结构，将"123 * x + 456 * y * 12 - 200 / z"这个Expression作为根节点，第一层子节点是所有需要"+"的Expression(123 * x， 456 * y * 12 - 200 / z)，第二层是" - "的，以此类推。最后调用根节点的evaluate方法递归的获得执行结果。
/*根据不同的运算符返回不同的结果,例如：对于加法运算符，则返回value1 + value2.*/
public interface IOperator {
public double evaluate(double value1, double value2);
public String getName();
}
public class Expression {
private String expression;
private List<Expression> subExpressions;
private IOperator operator;
public static Map<String, Double> valueMap;
private static final String[] operatorNames = { "+", "-", "*", "/" };
public Expression(String expression) {
this.expression = expression.trim();
}
public double evaluate() throws Exception {
if(isNumber(expression)){
return Character.isDigit(expression.charAt(0))?Double.valueOf(expression):valueMap.get(expression);
}
List<Expression> subExpressions=getSubExpressions();
if(subExpressions.size()==0){
throw new Exception("Invalid expression: "+expression);
}
double result=subExpressions.get(0).evaluate();
for(int i=1;i<subExpressions.size();++i){
result=operator.evaluate(result, subExpressions.get(i).evaluate());
}
return result;
}
@Override
public String toString(){
return expression;
}
public void compile() {
compile(this, 0);
}
private void compile(Expression expression, int operatorIndex) {
if(isNumber(expression.toString())){
return;
}
if (operatorIndex < operatorNames.length) {
expression.setOperator(OperatorFactory.getOperatorByName(operatorNames[operatorIndex])); //OperatorFactory根据不同的运算符字符串返回不同的IOperator对象，此处省略实现.
expression.setSubExpressions(getSubExpressionByOperator(expression.toString(), expression.getOperator()));
for(Expression subExpression:expression.getSubExpressions()){
compile(subExpression, operatorIndex+1);
}
}
}
private List<Expression> getSubExpressionByOperator(String expression, IOperator operator){
String[] subExpressionStrs=expression.split(operator.getName());
List<Expression> subExpressions=new ArrayList<Expression>();
for(String subExpressionStr:subExpressionStrs){
subExpressions.add(new Expression(subExpressionStr));
}
return subExpressions;
}
private boolean isNumber(String str) {
Pattern pattern = Pattern.compile("[0-9]+.?[0-9]*");
Matcher isNum = pattern.matcher(str);
return isNum.matches() || (valueMap!=null && valueMap.containsKey(expression.toString()));
}
/*省略get/set方法*/
}