/*
 * Expressions.java
 *
 * Version:
 *     $Id$
 *
 * Revisions:
 *     $Log$
 */ 

import java.util.Random;
import java.util.Scanner;

/**
 * An application that allows people to practice calculating
 * simple Java expressions with precedence.
 *
 */
public class Expressions {

  // set up the numbers used in expressions
  // number of segments should always be odd
  private final static int MAX_SEGMENTS = 9;
  private final static int MINIMUM_NUMBER_RANGE = 0;
  private final static int MAXIMUM_NUMBER_RANGE = 9;

  //Display options
  private final static int CONTINUE=0, EXPRESSION=1, RESULT=2, SCORE=3, END=4;


  //Set up score and timer
  private int score = 0;
  private long startTime=0, totalTime=0;


  // variables for the data input
  private Scanner input = new Scanner( System.in );


  // random will be able to choose things randomly for us for the expressions
  private Random random = new Random();

  // Variables used in the program
  private String expression;
  private String result = "0";

  /**
   * The main program.
   *
   * @param    args    command line arguments (ignored)
   */
  public static void main( String[] args ) {
    Expressions expressions = new Expressions();
    expressions.runGame(); 
  }

  /**
   * In order to start a sequence of expressions this method must
   * be called.
   *
   */
  public void runGame( ) {
     boolean done = false;
     startTime = System.currentTimeMillis();
 
    while( !done ) {
      if (!done ) {
	  expression = makeExpression();
	  display( EXPRESSION );
	  result = solveExpression( expression );
	  String userResult = getUserInput();

        if (userResult.matches(result)) {
          score += 10;
        }

	  // always display the correct result in the end
	  display( RESULT );

      }

      display( CONTINUE );

      // we see if we want to go again
      done = wantToQuit();
    }

    // print out completed information
    display( END );
   }

  //Prints output based on the type of text that needs to be displayed
  private void display( int typeToDisplay ) {

    totalTime = (System.currentTimeMillis() - startTime) / 1000;

    switch(typeToDisplay){
      case 0:
        System.out.println();
        System.out.println("--------------------------------------------------------------------");
        System.out.print("Type a 'q' to quit or any other key to continue: ");
        break;
      case 1:
        System.out.println();
        System.out.println("--------------------------------------------------------------------");
        System.out.println( "Calculate the value of the following expression: " + 
		           expression);
        break;
      case 2:
        System.out.println();
        System.out.println("The answer is: " + result );
        System.out.println("Your score is: " + score + " points in " + totalTime + " seconds.");
        break;
      case 3:
        break;
      case 4:
        System.out.println();
        System.out.println("--------------------------------------------------------------------");
        System.out.println("FINAL SCORE: " + score + " points in " + totalTime + " seconds.");
        System.out.println("--------------------------------------------------------------------");
        break;
    }
  }

  /**
   * A simple routine to get input from the user.
   *
   * @return The answer to an expression. Should be numeric.
   */
  private String getUserInput( ) {
    System.out.print("Enter your answer: ");
    
    return(input.nextLine());
  }

  /** 
   * @return True if the user hits the 'q' key to quit and false otherwise.
   */
  private boolean wantToQuit() {    
    return( input.nextLine().equalsIgnoreCase("q") );
  }

  /**
   * A method that makes expressions of a certain length with certain predefined
   * operators from a range of integer numbers.
   *
   * @return An expression in string form without spaces separating elements.
   */
  public String makeExpression( ) {
    // We use a stringbuffer as string will keep making new objects if we change it whereas
    // stringbuffer allows us to append new characters onto the end of it.
    StringBuffer segments = new StringBuffer("");

    // we keep a count of where we are so we know when to put in operators vs. numbers.
    int currentSegment = 0;

    int segmentsForThisExpression = random.nextInt( MAX_SEGMENTS-3 ) +3;
    if (segmentsForThisExpression % 2 == 0 ) {
      segmentsForThisExpression++;
    }

    // We're not going to handle creating divIndex by zero situations in here.
    // They will be handled by those that solve the equation.

    while ( currentSegment < segmentsForThisExpression ) {
      if ( currentSegment % 2 == 1 ) {
	// for statements that must take two arguments, odd numbers are always operators
	// we're only going to put the '-' sign in as a unary operator when
	// we're generating numbers
	int operator = random.nextInt( 5 );
	String nextOperator = "*";
	switch( operator ) {
	  case 1: nextOperator = "/";
	    break;
	  case 2: nextOperator = "%";
	    break;
	  case 3: nextOperator = "+";
	    break;
	  case 4: nextOperator = "-";
	    break;
	}
	segments.append( nextOperator );
      } else {
	// The "" is there to turn the whole expression into a string automagically for us rather
	// than a number type.
	String nextNumber = "" + 
	  ( random.nextInt( MAXIMUM_NUMBER_RANGE + Math.abs(MINIMUM_NUMBER_RANGE) ) - Math.abs(MINIMUM_NUMBER_RANGE) );
	segments.append( nextNumber );
      }
      currentSegment++;
    }

     return segments.toString();
    
  }

