mathematicalexpression.java

矩阵的QR分解算法

/*
 *    This program is free software; you can redistribute it and/or modify
 *    it under the terms of the GNU General Public License as published by
 *    the Free Software Foundation; either version 2 of the License, or
 *    (at your option) any later version.
 *
 *    This program is distributed in the hope that it will be useful,
 *    but WITHOUT ANY WARRANTY; without even the implied warranty of
 *    MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
 *    GNU General Public License for more details.
 *
 *    You should have received a copy of the GNU General Public License
 *    along with this program; if not, write to the Free Software
 *    Foundation, Inc., 675 Mass Ave, Cambridge, MA 02139, USA.
 */

/*
 *    MathematicalExpression.java
 *    Copyright (C) 2004 Prados Julien
 *    Copyright (C) 2002 University of Waikato, Hamilton, New Zealand
 */

package weka.core;

import java.io.IOException;
import java.io.Reader;
import java.io.Serializable;
import java.io.StreamTokenizer;
import java.io.StringReader;
import java.util.Map;
import java.util.Vector;

/** 
 * Class to build (and evaluate) the tree of the grammar:<br/>
 * 
 * <pre>
 * Exp  -&gt; Term '+' Exp   
 *         | Term '-' Exp 
 *         | Term         
 * Term -&gt; Atom '*' Term  
 *         | Atom '/' Term 
 *         | Atom 
 * Atom -&gt; &lt;number&gt; 
 *         | '('Exp')' 
 *         | function '(' Params ')' 
 *         | '-' Atom | VARIABLE 
 *         | Disjunction 
 * Params -&gt; E 
 *           | E,Params 
 * Disjunction -&gt; Conjunction 
 *                | Conjunction '|' Disjunction 
 * Conjunction -&gt; NumTest 
 *                | NumTest '&amp;' Conjunction 
 * NumTest -&gt; Exp '&lt;' Exp | Exp '&gt;' Exp | Exp '=' Exp | '[' Disjunction ']' | '!' '[' Disjunction ']'
 * </pre>
 *
 * Code example 1:
 * <pre>
 * String expr = "pow(BASE,EXPONENT)*MULT";
 * HashMap symbols = new HashMap();
 * symbols.put("BASE", new Double(2));
 * symbols.put("EXPONENT", new Double(9));
 * symbols.put("MULT", new Double(0.1));
 * double result = MathematicalExpression.evaluate(expr, symbols);
 * System.out.println(expr + " and " + symbols + " = " + result);
 * </pre>
 * 
 * Code Example 2 (utilizing a parse tree several times):
 * <pre>
 * String expr = "pow(BASE,EXPONENT)";
 * MathematicalExpression.TreeNode tree = MathematicalExpression.parse(expr);
 * for (int i = -10; i <= 10; i++) {
 *   HashMap symbols = new HashMap();
 *   symbols.put("BASE", new Double(2));
 *   symbols.put("EXPONENT", new Double(i));
 *   double result = MathematicalExpression.evaluate(tree, symbols);
 *   System.out.println(expr + " and " + symbols + " = " + result);
 * }
 * </pre>
 *
 * @author Eibe Frank ([e-mail]) 
 * @author Prados Julien ([e-mail]) 
 * @version $Revision: 1.3 $
 */
public class MathematicalExpression {
  
  /**
   * A tokenizer for MathematicalExpression
   *
   * @author Eibe Frank ([e-mail]) 
   * @author Prados Julien ([e-mail]) 
   * @version $Revision: 1.3 $
   */
  static public class Tokenizer 
    extends StreamTokenizer {
    
    /** token for a variable */
    final static int  TT_VAR = -5;
    
    /** token for a function */
    final static int  TT_FUN = -6;
    
    /** token for if-else */
    final static int  TT_IFELSE = -7;
    
    /**
     * Constructor
     * 
     * @param r		the reader to use
     */
    public Tokenizer(Reader r) {
      super(r);
      resetSyntax();
      parseNumbers();
      whitespaceChars(' ',' ');
      wordChars('a','z');
      wordChars('A','Z');
      ordinaryChar('-');
    }
    
    /**
     * returns the next token
     * 
     * @return			the next token
     * @throws IOException	if something goes wrong
     */
    public int nextToken() throws IOException {
      super.nextToken();
      if (ttype == TT_WORD) {
	if (sval.equals("ifelse")) {
	  ttype = TT_IFELSE;
	} else if (Character.isUpperCase(sval.charAt(0))) {
	  ttype = TT_VAR;
	} else {
	  ttype = TT_FUN;
	}
      }
      return ttype;
    }
  }
  
