package A1;

import java.util.InputMismatchException;
import java.util.Scanner;

/**
    This class contains an <code>evaluate</code> method that evaluates
    boolean expressions represented as <code>String</code>s, provided
    that they are legal expressions with respect to the language defined 
    by the grammar given below.  If not, the method will throw an
    <code>InputMismatchException</code> that contains an appropriate
    error message. 
    
    The program representation is as a string of tokens separated
    by whitespace characters as recognized by the 
    <code>Character.isWhitespace</code> predicate.
    
    There is no explicit constructor; the default constructor is sufficient.
          
    The grammar for boolean expressions has start symbol &lt;expr&gt; and productions <pre>
    &lt;expr&gt; ::= &lt;operand&gt; | ~&lt;expr&gt; | ( &lt;expr&gt; &lt;operator&gt; &lt;expr&gt; )
    &lt;operator&gt; ::= ^ | v 
    &lt;operand&gt; ::= T | F | true | false</pre>
    
    Note that recursive descent parsing is appropriate for this grammar. 
 */


public class Interpreter
{

	
  // used to divide the program into tokens 
  //   and to retrieve the next token
  private Scanner tokenizer;
  
  // the next unprocessed token of the program
  private String lookahead;

  
  /**
      Instances of this class represent syntax trees (analogs
      of parse trees that are used for expression evaluation).  
      Their methods are abstract, since different subclasses
      are used for leaves and nonleaves.
   */
  
  private abstract class ExprTree
  {
    abstract public boolean evaluate();
    abstract public String getOperator();
    abstract protected String toString(String str);
  }  // end ExprTree class
  
  
  /**
     Instances of this class represent syntax trees with single
     nodes representing operands.
  */
 
  private class ExprLeaf extends ExprTree
  {
    
    // the value of the operand
    private boolean value;
    
    /**
        This constructor takes a token and constructs a
          corresponding syntax tree of one node. 
       @param token one of the four legal operand tokens permitted
          by the current grammar (T, F, true, false).  Illegal
          operand tokens are given the value <code>false</code>.
     */
    
    public ExprLeaf(String token)                         {
      if (token.equals("T") || token.equals("true"))
        value = true;
      else 
        value = false;                                    }
    
    
    /**
        @return the value of the syntax tree
     */
    
    public boolean evaluate()                             {
      return value;                                       }
    


    /**
        @return a dummy value for the tree's top-level operator,
          since trees of 1 node have no operators.
     */
    
    public String getOperator()                           {
      return null;                                        }

   
    // overrides inherited method 

    public String toString()                              {
      return Boolean.toString(value);                     }
    
    
    public String toString(String indent)                 {
      return indent + value;                              }

  } // end ExprLeaf class
    
  
  
  /**
     Instances of this class represent syntax trees with 
       more than one node.  Roots represent operators,
       and children represent operands.  Operators may
       be unary or binary.  Unary operators are assumed 
       to have null second children.  Currently the only
       operators supported are the logical operators 
       <code>~</code>, <code>^</code>, and <code>v</code>.   
  */

  private class ExprInternalNode extends ExprTree         
  {
     // the top-level operator
     private String operator;
     
     // the first operand
     private ExprTree firstChild;
     
     // the second operand (null for a unary operator)
     private ExprTree secondChild;
     
     
     /**
         A constructor that takes as arguments the three desired components
           of the new tree
         @param op the top-level operator, represented as a <code>String</code>
         @param first the first operand
         @param second the second operand
      */
     
     public ExprInternalNode(String op, ExprTree first, ExprTree second) {
       operator = op;
       firstChild = first;
       secondChild = second;                                             }
     
     
     /**
         @return the boolean value obtained by evaluating the tree 
         @throws InputMismatchException if an illegal operator is present
      */
     // The evaluation algorithm is straightforward recursive evaluation,
     //   equivalent to a postorder traversal
     
     public boolean evaluate()                                           {
       if (operator.equals("~"))
         return !firstChild.evaluate();
       else if (operator.equals("^"))
         return (firstChild.evaluate() && secondChild.evaluate());
       else if (operator.equals("v"))
         return (firstChild.evaluate() || secondChild.evaluate());
       else 
         throw new InputMismatchException(
            "illegal operand");                                          }
     
     
     /**
         @return the top-level operator token, represented as a string 
      */
     
     public String getOperator()                               {
       return operator;                                        }

     
     // overrides inherited method 

     public String toString()                               {
       return toString("");                                 }

     /**
         @param indent a string of spaces which is printed before the
          contents of the root.  That is, the length of this string 
          specifies how far the contents of the root are to be indented.
         @return a string representing the expression rooted at the node 
         The node contents are printed in preorder.  The contents of 
         each node is indented an amount proportional to its distance
         from the root.
      */
     /*
         The algorithm is the straightforward recursive one for preorder
         traversal, with a fixed-length string of spaces appended to the 
         parameter at each recursive call.
      */
       
