/*
   * Expression parser and interpreter class. Ver 1.1
   *
   * Java code Copyleft (l) Stanislav Sokolov, 1999, and onwards
   * Algorithm Copyleft (l) Steinar Foss, 1996, and onwards
   *
   * JavaScript, C and QuickBASIC versions can be found at Nemo's realms:
   * http://members.tripod.com/~stanislavs/utils/interpre.htm
   * and
   * http://members.tripod.com/~stanislavs/prog/prog.htm
   *
   * This program is subject to GNU General Public License ver. 2 of June 1991,
   * and any later version.
   * See http://members.tripod.com/~stanislavs/prog/copying for details.
   *
   * If you modify or distribute this code, make sure this header notice
   * follows it.
   */

import java.math.*;

public class Interpreter{

  //Maximum number of parenthesis
  private final static int MaxParam = 150;

  /*==========================================================================
   * This function is thought to become programmer's interface
   * While you can first parse() an expression, make some ajustments to it
   * and then pass it on to eval(), treating the exceptions separately,
   * it would be more convenient to just use interpret() and have a result
   * out (taking care of what exceptions that might have occured).
   * NB! If you are going to intrpret one function repeatedly, parse it first,
   * and then call eval() as it will amke things go faster.
   *==========================================================================*/
  public static double interpret(String s, double x) throws Exception{
    return eval(parse(s), x);
  }


  /*==========================================================================
   * The main expression evaluation function
   *==========================================================================*/
  public static double eval(String Formula, double x) throws Exception{

    //Variable declaration and initialization
    int i;                 //Counter
    boolean Empty = true;  //Flag for empying of number accumulator
    int NumLen = 0;        //Substring length of number
    int Orden = 0;         //Parentheses level
    double Type1 = 0;      //The number being handled (converted from string)

    double Sum [] = new double[MaxParam];
    double Overfac [] = new double[MaxParam];
    double Exp2 [] = new double[MaxParam];

    Overfac[0] = 1;
    Exp2[0] = Sum[0] = 0;

    //Main loop (the string is being prosessed from the end)
    for(i = Formula.length() - 1; i >= 0; i--){
      Empty = true;

      //Find the length of a number to work on
      if(((Formula.charAt(i) >= '0') && (Formula.charAt(i) <= '9')) || (Formula.charAt(i) == '.') || (Formula.charAt(i) == 'E') || ((Formula.charAt(i) == '-') && (Formula.charAt(i-1) == 'E') && (i > 0))){
	NumLen++;
	Empty = false;    //The number has not yet been found
      }

      //if the number is found, convert it to double and store in Type1
      if (Empty && (NumLen > 0)){
	NumLen++;
	Type1 = Double.valueOf(Formula.substring(i + 1, i + NumLen)).doubleValue();   //Convert
	NumLen = 0;                           //Ready to read next number
      }

      //Find which operation to perform
      if (Formula.charAt(i) == '*'){
	Overfac[Orden] *= Math.pow(Type1, Exp2[Orden] + 1);
	Type1 = Exp2[Orden] = 0;
      }

      if (Formula.charAt(i) == '/'){
	if(Math.pow(Type1, Exp2[Orden] + 1) == 0)
	  throw new InterpreterException("Error: Division by zero!");
	Overfac[Orden] /= Math.pow(Type1, Exp2[Orden] + 1);
	Type1 = Exp2[Orden] = 0;
      }

      if (Formula.charAt(i) == '+'){
	Sum[Orden] += Math.pow(Type1, Exp2[Orden] + 1) * Overfac[Orden];
	Overfac[Orden] = 1;
	Type1 = Exp2[Orden] = 0;
      }

      if (Formula.charAt(i) == '-'){
	if((Formula.charAt(i-1) != 'E') || (i == 0)){
	  Sum[Orden] -= Math.pow(Type1,Exp2[Orden] + 1) * Overfac[Orden];
	  Overfac[Orden] = 1;
	  Type1 = Exp2[Orden] = 0;
	}
      }

      //Return to previous level
      if (Formula.charAt(i) == '('){
	Type1 = Sum[Orden] + Math.pow(Type1, Exp2[Orden] + 1) * Overfac[Orden];
	Orden--;
      }

      //Jump to next level (the string is being prosessed from the end)
      if (Formula.charAt(i) == ')'){
	Orden++;
	Overfac[Orden] = 1;
	Exp2[Orden] = Sum[Orden] = 0;
      }

      if (Formula.charAt(i) == '^'){
	Exp2[Orden] = Type1 - 1;
	Type1 = 0;
      }

      if (Formula.charAt(i) == 'e')
	Type1 = Math.exp(Type1);

      if ((Formula.charAt(i) == 'C') || (Formula.charAt(i) == 'c'))
	Type1 = Math.cos(Type1);

      if ((Formula.charAt(i) == 'S') || (Formula.charAt(i) == 's'))
	Type1 = Math.sin(Type1);

      if ((Formula.charAt(i) == 'T') || (Formula.charAt(i) == 't'))
	Type1 = Math.tan(Type1);

      if ((Formula.charAt(i) == 'N') || (Formula.charAt(i) == 'n'))
	Type1 = Math.atan(Type1);

      if ((Formula.charAt(i) == 'L') || (Formula.charAt(i) == 'l')){
	if (Type1 <= 0)
	  throw new InterpreterException("Error: LOG of a negative number is not defined!");
	Type1 = Math.log(Type1);
      }

      if ((Formula.charAt(i) == 'A') || (Formula.charAt(i) == 'a'))
	Type1 = Math.abs(Type1);

      if ((Formula.charAt(i) == 'R') || (Formula.charAt(i) == 'r')){
	if (Type1 < 0.0)
	  throw new InterpreterException("Error: Square root of a negative value!");
	Type1 = Math.sqrt(Type1);
      }

      if ((Formula.charAt(i) == 'P') || (Formula.charAt(i) == 'p'))
	Type1 = Math.PI;

      if ((Formula.charAt(i) == 'X') || (Formula.charAt(i) == 'x'))
	Type1 = x;
    } //for

    //Prosess the first number in the string and store it in Type1 before
    //final calculation (The first number is always prosessed last!)
    if(!Empty){
      NumLen++;
      Type1 = Double.valueOf(Formula.substring(i + 1, i + NumLen)).doubleValue();
    }

    //The final calculation
    Sum[0] += Math.pow(Type1, (Exp2[0] + 1.0)) * Overfac[0];

    return Sum[0];

  } //eval


