mathematicalexpression.java

矩阵的QR分解算法

	    return operands[0].eval(symbols) - operands[1].eval(symbols);
	  } else {
	    return -operands[0].eval(symbols);
	  }
	case '*': return operands[0].eval(symbols) * operands[1].eval(symbols);
	case '/': return operands[0].eval(symbols) / operands[1].eval(symbols);
	case '>': return (operands[0].eval(symbols) > operands[1].eval(symbols))?1.0:0.0;
	case '<': return (operands[0].eval(symbols) < operands[1].eval(symbols))?1.0:0.0;
	case '=': return (operands[0].eval(symbols) == operands[1].eval(symbols))?1.0:0.0;
	case '&': return (operands[0].eval(symbols)==1.0) && (operands[1].eval(symbols)==1.0)?1.0:0.0;
	case '|': return (operands[0].eval(symbols)==1.0) || (operands[1].eval(symbols)==1.0)?1.0:0.0;
	case '!': return (operands[0].eval(symbols)==1.0)?0.0:1.0;
	case Tokenizer.TT_FUN:
	  switch ((int) nval) {
	    case 0: return Math.abs(operands[0].eval(symbols));
	    case 1: return Math.sqrt(operands[0].eval(symbols));
	    case 2: return Math.log(operands[0].eval(symbols));
	    case 3: return Math.exp(operands[0].eval(symbols));
	    case 4: return Math.sin(operands[0].eval(symbols));
	    case 5: return Math.cos(operands[0].eval(symbols));
	    case 6: return Math.tan(operands[0].eval(symbols));
	    case 7: return Math.rint(operands[0].eval(symbols));
	    case 8: return Math.floor(operands[0].eval(symbols));
	    case 9: return Math.pow(operands[0].eval(symbols),
		operands[1].eval(symbols));
	    case 10:return Math.ceil(operands[0].eval(symbols));
	    default: throw new Exception("Unknow Function");
	  }
	case Tokenizer.TT_IFELSE: return (operands[0].eval(symbols)==1.0)?operands[1].eval(symbols):operands[2].eval(symbols);
	
	default:throw new Exception("Unknow Tree Node Type.");
      }
    }
  }
  
  /**
   * Construct the Expression tree for a given String
   * 
   * @param exp the expression used to build the tree
   * @return the generated node
   * @throws Exception if EOF is not reached
   */
  public static MathematicalExpression.TreeNode parse(String exp) throws Exception {
    MathematicalExpression.Tokenizer tokenizer = new Tokenizer(new StringReader(exp));
    tokenizer.nextToken();
    MathematicalExpression.TreeNode res = parseExp(tokenizer);
    if (tokenizer.ttype != Tokenizer.TT_EOF) {
      throw new Exception("Syntax Error: end of file expected.");
    }
    return res;
  }
  
  /**
   * Parse the exp rule
   * 
   * @param tokenizer the tokenizer from which the token are extracted.
   * @return the tree of the corresponding expression
   * @throws Exception if something goes wrong
   */
  protected static MathematicalExpression.TreeNode parseExp(MathematicalExpression.Tokenizer tokenizer) throws Exception {
    Vector operands = new Vector();
    operands.add(parseTerm(tokenizer));
    switch (tokenizer.ttype) {
      case '+':
	tokenizer.nextToken();
	operands.add(parseExp(tokenizer));
	return new TreeNode('+',operands);
      case '-':
	tokenizer.nextToken();
	operands.add(parseExp(tokenizer));
	return new TreeNode('-',operands);
      default:
	return (MathematicalExpression.TreeNode) operands.get(0);
    }
  }    
  
  /**
   * Parse the term rule
   * 
   * @param tokenizer the tokenizer from which the token are extracted.
   * @return the tree of the corresponding term
   * @throws Exception if something goes wrong
   */    
  protected static MathematicalExpression.TreeNode parseTerm(MathematicalExpression.Tokenizer tokenizer) throws Exception {
    Vector operands = new Vector();
    operands.add(parseAtom(tokenizer));
    switch (tokenizer.ttype) {
      case '*':
	tokenizer.nextToken();
	operands.add(parseTerm(tokenizer));
	return new TreeNode('*',operands);
      case '/':
	tokenizer.nextToken();
	operands.add(parseTerm(tokenizer));
	return new TreeNode('/',operands);
      default:
	return (MathematicalExpression.TreeNode) operands.get(0);
    }
  }    
  
  /**
   * Parse the atom rule
   * 
   * @param tokenizer the tokenizer from which the token are extracted.
   * @return the tree of the corresponding atom
   * @throws Exception if a syntax error occurs
   */    
  protected static MathematicalExpression.TreeNode parseAtom(MathematicalExpression.Tokenizer tokenizer) throws Exception {
    switch (tokenizer.ttype) {
      case Tokenizer.TT_NUMBER:
	MathematicalExpression.TreeNode res = new TreeNode(tokenizer.nval);
	tokenizer.nextToken();
	return res;
      case '(':
	tokenizer.nextToken();
	MathematicalExpression.TreeNode e = parseExp(tokenizer);
	if (tokenizer.ttype != ')') {
	  throw new Exception("Syntax Error: ')' expected.");
	}
	tokenizer.nextToken();
	return e;
      case '-':
	tokenizer.nextToken();
	Vector operands = new Vector(1);
	operands.add(parseAtom(tokenizer));
	return new TreeNode('-',operands);
      case Tokenizer.TT_VAR:
	MathematicalExpression.TreeNode t = new TreeNode(tokenizer.sval);
	tokenizer.nextToken();
	return t;
      case Tokenizer.TT_IFELSE:
	tokenizer.nextToken();
	if (tokenizer.ttype != '(') {
	  throw new Exception("Syntax Error: '(' expected.");
	}
	tokenizer.nextToken();
	Vector par = new Vector(3);
	par.add(parseDisjunction(tokenizer));
	if (tokenizer.ttype != ',') throw new Exception("Syntax Error: ',' expected.");
	tokenizer.nextToken();
	par.add(parseExp(tokenizer));
	if (tokenizer.ttype != ',') throw new Exception("Syntax Error: ',' expected.");
	tokenizer.nextToken();
	par.add(parseExp(tokenizer));
	if (tokenizer.ttype != ')') throw new Exception("Syntax Error: ',' expected.");
	tokenizer.nextToken();
	return new TreeNode(par);            
      case Tokenizer.TT_FUN:
	String fn = tokenizer.sval;
	tokenizer.nextToken();
	if (tokenizer.ttype != '(') throw new Exception("Syntax Error: '(' expected.");
	tokenizer.nextToken();
	Vector params = new Vector(1);
	params.add(parseExp(tokenizer));
	while (tokenizer.ttype == ',') {
	  tokenizer.nextToken();
	  params.add(parseExp(tokenizer));
	}
	if (tokenizer.ttype != ')') throw new Exception("Syntax Error: ')' expected.");
	tokenizer.nextToken();
	return new TreeNode(fn,params);
      default:
	throw new Exception("Syntax Error: Unexpected token");
    }
  }
  
  /**
   * Disjunctive boolean test
   * 
   * @param tokenizer the tokenizer from which the token are extracted.
   * @return the tree of the corresponding Dijunction
   * @throws Exception if something goes wrong
   */    
  protected static MathematicalExpression.TreeNode parseDisjunction(MathematicalExpression.Tokenizer tokenizer) throws Exception {
    Vector params = new Vector(2);
    params.add(parseConjunction(tokenizer));
    if (tokenizer.ttype != '|') {
      return (MathematicalExpression.TreeNode) params.get(0);
    }
    tokenizer.nextToken();
    params.add(parseDisjunction(tokenizer));
    return new TreeNode('|',params);
  }
  
  /**
   * Conjunction boolean test
   * 
   * @param tokenizer the tokenizer from which the token are extracted.
   * @return the tree of the corresponding Conjunction
   * @throws Exception if something goes wrong
   */        
  protected static MathematicalExpression.TreeNode parseConjunction(MathematicalExpression.Tokenizer tokenizer) throws Exception {
    Vector params = new Vector(2);
    params.add(parseNumTest(tokenizer));
    if (tokenizer.ttype != '&') {
      return (MathematicalExpression.TreeNode) params.get(0);
    }
    tokenizer.nextToken();
    params.add(parseConjunction(tokenizer));
    return new TreeNode('&',params);
  }
  
  /**
   * Parse a numeric test
   * 
   * @param tokenizer the tokenizer from which the token are extracted.
   * @return the tree of the corresponding test
   * @throws Exception if brackets don't match or test unknown
   */            
  protected static MathematicalExpression.TreeNode parseNumTest(MathematicalExpression.Tokenizer tokenizer) throws Exception {
    MathematicalExpression.TreeNode n;
    switch (tokenizer.ttype) {
      case '[':
	tokenizer.nextToken();
	n = parseDisjunction(tokenizer);
	if (tokenizer.ttype != ']') {
	  throw new Exception("']' expected");
	}
	tokenizer.nextToken();
	return n;
      case '!':
	tokenizer.nextToken();
	if (tokenizer.ttype != '[') {
	  throw new Exception("'[' expected after '!'");
	}
	tokenizer.nextToken();
	n = parseDisjunction(tokenizer);
	if (tokenizer.ttype != ']') {
	  throw new Exception("']' expected");
	}
	tokenizer.nextToken();
	return new TreeNode(n);                
      default:
	Vector params = new Vector(2);
      params.add(parseExp(tokenizer));
      int op = tokenizer.ttype;
      if (op != '<' && op != '>' && op != '=') {
	throw new Exception("Unknow test " + (char) tokenizer.ttype);
      }
      tokenizer.nextToken();
      params.add(parseExp(tokenizer));
      return new TreeNode(op,params);
    }
  }
  
  /**
   * generates a new parse tree from the given expression and evalutes and
   * returns the result of a mathematical expression, based on the given 
   * values of the symbols.
   * 
   * @param expr	the expression to evaluate
   * @param symbols	the symbol/value mapping
   * @return		the evaluated result
   * @throws Exception	if something goes wrong
   */
  public static double evaluate(String expr, Map symbols) throws Exception {
    return evaluate(parse(expr), symbols);
  }
  
  /**
   * evalutes and returns the result of a mathematical expression, based on 
   * the given expression tree and values of the symbols.
   * 
   * @param parseTree	fully generated expression tree
   * @param symbols	the symbol/value mapping
   * @return		the evaluated result
   * @throws Exception	if something goes wrong
   */
  public static double evaluate(MathematicalExpression.TreeNode parseTree, Map symbols) throws Exception {
    return parseTree.eval(symbols);
  }
}