Expression

import java.util.regex.Matcher;
import java.util.regex.Pattern;
/**
 * Name: Trevor Brown
 * Expression Project 2.0
 */
//Note: Currently all methods are made static to easily test their functionality in main.
public class Expression {

    private String ex;
    public Expression(String ex)
    {
        //Trim whitespace from string.
        ex = ex.replaceAll("\\s", "");
        if (checkSyntax(ex) == true)
            this.ex = ex;
        else
            throw new IllegalArgumentException("Improper syntax used!");
    }
    public String getEx()
    {
        return ex;
    }


    /**
     * @param e an expression in the form of a string.
     * @return True if the expression has proper syntax, and false if not.
     */
    public static boolean checkSyntax(String e)
    {

        //ACCEPTED TOKENS 0-9, (,),*,/,^,+,-,.
        //Use regex for check if anything other than these tokens are present.
        //I promise this is all of the criteria for proper syntax. You can't evaluate an expression that does not follow
        //these rules.
        Pattern p = Pattern.compile("[^\\-*\\/\\(\\)^\\+\\. 0-9]|--|[\\-*\\/^\\+.][\\-*\\/^\\+\\.]+|[(][*\\/^\\+\\.]|[\\-*\\/^\\+\\.][)]|[(][)]|[0-9][(]|[)][0-9]");
        Matcher m = p.matcher(e);
        if(m.find() == true)
            return false;

        //count parenthesis.
        int pCount = 0;
        for(int i = 0; i < e.length(); i++)
        {
            if(e.charAt(i) == '(')
                pCount++;
            if(e.charAt(i) == ')')
                pCount--;

            if (pCount < 0)
                return false;
        }
        if (pCount != 0)
            return false;
        return true;
    }

    /*
    First and most important subroutine is one that evaluates a single operation.
    The function will have three parameters. two doubles and an operator character.
     */

    /**
     *
     * @param d1 the first double
     * @param operator the operation to perform on the two doubles
     * @param d2 the second double
     *
     *           ==========================================================
     *           For example: operation(2, '*', 4)
     *           would compute the operation 2d*4d, which would return 8d.
     *           ==========================================================
     *
     * @return The computation of the two doubles with the given operator.
     */
    public static double operation(double d1, char operator, double d2)
    {
        double result = 0;
        switch(operator)
        {
            case '^':
                result = Math.pow(d1,d2);
                break;
            case '*':
                result = d1 * d2;
                break;
            case '/':
                result = d1 / d2;
                break;
            case '+':
                result = d1 + d2;
                break;
            case '-':
                result = d1 - d2;
                break;
        }

        return result;
    }