  /*==========================================================================
   * Expression verifyer.
   * Java code and algorithm Copyleft (l) Stanislav Sokolov, 1997, and onwards
   * This script is designed for use with expression interpreter function
   *
   * You may freely use this script as long as this copyleft notice
   * follows the script.
   *==========================================================================*/
  public static String parse(String Expr) throws Exception{

    //Initialize
    int i = 0, f = 0;  //Counters
    String Str = "";   //Accumulators
    int ParCount = 0;  //Parenthesis counter

    String Find[] = {"sin", "cos", "tan", "atan", "atn", "exp", "abs", "sqrt", "sqr", "pi", "log", " "};
    String Repl[] = {"s",   "c",   "t",   "n",    "n",   "e",   "a",   "r",    "r",   "p",  "l",   ""};

    //Check if the string is null-string or empty string
    if((Expr == null) || Expr.equals(""))
      throw new InterpreterException("Expression is an empty string!");

    //Replace long names with their short symbols
    for(i = 0; i <= 11; i++){
      Str = Expr.toLowerCase();
      f = Str.indexOf(Find[i]);
      if(f != -1){
	Str = Expr.substring(f + Find[i].length(), Expr.length());
	Expr = Expr.substring(0, f) + Repl[i] + Str;
	i--;       //A case of Find[i] has been found - try another search until no more cases found
      }
    }

    //Check if the amount of opening and closing parenthesis coinside . . .
    for(i = 0; i < Expr.length(); i++){
      if(Expr.charAt(i) == '(')	ParCount++;

      //Cannot handle an expression with that many nestes parenthesis
      if(ParCount > MaxParam)
	throw new InterpreterException("Too many parenthesis!\n");

      
      if(Expr.charAt(i) == ')')	ParCount--;
    }

    // . . . If not, abort calculation 
    if(ParCount != 0)
      throw new InterpreterException("Parenthesis count mismatch!\n" +
				     "  Check the number of opening and closing parenthesis.");

    //Check the last symbol in the expression
    f = Expr.charAt(Expr.length() - 1);
    if(!(((f >= '0') && (f <= '9')) || (f == 'p') || (f == ')') || (f == 'x')))
      throw new InterpreterException("Last symbol in the expression is illigal!\n" +
				     "  The last symbol must be a number (0 through 9), closing parenthesis ')' or symbol PI");

    return Expr;

  } //ParseExp

} //class Interpreter