source: src/main/java/weka/core/AttributeExpression.java @ 8

/*
 *    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.
 */

/*
 *    AttributeExpression.java
 *    Copyright (C) 2006 University of Waikato, Hamilton, New Zealand
 *
 */

package weka.core;

import java.io.Serializable;
import java.util.Stack;
import java.util.StringTokenizer;
import java.util.Vector;

/**
 * A general purpose class for parsing mathematical expressions
 * involving attribute values. Values can be provided in an array
 * or in an Instance. Values are accessed in the expression by
 * prefixing their index (starting at 1) with the character 'a'.
 *
 * <pre> Example expression: a1^2*a5/log(a7*4.0) </pre>
 *
 * Supported opperators: +, -, *, /, ^, log, abs, cos, exp, sqrt,
 * floor, ceil, rint, tan, sin, (, ).
 *
 * @author Mark Hall
 * @version $Revision: 5988 $
 */
public class AttributeExpression
  implements Serializable, RevisionHandler {

  /** for serialization */
  static final long serialVersionUID = 402130123261736245L;
  
  /**
   * Interface implemented by operators and operants.
   */
  private interface ExpressionComponent {};

  /**
   * Inner class handling an attribute index as an operand
   */
  private class AttributeOperand  
    implements ExpressionComponent, Serializable, RevisionHandler {
    
    /** for serialization */
    static final long serialVersionUID = -7674280127286031105L;

    /** the index of the attribute */
    protected int m_attributeIndex;

    /** true if the value of the attribute are to be multiplied by -1 */
    protected boolean m_negative;

    /**
     * Constructor
     * 
     * @param operand
     * @param sign
     * @throws Exception
     */
    public AttributeOperand(String operand, boolean sign) throws Exception {
      // strip the leading 'a' and set the index
      m_attributeIndex = (Integer.parseInt(operand.substring(1)))-1;
      m_negative = sign;
    }

    /**
     * Return a string describing this object
     * @return a string descibing the attribute operand
     */
    public String toString() {
      String result = "";
      if (m_negative) {
        result += '-';
      }
      return result+"a"+(m_attributeIndex+1);
    }
    
    /**
     * Returns the revision string.
     * 
     * @return          the revision
     */
    public String getRevision() {
      return RevisionUtils.extract("$Revision: 5988 $");
    }
  }

  /**
   * Inner class for storing numeric constant opperands
   */
  private class NumericOperand 
    implements ExpressionComponent, Serializable, RevisionHandler {
    
    /** for serialization */
    static final long serialVersionUID = 9037007836243662859L;

    /** numeric constant */
    protected double m_numericConst;

    /**
     * Constructor
     * 
     * @param operand
     * @param sign
     * @throws Exception
     */
    public NumericOperand(String operand, boolean sign) throws Exception {
      m_numericConst = Double.valueOf(operand).doubleValue();
      if (sign) {
        m_numericConst *= -1.0;
      }
    }
    
    /**
     * Return a string describing this object
     * @return a string descibing the numeric operand
     */
    public String toString() {
      return ""+m_numericConst;
    }
    
    /**
     * Returns the revision string.
     * 
     * @return          the revision
     */
    public String getRevision() {
      return RevisionUtils.extract("$Revision: 5988 $");
    }
  }

  /**
   * Inner class for storing operators
   */
  private class Operator 
    implements ExpressionComponent, Serializable, RevisionHandler {
    
    /** for serialization */
    static final long serialVersionUID = -2760353522666004638L;

    /** the operator */
    protected char m_operator;

    /**
     * Constructor
     * 
     * @param opp the operator
     */
    public Operator(char opp) {
      if (!isOperator(opp)) {
        throw new IllegalArgumentException("Unrecognized operator:" + opp);
      }
      m_operator = opp;
    }

    /**
     * Apply this operator to the supplied arguments
     * @param first the first argument
     * @param second the second argument
     * @return the result
     */
    protected double applyOperator(double first, double second) {
      switch (m_operator) {
        case '+' :
          return (first+second);
        case '-' :
          return (first-second);
        case '*' :
          return (first*second);
        case '/' :
          return (first/second);
        case '^' :
          return Math.pow(first,second);
      }
      return Double.NaN;
    }

    /**
     * Apply this operator (function) to the supplied argument
     * @param value the argument
     * @return the result
     */
    protected double applyFunction(double value) {
      switch (m_operator) {
        case 'l' :
          return Math.log(value);
        case 'b' :
          return Math.abs(value);
        case 'c' :
          return Math.cos(value);
        case 'e' :
          return Math.exp(value);
        case 's' :
          return Math.sqrt(value);
        case 'f' :
          return Math.floor(value);
        case 'h' :
          return Math.ceil(value);
        case 'r' :
          return Math.rint(value);
        case 't' :
          return Math.tan(value);
        case 'n' :
          return Math.sin(value);
      }
      return Double.NaN;
    }

    /**
     * Return a string describing this object
     * @return a string descibing the operator
     */
    public String toString() {
      return ""+m_operator;
    }
    
    /**
     * Returns the revision string.
     * 
     * @return          the revision
     */
    public String getRevision() {
      return RevisionUtils.extract("$Revision: 5988 $");
    }
  }

  /** Operator stack */
  private Stack<String> m_operatorStack = new Stack<String>();

  /** Supported operators. l = log, b = abs, c = cos, e = exp, s = sqrt, 
      f = floor, h = ceil, r = rint, t = tan, n = sin */
  private static final String OPERATORS = "+-*/()^lbcesfhrtn";
  /** Unary functions. l = log, b = abs, c = cos, e = exp, s = sqrt, 
      f = floor, h = ceil, r = rint, t = tan, n = sin */
  private static final String UNARY_FUNCTIONS = "lbcesfhrtn";

  /** Holds the original infix expression */
  private String m_originalInfix;
  
  /** Holds the expression in postfix form */
  private Vector<ExpressionComponent> m_postFixExpVector;

  /** True if the next numeric constant or attribute index is negative */
  private boolean m_signMod = false;

  /** Holds the previous token */
  private String m_previousTok = "";

    /**
   * Handles the processing of an infix operand to postfix
   * @param tok the infix operand
   * @throws Exception if there is difficulty parsing the operand
   */
  private void handleOperand(String tok) throws Exception {
    // if it contains an 'a' then its an attribute index
    if (tok.indexOf('a') != -1) {
      m_postFixExpVector.addElement(new AttributeOperand(tok,m_signMod));
    } else {
      try {
        // should be a numeric constant
        m_postFixExpVector.addElement(new NumericOperand(tok, m_signMod));
      } catch (NumberFormatException ne) {
        throw new Exception("Trouble parsing numeric constant");
      }
    }
    m_signMod = false;
  }

  /**
   * Handles the processing of an infix operator to postfix
   * @param tok the infix operator
   * @throws Exception if there is difficulty parsing the operator
   */
  private void handleOperator(String tok) throws Exception {
    boolean push = true;

    char tokchar = tok.charAt(0);
    if (tokchar == ')') {
      String popop = " ";
      do {
        popop = (String)(m_operatorStack.pop());
        if (popop.charAt(0) != '(') {
          m_postFixExpVector.addElement(new Operator(popop.charAt(0)));
        }
      } while (popop.charAt(0) != '(');
    } else {
      int infixToc = infixPriority(tok.charAt(0));
      while (!m_operatorStack.empty() && 
             stackPriority(((String)(m_operatorStack.peek())).charAt(0)) 
             >= infixToc) {
        
        // try an catch double operators and see if the current one can
        // be interpreted as the sign of an upcoming number
        if (m_previousTok.length() == 1 && 
            isOperator(m_previousTok.charAt(0)) &&
            m_previousTok.charAt(0) != ')') {
          if (tok.charAt(0) == '-') {
            m_signMod = true;
          } else {
            m_signMod = false;
          }
          push = false;
          break;
        } else {
          String popop = (String)(m_operatorStack.pop());
          m_postFixExpVector.addElement(new Operator(popop.charAt(0)));
        }
      }
      if (m_postFixExpVector.size() == 0) {
        if (tok.charAt(0) == '-') {
          m_signMod = true;
          push = false;
        }
      }

      if (push) {
        m_operatorStack.push(tok);
      }
    }
  }

  /**
   * Converts a string containing a mathematical expression in infix form
   * to postfix form. The result is stored in the vector m_postfixExpVector
   *
   * @param infixExp the infix expression to convert
   * @throws Exception if something goes wrong during the conversion
   */
  public void convertInfixToPostfix(String infixExp) throws Exception {
    m_originalInfix = infixExp;

    infixExp = Utils.removeSubstring(infixExp, " ");
    infixExp = Utils.replaceSubstring(infixExp,"log","l");
    infixExp = Utils.replaceSubstring(infixExp,"abs","b");
    infixExp = Utils.replaceSubstring(infixExp,"cos","c");
    infixExp = Utils.replaceSubstring(infixExp,"exp","e");
    infixExp = Utils.replaceSubstring(infixExp,"sqrt","s");
    infixExp = Utils.replaceSubstring(infixExp,"floor","f");
    infixExp = Utils.replaceSubstring(infixExp,"ceil","h");
    infixExp = Utils.replaceSubstring(infixExp,"rint","r");
    infixExp = Utils.replaceSubstring(infixExp,"tan","t");
    infixExp = Utils.replaceSubstring(infixExp,"sin","n");

    StringTokenizer tokenizer = new StringTokenizer(infixExp, OPERATORS, true);
    m_postFixExpVector = new Vector<ExpressionComponent>();

    while (tokenizer.hasMoreTokens()) {
      String tok = tokenizer.nextToken();
      
      if (tok.length() > 1) {
        handleOperand(tok);
      } else {
        // probably an operator, but could be a single char operand
        if (isOperator(tok.charAt(0))) {
          handleOperator(tok);
        } else {
          // should be a numeric constant
          handleOperand(tok);
        }
      }
      m_previousTok = tok;
    }
    while (!m_operatorStack.empty()) {
      String popop = (String)(m_operatorStack.pop());
      if (popop.charAt(0) == '(' || popop.charAt(0) == ')') {
        throw new Exception("Mis-matched parenthesis!");
      }
      m_postFixExpVector.addElement(new Operator(popop.charAt(0)));
    }
  }

  /**
   * Evaluate the expression using the supplied Instance.
   * Assumes that the infix expression has been converted to 
   * postfix and stored in m_postFixExpVector
   *
   * @param instance the Instance containing values to apply
   * the expression to
   * @throws Exception if something goes wrong
   */
  public double evaluateExpression(Instance instance)
    throws Exception {
    double [] vals = new double [instance.numAttributes()+1];
    for(int i = 0; i < instance.numAttributes(); i++) {
      if (instance.isMissing(i)) {
        vals[i] = Utils.missingValue();
      } else {
        vals[i] = instance.value(i);
      }
    }
    
    evaluateExpression(vals);
    return vals[vals.length - 1];
  }

  /**
   * Evaluate the expression using the supplied array of attribute values.
   * The result is stored in the last element of the array. Assumes that
   * the infix expression has been converted to postfix and stored in
   * m_postFixExpVector
   * @param vals the values to apply the expression to
   * @throws Exception if something goes wrong
   */
  public void evaluateExpression(double [] vals) throws Exception {
    Stack<Double> operands = new Stack<Double>();

    for (int i=0;i<m_postFixExpVector.size();i++) {
      Object nextob = m_postFixExpVector.elementAt(i);
      if (nextob instanceof NumericOperand) {
        operands.push(new Double(((NumericOperand)nextob).m_numericConst));
      } else if (nextob instanceof AttributeOperand) {
        double value = vals[((AttributeOperand)nextob).m_attributeIndex];
        /*if (Utils.isMissingValue(value)) {
          vals[vals.length-1] = Utils.missingValue();
          break;
        }*/
        if (((AttributeOperand)nextob).m_negative) {
          value = -value;
        }
        operands.push(new Double(value));
      } else if (nextob instanceof Operator) {
        char op = ((Operator)nextob).m_operator;
        if (isUnaryFunction(op)) {
          double operand = ((Double)operands.pop()).doubleValue();
          double result = ((Operator)nextob).applyFunction(operand);
          operands.push(new Double(result));
        } else {
          double second = ((Double)operands.pop()).doubleValue();
          double first = ((Double)operands.pop()).doubleValue();
          double result = ((Operator)nextob).applyOperator(first,second);
          operands.push(new Double(result));
        }
      } else {
        throw new Exception("Unknown object in postfix vector!");
      }
    }

    if (operands.size() != 1) {
      throw new Exception("Problem applying function");
    }

    Double result = ((Double)operands.pop());
    if (result.isNaN() || result.isInfinite()) {
      vals[vals.length-1] = Utils.missingValue();
    } else {
      vals[vals.length-1] = result.doubleValue();
    }
  }

  /**
   * Returns true if a token is an operator
   * @param tok the token to check
   * @return true if the supplied token is an operator
   */
  private boolean isOperator(char tok) {
    if (OPERATORS.indexOf(tok) == -1) {
      return false;
    }

    return true;
  }

  /**
   * Returns true if a token is a unary function
   * @param tok the token to check
   * @return true if the supplied token is a unary function
   */
  private boolean isUnaryFunction(char tok) {
    if (UNARY_FUNCTIONS.indexOf(tok) == -1) {
      return false;
    }

    return true;
  }

  /**
   * Return the infix priority of an operator
   * @param opp the operator
   * @return the infix priority
   */
  private int infixPriority(char opp) {
    switch (opp) {
      case 'l' : 
      case 'b' :
      case 'c' :
      case 'e' :
      case 's' :
      case 'f' :
      case 'h' :
      case 'r' :
      case 't' :
      case 'n' :
        return 3;
      case '^' :
        return 2;
      case '*' : 
        return 2;
      case '/' : 
        return 2;
      case '+' :
        return 1;
      case '-' :
        return 1;
      case '(' :
        return 4;
      case ')' :
        return 0;
      default :
        throw new IllegalArgumentException("Unrecognized operator:" + opp);
    }
  }

  /**
   * Return the stack priority of an operator
   * @param opp the operator
   * @return the stack priority
   */
  private int stackPriority(char opp) {
     switch (opp) {
       case 'l' :
       case 'b' :
       case 'c' :
       case 'e' :
       case 's' :
       case 'f' :
       case 'h' :
       case 'r' :
       case 't' :
       case 'n' :
         return 3;
       case '^' :
         return 2;
       case '*' : 
         return 2;
       case '/' : 
         return 2;
       case '+' :
         return 1;
       case '-' :
         return 1;
       case '(' :
         return 0;
       case ')' :
         return -1;
       default :
         throw new IllegalArgumentException("Unrecognized operator:" + opp);
    }
  }

  /**
   * Return the postfix expression
   *
   * @return the postfix expression as a String
   */
  public String getPostFixExpression() {
    return m_postFixExpVector.toString();
  }

  public String toString() {
    return m_originalInfix;
  }
  
  /**
   * Returns the revision string.
   * 
   * @return            the revision
   */
  public String getRevision() {
    return RevisionUtils.extract("$Revision: 5988 $");
  }
}