    /*
    Next we need to do a few things at once in order to use our operator method:
    First: we need to identify a single operation within a string.
    Second: we need to correctly parse that operation into the three parts required for the operation method.

    First: A single operation can be defined as two doubles with an operation between them.
    This definition however gets complicated due to the unique situation of the '-' sign both signifying a subtraction
    and a negative number.

    The most important thing to correctly execute this subroutine is to know when there is a
    negative number present within the operation. Since the core of this project is that when a parenthesis is reached,
    we recurse, we need to identify the single case where a parenthesis is not containing an operation but simply a negative number

    For example: "3*(2*(-4))-4*(-1)"
                        ^A  ^B
        A: The case of the '-' at A is representing a negative number.
        In evaluating weather we should recurse or not, a check needs to be made that there is actually an operation within.
        This way when it comes time to partition the expression into individual operations, there are a set of assumptions the
        method can have.

        A: '-' is representing a subtraction when and only when there is a number on both sides of the '-' or if the '-' is preceded by a ')'.
        There is another edge case of if the '-' is at the very beginning of the expression string. This is because we can't evaluate
        outside of the bounds of the string. It is required for the user to wrap a negative number in parentheses however the program
        will inevitably need to unwrap the parentheses for evaluation.

        B: is representing a subtraction because there is a ')' preceding it.

        So a single operation can be defined by the following:
        It can start with a '-' assuming a number does not precede it. It will contain an operator, and two doubles.
        The doubles may be wrapped in parentheses. If so they need to be removed.




    Now with the logic laid out, it's time to work on evaluating a string containing a single operation.
    called parseOperation.
    Goal:
    The goal of parseOperation is to take a string containing a single operation, parse it into the appropriate individual
    components and return a double that is the result of the operation. This method assumes the string is given with proper
    syntax.
    Parameters:
     String op -> a string containing a single operation in correct syntax.
    Returns: a double that is the result of the operation in the string.

    Therefore:
        Step One:   If present, remove all parentheses from the operation.
        Step Two:   Identify the true operator. in any given expression, there could be up two three operators present.
                    If there is not a leading '-' the first operator is always the true operator.
                    If there is a leading '-', the second operator is always the true operator.
                    Save the index of the true operator as an integer for later use.
        Step Three: We now have a clear and understandable format. We also have the index of the operator.
                    We create two Double variables d1 and d2 initialized to zero.
                    d1 = parseDouble(operation.subString(0, opIndex);
                    d2 = parseDouble(operation.subString(opIndex+1);
    */
    public static double parseOperation(String operation)
    {
        double result = 0;


        //Step One
        StringBuffer operationBuff = new StringBuffer(operation);
        for(int i = 0; i<operationBuff.length(); i++)
        {
            if(operationBuff.charAt(i) == '(' || operationBuff.charAt(i) == ')')
            {
                operationBuff.deleteCharAt(i);
            }
        }
        operation = operationBuff.toString();


        //Step Two
        int opIndex = 0;
        int index = 0;
        if(operation.charAt(0) == '-') index++;

        boolean operationFound = false;
        while(index < operation.length() && !operationFound)
        {
            switch (operation.charAt(index))
            {
                case '^':
                case '*':
                case'/':
                case '+':
                case '-':
                    opIndex = index;
                    operationFound = true;
                    break;
                default:
                    index++;
                    break;
            }
        }


        //Step Three
        double d1 = parseDouble(operation.substring(0, opIndex));
        double d2 = parseDouble(operation.substring(opIndex+1));

        result = operation(d1, operation.charAt(opIndex), d2);


        return result;
    }


    /*
    This will require us to simultaneously create the method that will correctly convert a single double in string form
    to a true double for evaluation. We will call this method parseDouble.
    Goal: To take a single double in string form and return it as a true double.
    Parameters:
    String dub -> a string containing a single double in correct format.
    First we check if there is a negative in front of the string.
    If so, we remove it and we set the negative flag to true.
    Once the negative sign is removed and the flag is correctly set, we parse the double to decimal form
    Then we multiply the double by -1 if the negative flag is true.

    Returns: The double that the string corresponds with.
     */
    public static double parseDouble(String theDouble)
    {
        double dub = 0;
        boolean negative = false;
        if(theDouble.charAt(0) == '-')
        {
            negative = true;
            theDouble = theDouble.substring(1);
        }
        int index = theDouble.indexOf(".");
        if(index == -1)
        {
            int pow = 0;
            for(int i = theDouble.length()-1; i>= 0; i--)
            {
                dub += (double) (theDouble.charAt(i) - 48) * Math.pow(10,pow);
                pow++;
            }

        }else
        {
            //Go left
            int pow = 0;
            for(int i = index-1; i>=0; i--)
            {
                dub += (double) (theDouble.charAt(i) - 48) * Math.pow(10,pow);
                pow++;
            }
            pow = -1;
            //Go right
            for(int i = index+1; i<theDouble.length(); i++)
            {
                dub += (double) (theDouble.charAt(i) - 48) * Math.pow(10,pow);
                pow--;
            }
        }
        if(negative)
            dub *= -1;
        return dub;
    }