  /**
   * Solves an expression of arbitrary size that consists of operators that take two arguments.
   * The one operator that doesn't take two operators is the unary "-" operator to indicate
   * a negative number. Precedence is taken into account in solving the problem. Special consideration
   * is given to equations that are undefined (ex. divide by zero). 
   *
   * @return A string representing the solution to the expression. If there is a divide by zero in the
   *         expression then the string will say "undefined".
   */
public String solveExpression( String expression ) {

	boolean done = false;
	// The current string keeps our working version of the answer.
	String current = expression;

	// The current and eventually final numerical answer.
	int result = 0;

	// The index of the next operator we have to consider. Default is 0 which will mean we
	// haven't found a real operator since all real operators need arguments on both sides of them.
	int minimumIndex = -1;
	int middle = -1;

	int left = -1;
	int right = -1;

	// while we're not done solving...
	while ( !done ) {
		
          middle = -1;
	  if ( current.contains( "*" ) || current.contains( "/" ) || current.contains( "%" )  ){

            // get the index in the string of the first occurence of these operators since java will do them
            // from left to right
            int multIndex = current.indexOf("*");
            int divIndex = current.indexOf("/");
            int modIndex = current.indexOf("%");

            // if there's a valid index for mult then pick it else take a valid index for div else take one for mod.
            middle = (multIndex != -1) ? multIndex : ( (divIndex != -1) ? divIndex : ( (modIndex != -1) ? modIndex : -1 ) ) ;

            // Let's make sure we have a valid index before going further...
            if (middle != -1) {
              // One of the indices is valid so let's make sure it's the first
              if (modIndex > -1 && multIndex > -1 && divIndex > -1) {
                  middle = Math.min(Math.min(modIndex,divIndex),multIndex);
              }
              else if ( divIndex > -1 && multIndex > -1 ) {
                  middle = Math.min(multIndex,divIndex);
              }
              else if ( modIndex > -1 && multIndex > -1 ) {
                  middle = Math.min(multIndex,modIndex);
              } 
              else if ( modIndex > -1 && divIndex > -1 ) {
                  middle = Math.min(divIndex,modIndex);
              }

              // Now perform arithmetic and check to make sure we're not dividing or mod'ing by 0
              if ( current.charAt( middle ) == '*' ) {
                left = getNumberAt(current, middle - 1);
                right = getNumberAt(current, middle + 1);
                result = left * right;
              } else if ( current.charAt( middle ) == '/' ) {
                left = getNumberAt(current, middle - 1);
                right = getNumberAt(current, middle + 1);

                // since divide by 0 is normally an error condition we're going to return
                // in the middle of the method
                if (right == 0) {
                  return "undefined";
                }

                result = left / right;

              } else if ( current.charAt( middle ) == '%' ) {
                left = getNumberAt(current, middle - 1);
                right = getNumberAt(current, middle + 1);
                // since divide/mod by 0 is normally an error condition we're going to return
                // in the middle of the method
                if (right == 0) {
                  return "undefined";
                }
                result = left % right;
              }
            }

            
	  
          } 
	  else if (current.contains( "+" ) || current.contains( "-" )){
            // next precedence
            int a = current.indexOf("+");
            int b = getFirstSubtractionIndex(current);
            middle = a;

            //NOTE: HELP ON THE MINS IN THIS SECTION WAS OBTAINED FROM GOOSE AND ADAM
            if (a > -1 && b > -1 ) {
              middle = Math.min(a,b);
            }
            else if ( b > -1 ) {
              middle = b;
            }

            if (middle != -1) {
              if ( current.charAt( middle ) == '+' ) {
                left = getNumberAt(current, middle - 1);
                right = getNumberAt(current, middle + 1);
                result = left + right;
              } else if ( current.charAt( middle ) == '-' ) {
                left = getNumberAt(current, middle - 1);
                right = getNumberAt(current, middle + 1);
                result = left - right;
              }
            }

			
	  } 
	  minimumIndex = middle;
          int leftSide = left;
	  int rightSide = right;
	  if (minimumIndex >= 1) {
	    int rightSize = new Integer(rightSide).toString().length();
	    int leftSize = new Integer(leftSide).toString().length();

	    if (minimumIndex-leftSize != 0 && minimumIndex+rightSize!=current.length()-1) {
	      current = current.substring(0, minimumIndex- leftSize ) + result  + 
		current.substring(minimumIndex + rightSize+1, current.length()); 
	    } else if (minimumIndex-leftSize != 0 ) {
	      current = current.substring(0, minimumIndex-leftSize) + result ;
	    } else if (minimumIndex+rightSize!=current.length()-1) {
	      current = result + 
		current.substring(minimumIndex +rightSize+1, current.length()); 
	    } else {
	      current = result + "";
	    }
	  }
	  
	  if (current.length() <= 1 || minimumIndex == -1 ) {
	    done = true;
	  }
	  minimumIndex = -1;
	  
	}

	return ""+result;
  }

