// file:    LogicParser.java
// author:  Robert Keller
// purpose: Skeleton for logic parser program that shows how to read lines
//          as Strings, create a parser, and call the parse method.

import java.io.*;

/**
 * A LogicParser reads a proposition logic expression from a String
 * and returns a LogicTree representing the syntax of the expression.
 */

class LogicParser
{
/** char constants for various symbols */

static final char iffSymbol     = '=';
static final char impliesSymbol = '>';
static final char orSymbol      = '+';
static final char andSymbol     = '*';
static final char notSymbol     = '\'';
static final char lparenSymbol  = '(';
static final char rparenSymbol  = ')';
static final char zeroSymbol    = '0';
static final char oneSymbol     = '1';

/** int constants for various character categories */

static final int VARIABLE    = 0;
static final int CONSTANT    = 1;
static final int OPERATOR    = 2;
static final int LEFTPAREN   = 3;
static final int RIGHTPAREN  = 4;
static final int OTHER       = 5;

/** Names correspond to the above categories. */

String names[] = 	

    {"Variable", "Constant", "Operator", "LeftParen", "RightParen", "Other"};


/** 
 * Main program reads one line at a time and creates a parser for that line,
 * printing out the resulting tree
 */

public static void main(String arg[])
  {
  BufferedReader reader = new BufferedReader(new InputStreamReader(System.in));

  String expressionRead;  // The line of input read

  try
    {
    // Read the next line, continuing the loop only if not end-of-file.

    while( (expressionRead = reader.readLine()) != null )
      {
      // Create a parser for the line read.

      LogicParser parser = new LogicParser(expressionRead);


      // Parse the input.

      LogicTree tree = parser.parse();


      // Show the resulting tree.

      System.out.println("\nThe syntax tree for " + expressionRead + " is:");
      System.out.println(tree);
      }
    }
  catch( IOException e )
    {
    System.out.println("IOException caught: " + e);
    }
  }


/**
 * CharReader for the input String
 */

CharReader chars;


/**
 * Construct a LogicParser for a given input String.
 */

LogicParser(String input)
  {
  // Create a CharReader from the input string.

  chars = new CharReader(input);
  }


/**
 * The overal parse method; invokes the parse method E as the root
 * of the grammar.
 */

LogicTree parse()
  {
  // chars.setTrace(true);

  LogicTree result = E();

  if( ! result.isFailure() && chars.hasMore() )
    {
    return new Failure("garbage after valid input ", chars.toString());
    }
  else
    {
    return result;
    }
  }


/**
 * Parse method: Get an equality from the input.
 * The rule is E -> I [= I].
 */

 LogicTree E()
  {
  LogicTree result = I();	// Get first implication

  if( result.isFailure() )
    {
    return result;
    }

  if( chars.peek() == iffSymbol )
    {
    chars.get();
    LogicTree implication = I();
    if( implication.isFailure() )
      {
      return notFound("implication, sum, product, or literal", 
                      iffSymbol, 
                      ((Failure)implication).getResidual());
      }
    result = LogicTree.iff(result, implication);
    }

  return result;
  }


/**
 * Parse method: Get an implication from the input.
 * The rule is I -> S [> I].
 */

 LogicTree I()
  {
  LogicTree result = S();	// Get first literal.

  if( result.isFailure() )
    {
    return result;
    }

  if( chars.peek() == impliesSymbol )
    {
    chars.get();
    LogicTree implication = I();
    if( implication.isFailure() )
      {
      return notFound("implication, sum, product, or literal", 
                      impliesSymbol, 
                      ((Failure)implication).getResidual());
      }
    result = LogicTree.implies(result, implication);
    }

  return result;
  }


/**
 * Parse method: Get a sum from the input.
 * The rule is S -> P {+ P}.
 */