    /*
    Now that we are able to successfully parse a single operation, we now need to be able to handle a string containing
    several operations.
    Assumptions:
    All parentheses present are present because they house a single negative number and NOT and operation.

    We have to follow the order of operations. We must be mindful of '-' signs. They are NOT operators if:
    they are at the beginning of the string, any other operation precedes them, or if a '(' precedes it.

    if any of these conditions are met, ignore it as a candidate for determining the next true operation.

    With these assumptions in place, we iterate through the string.
    We assign a value to each of the operators to compare them.
    '^' = 3; '*' and '/' = 2; '+' and '-' = 1;
    We iterate through finding the operator with the highest value closest to the left.
    Once this operator is found we need to find the two doubles surrounding it, so we can determine the upper
    and lower bounds of the substring.
    once found, we replace(lowerBound, upperBound, parseOperation(operation.substring(lowerBound, upperBound));

    We repeat this process until there are no more true operators.

    We will call this method parseSubExpression.
    Goal:
    The goal of this method is to evaluate a series of operations, eventually returning a single double.
    Parameters:
    String subExpression -> a string containing a sub-expression with the proper syntax. All parentheses are assumed to
    be wrappers for negative numbers and NOT another sub-expression.

    ===================================================================================================================
    It is important to understand that this method can't possibly be reached until we have gone as far into the
    expression as possible and the evaluation method has identified that any parentheses remaining are not
    sub-expressions but are in stead housing negative numbers!
    ===================================================================================================================


    Returns:
    A double that is the result of the operations defined in the sub-expression.

    Step One:   Determine if any true operators remain. Create a boolean value to correspond with this.
                If not skip directly to final step.
                True operators are all operators. However a negative is not a true operator if it meets the criteria
                laid out above. We will do this with regex.
    Step Two:   Assuming there is a true operator, we create a variable to represent the current operator value and the
                highest operator value. Then we iterate through the string and stop when we reach the end.
                Before we assign a '-' as the highest operator we simply need to to a quick check to see if it is a
                true operator.
    Step Three: Once the true operator is found, we create two integer variables upperBound and lowerBound. These will
                contain the index of the beginning and the end of the target operation.
                To find the correct upper and lower bounds, we evaluate to the left from the index of the true operator,
                we stop when we reach another true operator, or the beginning of the string.
                Then we evaluate to the right and stop when we reach the next true operator or the end of the string.
    Step Four:  Once the sub-operation is found, we replace it with the result of the operation. We set the index back
                to zero so we can begin evaluating the expression again.
    Step Five:  Once this step is reached it is assumed that the only thing remaining in the string is a single double
                value. We can simply parse the double from the string and return it.
     */
    public static double parseSubExpression(String subExpression)
    {
        subExpression = deleteParentheses(subExpression);
        //subExpression = deleteParentheses(subExpression);
        double result = 0;
        //Step One

        int index = 0;
        StringBuffer bufferSubExpression = new StringBuffer(subExpression);

        /*

        Pattern p = Pattern.compile("[\\*\\+\\^\\/]|[0-9]\\-[0-9]");
        Matcher m = p.matcher(bufferSubExpression);
        boolean trueExpressionExists = m.find();
        */

        //Step Two
        //We're gonna make this a method called findTrueOperator()
        /*
        The assumption here is that there is always at least one true operator. It is highly likely that there always
        is one. If not the loop is entered and exited.
         */
        while(findTrueOperator(bufferSubExpression.toString()) != -1)
        {
            index = findTrueOperator(bufferSubExpression.toString());
            System.out.println(index);
            //This means a true operator was found.
            if(index != -1)
            {
                //Step Three
                int lowerBound = 0;
                int upperBound = bufferSubExpression.length();
                int tempIndex = index;
                //We scan left and right looking for a true operator to set the upper and lower bounds.
                //TODO Brainstorm how to effectively identify the upper and lower bounds for the sub-operation!
                //Scan left
                index--;
                boolean operationFound = false;
                boolean numberFound = false;
                while(index >= 0 && !operationFound)
                {
                    char c = bufferSubExpression.charAt(index);
                    System.out.println(c);
                    if (c >= '0' && c <= '9')
                        numberFound = true;
                    switch (c)
                    {
                        case '^':
                        case '*':
                        case '/':
                        case '+':
                           lowerBound = index+1;
                           operationFound = true;
                            break;
                        case '-':
                            if(negativeTest(bufferSubExpression.toString(), index))
                            {
                                //I think we need to move this up 1
                                lowerBound = index+1;
                                operationFound = true;
                            }
                            break;
                    }
                    index--;
                }

                index = tempIndex;
                /*
                WE ARE STILL HAVING SOME ISSUE SCANNING RIGHT! WHEN THERE IS A DOUBLE NEGATIVE
                 */
                //Scan right
                index++;
                operationFound = false;
                numberFound = false;
                while(index < bufferSubExpression.length() && !operationFound)
                {
                    char c = bufferSubExpression.charAt(index);
                    if (c >= '0' && c <= '9')
                        numberFound = true;

                    switch (c)
                    {
                        case '^':
                        case '*':
                        case '/':
                        case '+':
                            upperBound = index;
                            operationFound = true;
                            break;
                        case '-':
                            if(negativeTest(bufferSubExpression.toString(), index))
                            {
                                upperBound = index;
                                operationFound = true;
                            }
                            break;

                    }
                    index++;
                }
                index = tempIndex;
                System.out.println("(" + lowerBound + "," + upperBound + ")");
                //Step Four
                //Step four we replace the string now that we have the upper and lower bounds.
                System.out.println("Before: " + bufferSubExpression);
                System.out.println("Target Operation: "+ bufferSubExpression.substring(lowerBound, upperBound));
                String tempS = bufferSubExpression.toString();
                bufferSubExpression.delete(lowerBound, upperBound);
                bufferSubExpression.insert(lowerBound, parseOperation(tempS.substring(lowerBound,upperBound)));
                System.out.println("After: " + bufferSubExpression);
                //Not sure if this code is needed yet.
                /*
                m = p.matcher(bufferSubExpression);
                trueExpressionExists = m.find();

                index++;
                if (trueExpressionExists) {
                    index = 0;
                }
                 */
            }



        }
        //Step Five
        result = parseDouble(bufferSubExpression.toString());
        return result;
    }

