import java.util.Vector;

public class Analyse
{
    public static Element[] parseExpression(String pExpr) throws Exception
    {
        // First, check expression is valid
        if (checkExpression(pExpr) == false)
            throw new Exception("Expression is not valid");
        // Our vector of inner expressions
        Vector<Element> element = new Vector<Element>();
        // Flag to tell loop when to stop processing
        boolean continueProcessing;
        do
        {
            // Get our left and right () positions
            int posLeft = getInnermostNesting(pExpr);
            int posRight = getNextRightBracket(posLeft, pExpr);
            // If our left position is zero, abort loop
            continueProcessing = (posLeft != 0);
            // Retrieve value of inner expression
            String innerExpr = pExpr.substring(posLeft, posRight + 1);
            // Create a new element object for us
            Element currentElement = new Element(Element.getHighestChar(), innerExpr);
            // Save it...
            element.addElement(currentElement);
            // Replace our old expression with our new one
            pExpr = pExpr.substring(0, posLeft) + currentElement.getChar() + pExpr.substring(posRight + 1);
            // Display messages
        } while(continueProcessing);
        // Perform second-stage processing
        // We need to bracketify expressions with multiple operators
        for(int i=0; i<element.size(); i++)
        {
            String currentExpr = ((Element)element.elementAt(i)).getValue();
            int posFirst = getNextOperator(0, currentExpr);
            int posNext = getNextOperator(posFirst+1, currentExpr);
            if (posNext != 0)
            {
                System.out.println(posFirst + "\t" + ((Element)element.elementAt(i)).getValue());
                System.out.println(posNext + "\t" + ((Element)element.elementAt(i)).getValue());
            }
        }



        // Init our return array



        Element[] tempArray = new Element[element.size()];
        // Copy vector entries to array
        for(int i=0; i<element.size(); i++)
            tempArray[i] = (Element)element.elementAt(i);
        // Return
        return tempArray;
    }


    private static boolean checkExpression(String pExpr)
    {
        // Performs some basic sanity checking on the expression
        // Namely, checks there are no invalid characters and the number
        // of parenthesis match
        int depth = 0;
        for(int i=0; i<pExpr.length(); i++)
        {
            // Extract current character
            char currentChar = pExpr.charAt(i);
            // Check char is allowed
            if (isValidChar(currentChar) == false)
                return false;
            // Inc, dec, depth
            if (currentChar == '(')
                depth++;
            if (currentChar == ')')
                depth--;
            // Check to see whether we ever go -1 in brackets
            // ie )))(((
            if (depth < 0) return false;
        }
        // Check to see whether number of ( is same as number of )
        return (depth == 0);
    }

    private static boolean isValidChar(char pChar)
    {
        // Is this character allowed in an expression?
        // Digits
        if ((pChar == '0') || (pChar == '1') || (pChar == '2') || (pChar == '3')
            || (pChar == '4') || (pChar == '5') || (pChar == '6')
            || (pChar == '7') || (pChar == '8') || (pChar == '9')) return true;
        // Operators
        if ((pChar == '+') || (pChar == '-') || (pChar == '*') || (pChar == '/')
            || (pChar == '%') || (pChar == '^')) return true;
        // Other
        if ((pChar == '.') || (pChar == '(') || (pChar == ')')) return true;
        // Otherwise...
        System.out.println(pChar);
        return false;
    }

    private static boolean isCharOperator(char pChar)
    {
        // Checks to see whether a character is an operator
        return ((pChar == '+') || (pChar == '-') || (pChar == '*') || (pChar == '/') || (pChar == '%') || (pChar == '^'));
    }

    private static int getInnermostNesting(String pExpr)
    {
        // Returns the inner-most nested expression
        // First we need to see how many ( are present
        int depth = 0, highestDepth = 0, highestDepthPos = 0;
        // Loop through AGAIN
        for(int i=0; i<pExpr.length(); i++)
        {
            // If we find a ( , inc depth
            // If depth is currently highest, save current position
            if (pExpr.charAt(i) == '(')
            {
                depth++;
                if (depth > highestDepth)
                {
                    highestDepth = depth;
                    highestDepthPos = i;
                }
            }
            // If it's (, dec depth
            if (pExpr.charAt(i) == ')')
                depth --;
        }
        return highestDepthPos;
    }

    private static int getNextRightBracket(int pStart, String pExpr)
    {
        // This returns the position of the next right bracket after pStart
        for(int i=pStart; i<pExpr.length(); i++)
            if (pExpr.charAt(i) == ')') return i;
        return 0;
    }

    private static int getNextOperator(int pStart, String pExpr)
    {
        for(int i=pStart; i<pExpr.length(); i++)
            if (isCharOperator(pExpr.charAt(i))) return i;
        return 0;
    }
}