import java.lang.Math;

/**
 * <p>Title: Equation Parser</p>
 * <p>Description: Parses mathematical equations</p>
 * <p>Copyright: Copyright (c) 2003</p>
 * <p>Company: </p>
 * @author Chris Bolduc
 * @version 1.0
 *
 *  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 3 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, see <http://www.gnu.org/licenses/>.
 */

public class ParseEquation
{
  static final boolean debug = false;

  /**
   * Evaluates an equation for 'x'
   * @param equation String
   * @param x double
   * @return double
   */
  public static double parseEq(String equation, double x)
  {
    if(debug)System.out.println("x is: " + x);
    equation = evaluate(equation, x);
    try
    {
      equation = parenthesis(equation);
    }
    catch(Exception e)
    {
      e.printStackTrace();
    }
    equation = advancedMathOperators(equation);

    if (equation.equals("Infinity") || equation.equals("-Infinity") ||
        equation.equals("NaN") || equation.indexOf('E') != -1)
      return Double.NaN;
    equation = basicMathOperators(equation);
    if (equation.equals("Infinity") || equation.equals("-Infinity") ||
        equation.equals("NaN") || equation.indexOf('E') != -1)
      return Double.NaN;

    if(debug)System.out.println("Final Equation: " + equation);
    return Double.parseDouble(equation);
  }

  /**
   * Replaces 'x' in the equation with the supplied value for x.
   * Adds * where implied multiplication should be.
   * @param equation String
   * @param x double
   * @return String
   */
  public static String evaluate(String equation, double x)
  {
    StringBuffer temp = new StringBuffer(equation);

    for (int i = 0; i < temp.length(); i++)
      if (temp.charAt(i) == 'x')
      {
        if (i > 0 && (temp.charAt(i - 1) >= '0' && temp.charAt(i - 1) <= '9'))
          temp.replace(i, i + 1, '*' + Double.toString(x));
        else
          temp.replace(i, i + 1, Double.toString(x));
      }
      // Insert '*' where necessary (Java doesn't support implied multiplication)
      else if (temp.charAt(i) == '(' &&
               (i - 1 != -1 && (i > 0 && (temp.charAt(i - 1) >= '0'
                                          && temp.charAt(i - 1) <= '9') ||
                                temp.charAt(i - 1) == ')')))
      {
        temp.insert(i, '*');
        i++;
      }
      else if ( ( (temp.charAt(i) >= '0' && temp.charAt(i) <= '9') &&
                 i - 1 == -1) ||
               (temp.charAt(i) >= '0' && temp.charAt(i) <= '9') &&
               (temp.charAt(i - 1) != '.')) // Turns 3 into 3.0, 10 into 10.0, etc
      {
        if ( ( (temp.charAt(i) >= '0' && temp.charAt(i) <= '9') &&
              i + 1 == temp.length()) ||
            ! ( (temp.charAt(i + 1) >= '0' && temp.charAt(i + 1) <= '9') ||
               temp.charAt(i + 1) == '.'))
          temp.insert(i + 1, ".0");
      }
    return temp.toString();
  }

  /**
   * Recursive function.  Removes parenthesis from an equation and simplifies
   * whatever expression is inside.
   * @param eq String
   * @return String
   * @throws exception for invalid/unclosed parenthesis
   */
  public static String parenthesis(String eq) throws Exception
  {
    int nParenthesis = 0;
    int n = eq.indexOf('(');
    StringBuffer temp = new StringBuffer(eq);

    if (n == -1) // Base case: no parenthesis
      return eq;
    nParenthesis = 1;
    for(int i = n + 1; i < eq.length(); ++i)
    {
      if(eq.charAt(i) == '(')
        ++nParenthesis;
      else if(eq.charAt(i) == ')')
        --nParenthesis;
      if(nParenthesis == 0)
      {
        temp.replace(n, i + 1,
                     Double.toString(parseEq(eq.substring(n + 1, i), 0)));
        return temp.toString();
      }
    }
    throw new Exception("Unclosed or invalid parenthesis.");
  } // parenthesis()