    public static String deleteParentheses(String theExpression)
    {
        theExpression = theExpression.replaceAll("[\\(]|[\\)]", "");


        return theExpression;
    }


    /**
     *
     * @param subExpression
     * @return
     */
    public static int findTrueOperator(String subExpression) {

        int index = 0;
        int currentOpVal = -1;
        int highestOpVal = -1;
        int operatorIndex = -1;
        while (index < subExpression.length()) {
            switch (subExpression.charAt(index)) {
                case '^':
                    currentOpVal = 3;
                    break;
                case '*':
                case '/':
                    currentOpVal = 2;
                    break;
                case '+':
                    currentOpVal = 1;
                    break;
                case '-':
                    if(negativeTest(subExpression, index))
                        currentOpVal = 1;
                    break;
            }

            if (currentOpVal > highestOpVal) {
                highestOpVal = currentOpVal;
                operatorIndex = index;
            }else index++;

        }
        if(highestOpVal == -1)
            operatorIndex = -1;
        else System.out.println("Target Operator: " + subExpression.charAt(operatorIndex));
        return operatorIndex;
    }

    /*
        We will call this little helper method negativeTest
        It will return a boolean true or false. It has two arguments, the subExpression to evaluate, and
        the index of the negative number. It will be helpful to quickly check if a given '-' operator is a true
        operator throughout the steps of this program.
     */
    public static boolean negativeTest(String subExpression, int index)
    {

        boolean trueOperator = false;
        if (index != 0) {
            //System.out.println(subExpression.substring(index - 1, index + 2));
            Pattern testP = Pattern.compile("[0-9]\\-[0-9]|[0-9]\\-[(]|[)]\\-[0-9]|[0-9]\\-\\-");
            //System.out.println("Negative Test On: " + subExpression.substring(index - 1, index + 2));
            Matcher testM = testP.matcher(subExpression.substring(index - 1, index + 2));
            if (testM.find()) {
                trueOperator = true;
            }
        }


        return trueOperator;
    }