     protected String toString(String indent)                         {
       StringBuffer outputBuffer = 
         new StringBuffer(indent);
       outputBuffer.append(operator);
       outputBuffer.append(System.getProperty("line.separator")); 
       outputBuffer.append(firstChild.toString(indent+"  "));
       if (secondChild != null)                                     {
         outputBuffer.append(System.getProperty("line.separator"));
         outputBuffer.append(secondChild.toString(indent+"  "));    }
       return new String(outputBuffer);                               }
     
   } // end ExprInternalNode class
    
  
  /**
      Evaluate a boolean expression consistent with the given grammar
      @param input the input string representing the expression
      @return the boolean value
      @throws InputMismatchException for ill-formed input strings
   */
  
  public boolean evaluate(String input)                       {
    return parse(input).evaluate();                           }
    

  /**
     Evaluate a boolean expression consistent with the given grammar,
       but print a traversal of the parse tree before returning
       the value.
     @param input the input string representing the expression
     @return the boolean value
     @throws InputMismatchException for ill-formed input strings
*/


  public boolean evaluateShowingTraversal(String input)       {
    ExprTree parseTree = parse(input);
    System.out.println(parseTree);
    return parseTree.evaluate();                              }
  
  
  /**
      Parse a string that is assumed to represent a boolean
        expression that can be generated by the given grammar
      @param input the input string  
      @return a syntax tree for the expression, represented as 
        an <code>ExprTree</code>  
      @throws InputMismatchException for ill-formed input strings
   */
   // The parsing algorithm is recursive descent.
   // A dummy symbol is appended to each input string so
   //   that lookahead never fails
   // The input string is entered into a tokenizer
   // This method is private, since the ExprTree class is??

  private ExprTree parse(String input)                            {
    if (input == null)
      throw new InputMismatchException(
        "input string cannot be null");
    tokenizer = new Scanner(input + " $");
    lookahead = tokenizer.next();    
    ExprTree result = parseExpr();
    tokenizer.close();
    if (!lookahead.equals("$"))
      throw new InputMismatchException(
        "symbols remain after end of expression");    
    return result;                                               }
  
  
  ///////////// The parsing methods for particular nonterminals ////////////////

  /**
     Parse a string that is assumed to be generable from the
       <code>&lt;expr&gt;</code> symbol in the given grammar
     The string is assumed to be a prefix of the contents 
       of the tokenizer.  After parsing, all tokens of the
       string will have been removed from the tokenizer.
     @return a syntax tree for the expression, represented as 
       an <code>ExprTree</code>  
     @throws InputMismatchException for ill-formed input strings
  */
  
  private ExprTree parseExpr()                                     {
      // try the second rule
    if (lookahead.equals("~"))                           {
      lookahead = tokenizer.next();   
      ExprTree child = parseExpr();
      return new ExprInternalNode("~", child, null);     }  
    
      // try the third rule
    else if (lookahead.equals("("))                      {
      lookahead = tokenizer.next();    
      ExprTree child1 = parseExpr();
      ExprTree operator = parseOperator();
      ExprTree child2 = parseExpr();
      if (lookahead.equals("$"))
        throw new InputMismatchException(
          "premature end of input -- ) expected");
      else if (!lookahead.equals(")"))
        throw new InputMismatchException(
          ") expected -- "  + lookahead + " found");         
      else 
        lookahead = tokenizer.next();   
      return new ExprInternalNode(
          operator.getOperator(), child1, child2);       }
    
    // try the first rule
    //   this method will check for premature end of input
    //   and illegal symbols
    else return parseOperand();                                    }  
 
    
  
  /**
     Parse a string that is assumed to be generable from the
       <code>&lt;operator&gt;</code> symbol in the given grammar
     The string is assumed to be a prefix of the contents 
       of the tokenizer.  After parsing, all tokens of the
       string will have been removed from the tokenizer.
     @return a syntax tree for the expression, represented as 
       an <code>ExprTree</code> with the operator in the root
       and null children 
     @throws InputMismatchException for ill-formed input strings
  */
  
  private ExprTree parseOperator()                                    {     
    if (lookahead.equals("^") || lookahead.equals("v"))           {  
      String operator = lookahead;
      lookahead = tokenizer.next();   
      return new ExprInternalNode(operator, null, null);          }
    else if (lookahead.equals("$"))
      throw new InputMismatchException(
        "premature end of input -- operator expected");
    else
      throw new InputMismatchException(
        "operator expected -- " + lookahead + " found");              }

  
  /**
     Parse a string that is assumed to be generable from the
       <code>&lt;operand&gt;</code> symbol in the given grammar
     The string is assumed to be a prefix of the contents 
       of the tokenizer.  After parsing, all tokens of the
       string will have been removed from the tokenizer.
     @return a syntax tree for the expression, represented as 
       an <code>ExprTree</code> that is a leaf 
     @throws InputMismatchException for ill-formed input strings
*/
    
  private ExprTree parseOperand()     {
    if (lookahead.equals("T") || lookahead.equals("true")
        || lookahead.equals("F") || lookahead.equals("false"))        {
      String operand = lookahead;
      lookahead = tokenizer.next();   
      return new ExprLeaf(operand);                                   }
    else if (lookahead.equals("$"))
      throw new InputMismatchException(
        "premature end of input at beginning of expression");
    else
      throw new InputMismatchException(
        "operand expected -- " + lookahead + " found");                  }
  
  

 }