package lab05;

public class ExpressionTree {
	
	ExpressionTree leftTerm = null;  // Tree for left operand
	ExpressionTree rightTerm = null; // Tree for right operand
	
	char operator = '#';  			 // the default operator, a node can take '+','-','*','/','^'  
	
	double numberTerm = Double.NaN;  // only used for leaf number nodes
	
	ExpressionTree( double number )
	{
		// leaf node only stores number term, no left or right terms
		numberTerm = number;
	}
	
	/*
	 * Operator precedence is not implemented, 
	 * input expression is assumed fully parenthesized.
	 */
	ExpressionTree( String parseString )
	{
		// Parse input string into left and right operands (we also call terms)
		
		parseString = parseString.replace(" ", ""); //remove whitespace
		
		int leftTermStartIndex = 0;
		int leftTermEndIndex;
		String leftString;
		
		int operatorIndex;
		
		if( parseString.charAt(leftTermStartIndex) == '(' )
		{
			// Left term is a parenthesized expression:
			  
			// closing parenthesis corresponding to first '(' gives end of first term. 
			leftTermEndIndex = getClosingParenthesisIndex(parseString);
			
			// The operator is character next to the closing parenthesis
			operatorIndex = leftTermEndIndex + 1;
			
			// Extract string between parenthesis EXCLUDING the first and last '(', ')' characters
			// NOTE: for substring(), endIndex is one character after the desired last index.
			leftString = 
				parseString.substring( leftTermStartIndex + 1, leftTermEndIndex );
			
			// Create a new ExpressionTree for leftString 
			leftTerm = new ExpressionTree(leftString);
		}
		else
		{
			// Left term is a number expression:
			// number string till first operator is the left term
			
			// Get index for leftmost operator
			operatorIndex = getOperatorIndex(parseString);
			
			// Number term ends one character before the operator.
			leftTermEndIndex = operatorIndex - 1;
			
			// Extract substring for the number term 
			// NOTE: for substring(), endIndex is one character after the desired last index.
			leftString = 
					parseString.substring( leftTermStartIndex, leftTermEndIndex + 1 );
			
			// Create a new ExpressionTree for leftString
			// NOTE: double constructor should be invoked since leftString is a number term.
			leftTerm = new ExpressionTree(Double.parseDouble(leftString));
		}
		
		if( operatorIndex == parseString.length() )
			// parseString is either a single parenthesis term or a single number.
			// This node is a '#' node with only leftTerm, no operator and no rightTerm,
			// hence simply return.
			return;
		
		// Extract the operator character at operatorIndex
		operator = parseString.charAt( operatorIndex );
		
		// Whatever is left after the operator is the right term
		String rightString = parseString.substring( operatorIndex + 1 );
		
		// Create new ExpressionTree with rightString
		rightTerm = new ExpressionTree( rightString );
	}
	
	
	/*
	 * Returns index of closing parenthesis corresponding to first
	 * character which should be '('.
	 * Algorithm: upcount '(' and downcount ')' till count is back to zero.
	 */
	int getClosingParenthesisIndex( String parseString )
	{
		int stringIndex = 1;
		int parenthesisCount = 1;  // First character is already a '('
		while( parenthesisCount != 0 )
		{
			if( parseString.charAt(stringIndex) == '(' )
				// Upcount for '('
				parenthesisCount++;
			else if ( parseString.charAt(stringIndex) == ')' )
				// Downcount for ')'
				parenthesisCount--;
			stringIndex++;
		}
		return stringIndex - 1;
	}
	
	// Return index of leftmost operator 
	int getOperatorIndex( String parseString )
	{
		int index = 0;
		while( index < parseString.length() &&
				( ( parseString.charAt(index) >= '0' &&
				  parseString.charAt(index) <= '9' ) || parseString.charAt(index) == '.' ) )
		{
			index++;
		}
		return index;
	}
	
	double evaluateExpression()
	{
		double leftValue = 0, rightValue = 0;
		
		if ( leftTerm == null )
			// no leftTerm subtree: use numberTerm instead 
			leftValue = numberTerm;
		else
			// leftTerm subtree present: evaluate left expression  
			leftValue = leftTerm.evaluateExpression();
	
		if ( rightTerm != null )
			// rightTerm subtree present: evaluate right expression
			rightValue = rightTerm.evaluateExpression();
		
		// Do the actual math.
		switch( operator )
		{
			case '+':
				return leftValue + rightValue;
			case '-':
				return leftValue - rightValue;
			case '*':
				return leftValue * rightValue;
			case '/':
				return leftValue / rightValue;
			case '^':
				return Math.pow(leftValue,rightValue);
			case '#':
			default:
				return leftValue;
		}
	}
}