    /*
    FINALLY!
    Now we need to implement the recursion. We parse the main expression with recursion, we keep doing this until we
    reach a single value
    We will call this method evaluate().

    First let us lay out the assumptions.
    Assumptions:
    The expression MUST have correct syntax as laid out in the API.
    Any parenthesis that do NOT house an expression are to be ignored! (Wait or do they have to be ignored?)


    When we reach a parenthesis, we do the following:
    Identify the index of the upper and lower bounds of the parenthesis.
    create a temp copy of the string
    REMOVE the expression in between the bounds
    REMOVE the parentheses
    Call recursion on the subExpression and put the result at the index of the LOWER BOUNDS
    =================================================================================
    The above section is the recursion phase. The sentinel for this phase is that there are no more remaining true
    operations in the sub-expression.

    Before we get to that we have to go on to phase two:
    The assumption at this point is that any parentheses that are present at this point DO NOT represent a sub-expression
    With this assumption satisfied, we simply call and return parseSubOperation of the string.

    This repeats until we go as deep into the expression as we possibly can. Working from the inner most expression
    outwards.

    Step One:   We iterate through the expression and stop at a parenthesis.
                We need to identify weather this parentheses is housing
     */
    public static double evaluate(String theExpression)
    {
        double result = 0;
        StringBuffer bufferExpression = new StringBuffer(theExpression);
        //Step One
        int index = 0;
        int pcount = 0;
        int lowerBound = 0;
        int upperBound = bufferExpression.length();
        boolean lowerFound = false;
        boolean upperFound = false;
        while(hasParentheses(bufferExpression.toString()))
        {
            for(int i = 0; i < bufferExpression.length(); i++)
            {
                //System.out.println(e.charAt(i));
                int j = 0;
                if (bufferExpression.charAt(i) == '(') {
                    //Okay we need to partition, now we need to find the index of the matching parenthesis.
                    lowerBound = i;
                    j = i+1;
                    int pCount = 1;
                    while (pCount != 0) {


                        if (bufferExpression.charAt(j) == '(')
                            pCount++;
                        if (bufferExpression.charAt(j) == ')')
                            pCount--;

                        if (pCount == 0) {
                            //System.out.println("deleting");
                            upperBound = j + 1;
                        } else j++;
                        //System.out.println("Loop: " + j +"\npCount: " + pCount);
                    }
                }
            }


            String temp = bufferExpression.toString();
            bufferExpression = bufferExpression.delete(lowerBound,upperBound);
            bufferExpression.insert(lowerBound, "" + evaluate(temp.substring(lowerBound+1, upperBound-1)));
        }




        //By this step we assume there are no more parenthesis that contain a sub-expression.
        result = parseSubExpression(bufferExpression.toString());
        System.out.println("RESULT: " + bufferExpression.toString());
        return result;
    }

    //Work on this later
    public static boolean hasParentheses(String theExpression)
    {
        Pattern p = Pattern.compile("[\\(]|[\\)]");
        Matcher m = p.matcher(theExpression);

        return m.find();
    }

    public static void main(String args[])
    {
        /*
        SOLVED!
        Problem statement: It seems as if the parseSubExpression method is not correctly identifying
        the correct target operation every time. I need to re-evaluate the logic in that step.
        Start by breaking down what the components of a single operation are. Then I need to
        evaluate how to properly identify when we have found our operation.

        We need to start by listing the assumptions I am making
        Assumptions:
        The sub-expression does not contain invalid characters.
        The sub-expression only contains parentheses wrapping a negative number.

        Obeservations:
        It seems as if two things are happening.
        Firstly, the incorrect operation is being displayed in the target operation printout.
        The printout is also incomplete meaning something is wrong with the evaluation of the lower and upper
        bounds of the expression. Write out this logic on paper so I can better understand what is going on here.
         */


        /*
        So subExpression is not identifying the proper segment to evaluate!!
        TODO: FIX THAT^^^^
         */

        //System.out.println(hasParentheses("2212354"));
        System.out.println(evaluate("(2+4)-(1+1)^2-3-2+4"));
        char c = '4';



    }
}