 LogicTree S()
  {
  LogicTree result = P();	// Get first literal.

  if( result.isFailure() )
    {
    return result;
    }

  while( chars.peek() == orSymbol )
    {
    chars.get();
    LogicTree product = P();
    if( product.isFailure() )
      {
      return notFound("product or literal", 
                      orSymbol, 
                      ((Failure)product).getResidual());
      }
    result = LogicTree.or(result, product);
    }

  return result;
  }


/**
 * Parse method: Get a product from the input.
 * The rule is P -> L {* L}.
 */

 LogicTree P()
  {
  LogicTree result = L();	// Get first literal.

  if( result.isFailure() )
    {
    return result;
    }

  while( chars.peek() == andSymbol )
    {
    chars.get();
    LogicTree literal = L();
    if( literal.isFailure() )
      {
      return notFound("literal", andSymbol, ((Failure)literal).getResidual());
      }
    result = LogicTree.and(result, literal);
    }

  return result;
  }


/**
 * Parse method: Get a literal from the input.
 * The rule is L -> U {'}.
 */

 LogicTree L()
  {
  LogicTree result = U();

  if( result.isFailure() )
    {
    return result;
    }

  while( chars.peek() == notSymbol )
    {
    chars.get();
    result = LogicTree.not(result);
    }

  return result;
  }


/**
 * Parse method: Get a unit from the input.
 * The rule is U -> V | C | ( E ), where V is a variable and C is
 * a constant.  Variables are single letters, upper or lower case.
 * Constants are 0 or 1.
 */

 LogicTree U()
  {
  switch( category(chars.peek()) )
    {
    case VARIABLE : return LogicTree.var(chars.get());

    case CONSTANT : 
      {
      switch( chars.get() )
        {
        case zeroSymbol: return LogicTree.C0;
        case oneSymbol:  return LogicTree.C1;
        }
      }

    case LEFTPAREN :
      {
      chars.get();
      LogicTree result = E();
      if( result.isFailure() ) return result;

      if( chars.peek() == rparenSymbol )
        {
        chars.get();
        return result;        
        }
      return notFound("right paren", chars.toString());
      }

    default: return notFound("variable, constant, or left paren", 
                             chars.toString());
    }
  }


/**
 * category determines an integer category indicator for any character.
 */

int category(char c)
  {
  switch( c )
    {
    case 'a' : case 'b': case 'c' : case 'd': case 'e': case 'f': case 'g':
    case 'h' : case 'i': case 'j' : case 'k': case 'l': case 'm': case 'n':
    case 'o' : case 'p': case 'q' : case 'r': case 's': case 't': case 'u':
    case 'v' : case 'w': case 'x' : case 'y': case 'z': 

    case 'A' : case 'B': case 'C' : case 'D': case 'E': case 'F': case 'G':
    case 'H' : case 'I': case 'J' : case 'K': case 'L': case 'M': case 'N':
    case 'O' : case 'P': case 'Q' : case 'R': case 'S': case 'T': case 'U':
    case 'V' : case 'W': case 'X' : case 'Y': case 'Z': 

        return VARIABLE;


    case zeroSymbol:
    case oneSymbol:

        return CONSTANT;


    case orSymbol : 
    case andSymbol: 
    case iffSymbol : 
    case impliesSymbol: 
    case notSymbol:

        return OPERATOR;


    case lparenSymbol:

        return LEFTPAREN;


    case rparenSymbol:

        return RIGHTPAREN;


    default: 

        return OTHER;
    }
  }


/**
 * Indicate a failure in a specific category name, with the
 * residual input.
 */

LogicTree notFound(String category, String residual)
  {
  return new Failure("did not find " + category + " where expected",
                     residual);
  }


/**
 * Indicate a failure in a specific category name, with a specific
 * symbol expected, and the residual input.
 */

LogicTree notFound(String category, char symbol, String residual)
  {
  return new Failure("did not find " + category + " after " + symbol +
                          " where expected",
                     residual);
  }

}