  /**
   * Parses some operations such as log and abs
   * @param eq String
   * @return String
   */
  public static String advancedMathOperators(String eq)
  {
    StringBuffer temp = new StringBuffer(eq),
        number = new StringBuffer();

    int indexOfOperator = -1;

    double result;

    indexOfOperator = eq.indexOf("log"); // Start with logarithms
    if (indexOfOperator != -1)
    {
      for (int n = indexOfOperator + 3; n < eq.length(); n++)
      {
        if ( (eq.charAt(n) >= '0' && eq.charAt(n) <= '9') ||
            eq.charAt(n) == '.')
          number.append(eq.charAt(n));
        else if (eq.charAt(indexOfOperator + 3) == '-')
          return "NaN";
        else
          break;
      }
      if (debug) System.out.println("Taking log of: " + number);
      if (debug) System.out.println("Result: " +
                                    (Math.log(Double.parseDouble(number.
          toString()))));
      result = Math.log(Double.parseDouble(number.toString()));
      temp.replace(indexOfOperator, indexOfOperator + 3 + number.length(),
                   Double.toString(result));
      if (debug) System.out.println("Equation after log: " + temp);
      if (advancedMathOperators(temp.toString()).equals("NaN"))
        return "NaN";
      eq = advancedMathOperators(temp.toString());
    }

    indexOfOperator = eq.indexOf("abs"); // Now do absolute value
    if (indexOfOperator != -1)
    {
      for (int n = indexOfOperator + 3; n < eq.length(); n++)
      {
        if ( (eq.charAt(n) >= '0' && eq.charAt(n) <= '9') ||
            eq.charAt(n) == '.' || eq.charAt(n) == '-')
          number.append(eq.charAt(n));
        else
          break;
      }
      if (debug) System.out.println("Taking abs of: " + number);
      if (debug) System.out.println("Result: " +
                                    (Math.abs(Double.parseDouble(number.
          toString()))));
      result = Math.abs(Double.parseDouble(number.toString()));
      temp.replace(indexOfOperator, indexOfOperator + 3 + number.length(),
                   Double.toString(result));
      if (debug) System.out.println("Equation after abs: " + temp);
      if (advancedMathOperators(temp.toString()).equals("NaN"))
        return "NaN";
      eq = advancedMathOperators(temp.toString());
    }

    if (debug) System.out.println("AdvancedMathOperators return reached.");
    return eq;
  }

  /**
   * Parses basic math operations ( + - * / )
   * @param eq String
   * @return String
   */
  public static String basicMathOperators(String eq)
  {
    StringBuffer temp = new StringBuffer(eq);
    double[] locations;
    int signOccurances = 0;

    //double result;

    // First do the exponents
    for (int n = 0; n < temp.length(); n++)
    {
      if (temp.charAt(n) == '^')
        signOccurances++;
    }

    for (int n = 0; n < signOccurances; n++)
    {
      locations = findReplacements('^', temp.toString());
      temp.replace( (int) locations[0], (int) locations[1],
                   Double.toString(Math.pow(locations[2], locations[3])));
    }

    // Then divide
    signOccurances = 0;

    for (int n = 0; n < temp.length(); n++)
    {
      if (temp.charAt(n) == '/')
        signOccurances++;
    }

    for (int n = 0; n < signOccurances; n++)
    {
      locations = findReplacements('/', temp.toString());
      temp.replace( (int) locations[0], (int) locations[1],
                   Double.toString(locations[2] / locations[3]));
    }

    // Then multiply
    signOccurances = 0;

    for (int n = 0; n < temp.length(); n++)
    {
      if (temp.charAt(n) == '*')
        signOccurances++;
    }

    for (int n = 0; n < signOccurances; n++)
    {
      locations = findReplacements('*', temp.toString());
      temp.replace( (int) locations[0], (int) locations[1],
                   Double.toString(locations[2] * locations[3]));
    }

    // Then add and subtract.  This one is particularly difficult because
    // the order of both matters.  (5-3+2 = 4, not 0)
    if (debug) System.out.println(
        "Before adding and subtracting, the equation is: " + temp);

    StringBuffer order = new StringBuffer();

    for (int n = 0; n < temp.length(); n++)
    {
      if (temp.charAt(n) == '+' || temp.charAt(n) == '-')
        order.append(temp.charAt(n));
    }

    for (int n = 0; n < order.length(); n++)
    {
      // If the equation starts with a negative number, ignore the negative sign
      if (temp.charAt(0) == '-' && n == 0)
      {
        // If it is a double negative, delete the first TWO characters
        if (temp.charAt(1) == '-')
        {
          temp.delete(0, 2);
          n++; // Now two of the signs are gone, but n is just incrimented once.
               // This fixes that.
        }
      }
      else
      {
        locations = findReplacements(order.charAt(n), temp.toString());
        if (order.charAt(n) == '+')
          temp.replace( (int) locations[0], (int) locations[1],
                       Double.toString(locations[2] + locations[3]));
        else
          temp.replace( (int) locations[0], (int) locations[1],
                       Double.toString(locations[2] - locations[3]));
        if (debug) System.out.println("Order.length is: " + order.length());
      }
    }
    if (debug) System.out.println(
        "At the end of basicMathOperators(), the equation is: " + temp);
    return temp.toString();
  }

