/*
Copyright @ 2004, The Institute for Genomic Research (TIGR).
All rights reserved.
*/

/***************************************************************************
 * Author:  Jianwei(Jerry) Li.
 * Name:  ExpressionParser (Version 1.0)
 * Date:  Created: 10/15/2004 and modified: 11/04/2004
 * Descp: A Java class that evaluate a formula passed in.
 ***************************************************************************/

package org.tigr.util.formula;

import java.io.*;

import org.tigr.util.*;
import org.tigr.util.formula.node.MathNode;
import org.tigr.util.formula.node.EvaluateException;

public class ExpressionParser implements Variant {

  private MathTree gTree;
  private String gExpr;

  public ExpressionParser(String formula) {
    gExpr = formula;
  }

  public String evaluate(){
    String result = null;

    if(gTree != null){
      try{
        result = "" + gTree.evaluate();
      } catch (EvaluateException eex){

      }
    }
    return result;
  }

  /***************************************************************************
   * <b>Description: </b>
   *   evaluate the formula with passed value
   * <p><b>Parameter: </b>
   * <br> operants -- the values.
   * <p><b> Return: </b> the result of the calculation in String format.
   ***************************************************************************/
  public String evaluate(String[] operants, boolean iRes) {
    String result = null;
    float res;

    if(gTree != null){
      try{
        res = gTree.evaluate(operants);
        if(iRes){
          result = "" + (int)res;
        } else {
          result = "" + res;
        }

      } catch (EvaluateException eex){

      }
    }
    return result;
  }

  /***************************************************************************
   * <b>Description: </b>
   *   starts to parser the formula.
   * <p><b> Return: </b> the result of the calculation in String format.
   ***************************************************************************/
  public boolean execute() {
    boolean moreFormula = true;
    MathNode curNode;
    MathNode[] nodes;
    String rEnd = new String("");
    String[] moreExpr;

    gTree = new MathTree();
    buildMathTree(gExpr, 1);
    curNode = gTree.getNodeAt(1);
    while(curNode.getChildren() != null){
      nodes = curNode.getChildren();
      rEnd = nodes[1].getContent();
      if(!isNumber(rEnd)){
        int id = nodes[1].getIndex();
        buildMathTree(rEnd, id);
      }
      curNode = nodes[0];
    }

    while(moreFormula){
      moreExpr = gTree.findExpression();
      if(moreExpr != null){
        buildMathTree(moreExpr[0], Integer.parseInt(moreExpr[1]));
      } else {
        moreFormula = false;
      }
    }

    return true;
  }

  /***************************************************************************
   * <b>Description: </b>
   *    set up a tree to express the formula.
   * <p><b>Parameters: </b>
   * <br> operation -- the formula expression.
   * <br> ndAddr -- the index of a node of the tree.
   **************************************************************************/
  private void buildMathTree(String operation, int ndAddr){
    String leftVal, rightVal;
    String bitems[] = new String[3];

    bitems[0] = operation;

    while(true){
     bitems = buildTwoItems(bitems[0]);
     /*for(int i=0; i<bitems.length; i++){
       System.out.println(bitems[i]);
     }
     System.out.println();*/

     if(bitems[0] == null || bitems[1] == null){
       break;
     }
     leftVal = bitems[0];
     rightVal = bitems[2];
     if(isOperator(bitems[1].charAt(0), false)){
       gTree.extendTree(bitems, ndAddr);
     }
     if(leftVal == null || rightVal == null ||
        ((leftVal.equals("") || isNumber(leftVal)) && (rightVal.equals("") || isNumber(rightVal)))){
       break;
     }
   }
  }

