/**
 * A parser for simple arithmetic expressions with
 * the operators +, -, *, / and ( )
 *
 * It was written as a demonstration of a recursive
 * descent parser, therefore the emphasis is on
 * simplicity.
 *
 * @author <a href="http://www.heimetli.ch/te.html">P. Tellenbach</a>
 * @version 16. Dec. 2007
 */
public class Parser
{
  /** String to be parsed */
  protected String str ;

  /** Current position in the string */
  protected int position ;

  /**
   * Parses a "term", which is a production with
   * the operators "*" or "/"
   * @throws ParseException thrown by parseFactor
   */
  protected Node parseTerm() throws ParseException
  {
     // Parse factor to the left of the operator
     Node result = parseFactor() ;

     // While there are term operators in the string
     while( (position < str.length()) && ((str.charAt(position) == '*') || (str.charAt(position) == '/')) )
     {
        // Create a new node with the operator
        Node node = new Node( str.substring(position,position+1) ) ;
        ++position ;

        // Set the previus node as the left subtree
        node.setLeft( result ) ;

        // Set the factor to the right of the operator as the right subtree
        node.setRight( parseFactor() ) ;
        result = node ;
     }

     return result ;
  }

  /**
   * Parses a "factor", which is either an expression enclosed
   * by "(" and ")" or a simple number.
   * Note the recursion via parseExpression.
   * @throws ParseException if the expression is not terminated by ")"
   */
  protected Node parseFactor() throws ParseException
  {
     if( (position < str.length()) && (str.charAt(position) == '(') )
     {
        ++position ;

        Node result = parseExpression() ;

        if( (position == str.length()) || (str.charAt(position) != ')') )
           throw new ParseException( "Missing ')'" ) ;

        ++position ;

        return result ;
     }

     return parseNumber() ;
  }

  /**
   * Parses an "expression", which is a production with
   * the operators + and -
   * @throws ParseException thrown by parseTerm
   */
  protected Node parseExpression() throws ParseException
  {
     Node result = parseTerm() ;
   
     while( (position < str.length()) && ((str.charAt(position) == '+') || (str.charAt(position) == '-')) )
     {
        Node node = new Node( str.substring(position,position+1) ) ;
        ++position ;

        node.setLeft( result ) ;
        node.setRight( parseTerm() ) ;
        result = node ;
     }

     return result ;
  }

  /**
   * Returns an integer number from the string
   * @throws ParseException if the number is not valid
   */
  protected Node parseNumber() throws ParseException
  {
     int start = position ;

     while( (position < str.length()) && (str.charAt(position) >= '0') && (str.charAt(position) <= '9') )
        ++position ;

     if( position == start )
        throw new ParseException( "Number expected" ) ;

     return new Node( str.substring(start,position) ) ;
  }

  /**
   * Sets up the members, starts the parser and checks if
   * the whole string was parsed correctly.
   * Note that the string to be parsed may not contain whitespace.
   * @throws ParseException if there are any unparsed characters
   */
  public Node parse( String expr ) throws ParseException
  {
     str         = expr ;
     position       = 0 ;

     Node result = parseExpression() ;     

     if( position != str.length() )
        throw new ParseException( "Invalid expression" ) ;

     return result ;
  }
}