  /**
   * Used to replace a single expression (ie, 3 + 4) with the result of the
   * expression (ie, 7).  Finds the FIRST occurance of the supplied sign.
   * @param sign char
   * @param expression String
   * @return double[] numbers
   * numbers[0] = start of the expression
   * numbers[1] = end of the expression
   * numbers[2] = first number (ie, 3)
   * numbers[3] = second number (ie, 4)
   */
  public static double[] findReplacements(char sign, String expression)
  {
    StringBuffer before = new StringBuffer(),
        after = new StringBuffer();
    double[] numbers = new double[4];
    int digitsBeforeSign = 0,
        digitsAfterSign = 0,
        signAmt = 0;

    for (int signPos = 1; signPos < expression.length(); signPos++)
    {
      if (expression.charAt(signPos) == sign)
      {
        if (debug) System.out.println(sign);
        signAmt++;

        // Check to see if the equation is in scientific notation
        if (expression.charAt(signPos - 1) == 'E')
          break; // from first for() loop

        // Find out how many digits are before the sign
        for (int i = 1; i < expression.length() && signPos - i != -1; i++)
        {
          if ( ('0' <= expression.charAt(signPos - i) && expression.charAt(signPos - i) <= '9') ||
              expression.charAt(signPos - i) == '.')
            digitsBeforeSign++;
          // Check if the equation starts with a negative number
          else if (expression.charAt(signPos - i) == '-' &&
                   (signPos - i - 1 == -1 || expression.charAt(signPos - i - 1) == '('))
            digitsBeforeSign++;
          else
            break;
        }

        // Find out what number is before the sign
        for (int i = signPos - digitsBeforeSign; i < signPos; i++)
        {
          before.append(expression.charAt(i));
        }

        // Finds out what digits are after the sign
        for (int i = 1; i < expression.length() - signPos; i++)
        {
          if ( ('0' <= expression.charAt(signPos + i) && expression.charAt(signPos + i) <= '9') ||
              expression.charAt(signPos + i) == '.')
          {
            after.append(expression.charAt(signPos + i));
            digitsAfterSign++;
          }
          // If the equation ends with a negative number
          else if (i == 1 &&
                   (expression.charAt(signPos + i) == '-' || expression.charAt(signPos + i) == '('))
          {
            if (debug) System.out.println("Number after is negative");
            after.append(expression.charAt(signPos + i));
            digitsAfterSign++;
          }
          else
            break;
        }

        if (debug) System.out.println("Currently, the equation is: " + expression);
        if (debug) System.out.println("Start position: " +
                                      (signPos - digitsBeforeSign));
        numbers[0] = signPos - digitsBeforeSign;
        if (debug) System.out.println("End position: " +
                                      (signPos + digitsAfterSign + 1));
        numbers[1] = signPos + digitsAfterSign + 1;
        if (debug) System.out.println("Number before: " +
                                      (Double.parseDouble(before.toString())));
        numbers[2] = Double.parseDouble(before.toString());
        if (debug) System.out.println("Number after: " +
                                      (Double.parseDouble(after.toString())));
        numbers[3] = Double.parseDouble(after.toString());

        break; //from the first for() loop
      } // if()
    } // first for() loop
    return numbers;
  }
}