  /****************************************************************************
   * <b>Description: </b>
   *    parses the passed formula and change it into a format of two items
   *    separeted by an operator.
   * <p><b>Parameter: </b>
   * <br> formula -- the formula expression.
   * <p><b>Return: </b> a string array that has three elements: left operent,
   *                    operator, and right operent.
   ***************************************************************************/
  private String[] buildTwoItems(String formula){
    char ch;
    int end;
    int lpIndx;  // left parenthesis address.
    String[] temp = new String[3];

    end = formula.length();
    for(int i=end-1; i>=0; i--){
      ch = formula.charAt(i);
      if(ch == OPERATORS[0] || ch == OPERATORS[1]){ // '+', '-'
        temp[0] = formula.substring(0, i);
        temp[1] = "" + ch;
        temp[2] = formula.substring(i+1, end);
        i = -1;

      } else if(ch == OPERATORS[2]){ // 'x'
        lpIndx = hasParenthesis(formula.substring(0, i), false);
        if( lpIndx > 0){
          temp[0] = formula.substring(0, lpIndx);
          temp[1] = "" + formula.charAt(lpIndx);
          temp[2] = formula.substring(lpIndx+1, end);
        } else {
          temp[0] = formula.substring(0, i);
          temp[1] = "" + ch;
          temp[2] = formula.substring(i+1, end);
        }
        i = -1;

      } else if(ch == OPERATORS[3]){ // '/'
        lpIndx = hasParenthesis(formula.substring(0, i), true);
        if( lpIndx > 0){
          temp[0] = formula.substring(0, lpIndx);
          temp[1] = "" + formula.charAt(lpIndx);
          temp[2] = formula.substring(lpIndx+1, end);
        } else {
          temp[0] = formula.substring(0, i);
          temp[1] = "" + ch;
          temp[2] = formula.substring(i+1, end);
        }
        i = -1;

      } else if(ch == OPERATORS[5]){
        lpIndx = findLeftParenthesis(formula.substring(0, i+1));
        if(lpIndx > 0){
          int preOp = isPlusOrMinus(formula.substring(0, lpIndx), false);
          if(preOp > 0){
            temp[0] = formula.substring(0, lpIndx-1);
            temp[1] = "" + formula.charAt(lpIndx-1);
            temp[2] = formula.substring(lpIndx+1, end-1);
          } else {
            preOp = findPreOperator(formula.substring(0, lpIndx));
            if(preOp > 0){
              temp[0] = formula.substring(0, preOp);
              temp[1] = "" + formula.charAt(preOp);
              temp[2] = formula.substring(preOp+1, end);
            } else {
              temp[0] = formula.substring(0, lpIndx-1);
              temp[1] = "" + formula.charAt(lpIndx-1);
              temp[2] = formula.substring(lpIndx+1, end-1);
            }
          }
        } else {
          temp[2] = formula.substring(0, lpIndx);
          temp[1] = "" + ch;
          temp[0] = formula.substring(lpIndx+1, end-1);
        }

        i = -1;
      }
    }
    return temp;
  }

  /****************************************************************************
   * <b>Description: </b>
   *    search the passed formula to find the correct left parenthesis.
   * <p><b>Parameter: </b>
   * <br> formula --- the formula that has the parenthesis.
   * <p><b> Return: </b> the index of the parenethsis.
   ***************************************************************************/
  private int findLeftParenthesis(String formula){
    char ch;
    int indx, length;
    int lpNum, rpNum;  // number of parentenses
    lpNum = 0;
    rpNum = 0;

    length = formula.length();
    indx = length;

    for(int i=length-1; i>=0; i--){
      ch = formula.charAt(i);
      if(ch == OPERATORS[5]){
        rpNum++;
      } else if(ch == OPERATORS[4]){
        lpNum++;
        indx = i;
      }
      if(rpNum == lpNum && indx < length){
        return indx;
      }
    }

    return indx;
  }

  private int findPreOperator(String formula){
    char ch;
    int indx = 0;
    int count = 0;
    int length = formula.length();

    for(int i=length-1; i>=0; i--){
      ch = formula.charAt(i);
      if(isOperator(ch, false)){
        count++;
      }
      if(ch == OPERATORS[5]){
        return (findLeftParenthesis(formula.substring(0, i+1)) - 1);
      }
      if(count == 2){
        indx = i;
        i = -1;
      }
    }
    return indx;
  }