  /**
   * Tree Node of MathematicalExpression
   *
   * @author Eibe Frank ([e-mail]) 
   * @author Prados Julien ([e-mail]) 
   * @version $Revision: 1.3 $
   */
  static public class TreeNode 
    implements Serializable {
    
    /** for serialization */
    static final long serialVersionUID = -654720966350007711L;
    
    /** The known functions */
    static public String[] funs = {"abs", "sqrt", "log", "exp","sin","cos","tan","rint","floor","pow", "ceil"};
    
    /** The arity of the known functions */
    static public int[] arity   = {    1,      1,     1,     1,    1,    1,    1,     1,      1,    2,      1};
    
    /** Node type */
    int type;
    
    /** Constant value */
    double nval;
    
    /** Var name */
    String sval = null;
    
    /** table of operands */
    MathematicalExpression.TreeNode operands[] = null;
    
    /**
     * Construct a constant node
     * 
     * @param v the value of the constant
     */
    public TreeNode(double v) {
      type = Tokenizer.TT_NUMBER;
      nval = v;
    }
    
    /**
     * Construct a constant node
     * 
     * @param n the value of the constant
     */
    public TreeNode(MathematicalExpression.TreeNode n) {
      type = '!';
      operands = new MathematicalExpression.TreeNode[1];
      operands[0] = n;
    }
    
    /**
     * Construct a variable node
     * 
     * @param v the name of the variable
     */
    public TreeNode(String v) {
      type = Tokenizer.TT_VAR;
      sval = v;
    }
    
    /**
     * Construct an ifelse node
     * 
     * @param p parameters of the ifelse
     */
    public TreeNode(Vector p) {
      type = Tokenizer.TT_IFELSE;
      operands = new MathematicalExpression.TreeNode[p.size()];
      for(int i=0;i<operands.length;i++) {
	operands[i] = (MathematicalExpression.TreeNode) p.elementAt(i);
      }
    }
    
    /**
     * Construct a function node
     * 
     * @param f the name of the function
     * @param ops the operands of the function
     * @throws Exception if function is unknown or wrong arity
     */        
    public TreeNode(String f,Vector ops) throws Exception {
      int i = 0;
      while(i < funs.length && !funs[i].equals(f))
	i++;
      if (i >= funs.length) {
	throw new Exception("Unknow function " + f);
      }
      if (arity[i] != ops.size()) {
	throw new Exception("Wrong Number of argument in " + f);
      }
      type = Tokenizer.TT_FUN;
      nval = i;
      operands = new MathematicalExpression.TreeNode[ops.size()];
      for(i=0;i<operands.length;i++) {
	operands[i] = (MathematicalExpression.TreeNode) ops.elementAt(i);
      }
    }
    
    /**
     * Construct an operator node
     * 
     * @param t the operator '+','-','*','/'
     * @param ops the operands of the operator
     * @throws Exception is something goes wrong
     */        
    public TreeNode(int t,Vector ops) throws Exception {
      type = t;
      operands = new MathematicalExpression.TreeNode[ops.size()];
      for(int i=0;i<operands.length;i++) {
	operands[i] = (MathematicalExpression.TreeNode) ops.elementAt(i);
      }
    }
    
    /**
     * Evaluate the tree with for specific values of the variables
     * 
     * @param symbols a map associating a Double value to each variable name
     * @return the evaluation
     * @throws Exception if a symbol, function or node type is unknown
     */  
    public double eval(Map symbols) throws Exception {
      switch (type) {
	case Tokenizer.TT_NUMBER: return nval;
	case Tokenizer.TT_VAR: 
	  if (!symbols.containsKey(sval)) {
	    throw new Exception("Unknow symbol " + sval);
	  }
	  return ((Double) symbols.get(sval)).doubleValue();
	case '+': return operands[0].eval(symbols) + operands[1].eval(symbols);
	case '-': 
	  if (operands.length > 1) {