  /**
   * Returns a number that has an element in index value. The number may
   * extend after or before the index chosen.
   *
   * @param expression The expression to get a number from.
   * @param index The index of a piece of the number.
   * @return The actual number obtained from the numeric pieces around and inside of index or
   *         0 if there was a problem with the expression and index given.
   */
  public int getNumberAt( String expression, int index ) {
    
    int number =  0;
    int startIndex = index;
    int endIndex = index;

    try {
      // find the start of the number
      for (int i=index; i>=0; i--) {
	char current = expression.charAt( i );
	if ( Character.isDigit( current ) ) {
	  startIndex = i;
	} else if (current == '-' && isUnary( expression, i ) ) {
	  startIndex = i;
	  break;
	} else {
	  break;
	}
      }

      // make sure we skip over unary op's at the beginning of a number 
      // in order to get to the end of it
      if ( expression.charAt(index) == '-' && isUnary( expression, index ) ) {
	index++;
      }

      // find the end of the number
      for (int i=index; i<expression.length(); i++) {
	if ( Character.isDigit( expression.charAt( i ) ) ) {
	  endIndex = i;
	} else {
	  break;
	}
      }

      // now pass the whole number to be parsed out by the Integer class
      number = Integer.parseInt( expression.substring(startIndex, endIndex+1) );
  
    } catch (NumberFormatException e) {
    }
    
    return number;
  }

  /**
   * This method exists since a '-' sign can be part of an actual expression or can
   * just be a unary minus sign indicating the sign of a numeric value.
   *
   * @param expression The expression to look for an index in.
   * @return The value of the zero-based index or -1 if none were found.
   */
  private int getFirstSubtractionIndex( String expression ) {
    // First we make a copy of the string soas not to change it.
    StringBuffer current = new StringBuffer( expression );

    // Get the index of the first '-' sign.
    int index = current.indexOf("-");
    
    // we have an index so check whether or not it's unary and if it is then
    // nullify it and look for another '-'
    if (index != -1) {
      while ( (index != -1) && isUnary( current.toString(), index ) ) {
	current.setCharAt(index, 'x');
	index =  current.indexOf("-");
      }
    }

    return index; 
  }

  /**
   * An index value is a unary '-' if it's the first in an expression,
   * or if there is an operator in front of it. The passed index
   * is assumed to be the index of the '-' sign to check and the
   * expression must be a valid expression.
   *
   * @return true if the '-' sign is unary and false otherwise.
   */
  private boolean isUnary( String expression, int index ) {

    boolean unary = false;

    if ( index == 0) {
      unary = true;
    } else {
      String valueBefore = expression.substring( index-1, index );
      for (int i =0; i< 5; i++) {
	if ( valueBefore.equals( "*" ) ||valueBefore.equals( "%" ) ||valueBefore.equals( "/" ) ||
	     valueBefore.equals( "+" ) ||valueBefore.equals( "-" ) ) {
	  unary = true;
	  break;
	}
      }
    }

    return unary;
  }

  /** 
   * 
   * @return True if the character is a number and false otherwise.
   */
  private boolean isNumber( char numberPiece ) {
    return (numberPiece == '0' || numberPiece == '1' || numberPiece == '2' || numberPiece == '3' ||
	numberPiece == '4' || numberPiece == '5' || numberPiece == '6' || numberPiece == '7' ||
	    numberPiece == '8' || numberPiece == '9' );
  }
}