  /**************************************************************************
   * <b>Description: </b>
   *    search the last '+' and '-' in the passed formula.
   * <p><b>Parameter: </b>
   * <br> formula -- the formula to be checked.
   * <p><b>Return: </b> the index of the operator.
   ****************************************************************************/
  private int  getLastPlusOrMinus(String formula){
    int addr = -1;
    int end;
    char ch;

    end = formula.length();
    for(int i=end-1; i>=0; i--){
      ch = formula.charAt(i);
      if(ch == OPERATORS[0] || ch == OPERATORS[1]){
        return i;
      }
      if(ch == OPERATORS[5]){
        return (i+1);
      }
    }
    return addr;
  }

  /**************************************************************************
   * <b>Description: </b>
   *    checks if the passed formula has paranethsis at the end.
   * <p><b>Parameter: </b>
   * <br> formula -- the formula to be checked.
   * <br> plusMul -- includes '*'
   * <p><b>Return: </b> the index of the left parenthesis in the formalu string.
   ****************************************************************************/
  private int hasParenthesis(String formula, boolean plusMul){
    int addr = -1;
    int end;
    char ch;

    end = formula.length();
    for(int i=end-1; i>=0; i--){
      ch = formula.charAt(i);
      if(isOperator(ch, true)){
        if(ch == OPERATORS[5]){
          addr = findLeftParenthesis(formula.substring(0, i+1));
          addr--;
        } else {
          if(plusMul){
            addr = isPlusOrMinus(formula.substring(0, end-1), plusMul);
          } else {
            addr = getLastPlusOrMinus(formula.substring(0, end-1));
          }
        }
        return addr;
      }
    }
    return addr;
  }

  /***************************************************************************
   * <b>Description: </b>
   *    checks if the passed string is a number or not.
   * <p><b>Parameters: </b>
   * <br> st -- the string.
   * <p><b> Return: </b> true if it is; otherwise, false.
   **************************************************************************/
  private boolean isNumber(String st){
    float temp;
    try{
      temp = Float.parseFloat(st);
      return true;
    } catch (NumberFormatException nfe){
      return false;
    }
  }

  /**************************************************************************
   * <b>Description: </b>
   *    checks if the last operator is '+' or '-'.
   * <p><b>Parameter: </b>
   * <br> formula -- the formula to be checked.
   * <br> plusMul -- includes '*'
   * <p><b>Return: </b> the index of the operater in the formalu string.
   ****************************************************************************/
  private int isPlusOrMinus(String formula, boolean plusMul){
    int addr = -1;
    int end;
    char ch;

    end = formula.length();
    for(int i=end-1; i>=0; i--){
      ch = formula.charAt(i);
      if(plusMul){
        if(ch == OPERATORS[0] || ch == OPERATORS[1] || ch == OPERATORS[2]){
          addr = i;
          i = -1;
        } else if(ch == OPERATORS[3] || ch == OPERATORS[5]){
          i = -1;
        }
      } else {
        if(ch == OPERATORS[0] || ch == OPERATORS[1]){
          addr = i;
          i = -1;
        } else if(ch == OPERATORS[2] || ch == OPERATORS[3] || ch == OPERATORS[5]){
          i = -1;
        }
      }
    }

    return addr;
  }

  /***************************************************************************
   * <b>Description: </b>
   *    checks if the passed character is an operator.
   * <p><b>Parameters: </b>
   * <br> ch -- the character.
   * <p><b> Return: </b> true if it is; otherwise, false.
   **************************************************************************/
  private boolean isOperator(char ch, boolean all){
    boolean yes = false;
    int numOps;

    if(all){
      numOps = 6;
    } else {
      numOps = 4;
    }

    for(int i=0; i<numOps; i++){
      if(ch == OPERATORS[i]){
        yes = true;
        i = numOps;
      }
    }
    return yes;
  }
}