// ************************** PARSER ************************************
class Parser {
  //This class packages the parser code and expression to be parsed as an
  //object.  The tokens are stored in an array which is private to the
  //parser object.  The parsing routines will be instance methods and they
  //will call each other with mutual recursion.  The main method is called
  //parse and it returns an ExpTree.  To see how tokenizer and parser are
  //used see the final main method of the class Codegen.  The basic idea is
  //that every time you want to parse an expression you will create a new
  //parser object which encapsulates the parsing routines and the string of
  //characters which have to be parsed.

  private char[] tokens;
  private int cursor;
  private char sym;

  private void getsym(){
    //This gets a new symbol for processing and it advances the cursor.
    //The next comment is for debugging purposes.  Uncomment it if needed.
    //    System.out.println("Entering getsym " + cursor + " " + sym);
    cursor++; sym = tokens[cursor]; }

  private void error(){System.out.println("Parsing error occurred.");}

  public Parser(char[] A){
    //Creates a new parser object with the characters to be parsed stored
    //in it and the sym and cursor initialized.
    tokens = A;
    cursor = 0;
    sym = tokens[cursor];}

  public ExpTree parse(){
  //Does addition. Every time it sees addition, it calls the next most tightly
  //binding operation (subtraction).
      ExpTree result = null;
      ExpTree temp = null;
      ExpTree operRight = null;
      boolean newResult = false;
      temp = this.parsesub();
      result = temp; //Do this in case there's no addition performed, so this
                     //function still returns something.
      Character currentSym = new Character(this.sym);
      while (currentSym.toString().equals("+")) {
          getsym();
          if(!newResult) {
          //If this is the first result, we want to create a new tree.
              result = new Oper(currentSym, temp, this.parsesub());
              newResult = true;
          }
          else {
          //If we've already built a tree, we build "up" on it.
              result = new Oper(currentSym, result, this.parsesub());
          }
          currentSym = new Character(this.sym);
      }
      return result;
  }// end method parse
  
  public ExpTree parsesub(){
  //Does subtraction. Every time it sees subtraction, it calls the next most tightly
  //binding operation (multiplication).
      ExpTree result = null;
      ExpTree temp = null;
      ExpTree operRight = null;
      boolean newResult = false;
      temp = this.term();
      result = temp; //Do this in case there's no subtraction performed, so this
                     //function still returns something.
      Character currentSym = new Character(this.sym);
      while (currentSym.toString().equals("-")) {
          getsym();
          if(!newResult) {
          //If this is the first result, we want to create a new tree.
              result = new Oper(currentSym, temp, this.term());
              newResult = true;
          }
          else {
          //If we've already built a tree, we build "up" on it.
              result = new Oper(currentSym, result, this.term());
          }
          currentSym = new Character(this.sym);
      }
      return result;
  }// end method parsesub

  public ExpTree term(){
  //Does multiplication. Every time it sees multiplication, it calls the next most tightly
  //binding operation (division).
      ExpTree result = null;
      ExpTree temp = null;
      ExpTree operRight = null;
      boolean newResult = false;
      temp = this.termdiv();
      result = temp; //Do this in case there's no multiplication performed, so this
                     //function still returns something.
      Character currentSym = new Character(this.sym);
      while (currentSym.toString().equals("*")) {
          getsym();
          if(!newResult) {
          //If this is the first result, we want to create a new tree.
              result = new Oper(currentSym, temp, this.termdiv());
              newResult = true;
          }
          else {
          //If we've already built a tree, we build "up" on it.
              result = new Oper(currentSym, result, this.termdiv());
          }
          currentSym = new Character(this.sym);
      }
      return result;
  }//end method term
  
  public ExpTree termdiv(){
  //Does division. Every time it sees division, it calls the next most tightly
  //binding operation (powers).
      ExpTree result = null;
      ExpTree temp = null;
      ExpTree operRight = null;
      boolean newResult = false;
      temp = this.pow();
      result = temp; //Do this in case there's no division performed, so this
                     //function still returns something.
      Character currentSym = new Character(this.sym);
      while (currentSym.toString().equals("*")||currentSym.toString().equals("/")) {
          getsym();
          if(!newResult) {
          //If this is the first result, we want to create a new tree.
              result = new Oper(currentSym, temp, this.pow());
              newResult = true;
          }
          else {
          //If we've already built a tree, we build "up" on it.
              result = new Oper(currentSym, result, this.pow());
          }
          currentSym = new Character(this.sym);
      }
      return result;
  }//end method termdiv
  
  public ExpTree pow(){
  //Does powers. Every time it sees powers, it calls primary(), because powers
  //are the most tightly binding operation
      ExpTree result = null;
      ExpTree temp = null;
      ExpTree operRight = null;
      boolean newResult = false;
      temp = this.primary();
      result = temp; //Do this in case there's no powers performed, so this
                     //function still returns something.
      Character currentSym = new Character(this.sym);
      while (currentSym.toString().equals("^")) {
          getsym();
          if(!newResult) {
          //If this is the first result, we want to create a new tree.
              result = new Oper(currentSym, temp, this.primary());
              newResult = true;
          }
          else {
          //If we've already built a tree, we build "up" on it.
              result = new Oper(currentSym, result, this.primary());
          }
          currentSym = new Character(this.sym);
      }
      return result;
  }//end method term

  public ExpTree primary(){
      ExpTree result = null;
      Character currentSym = new Character(this.sym);
      //Use Unicode to check if it's a letter:
      int currentUnicode = Character.getNumericValue(this.sym);
      if (10 <= currentUnicode && currentUnicode <= 35) { //it's a variable
          result = new Var(new Character(this.sym));
          getsym();
          return result;
      }
      else if (currentSym.toString().equals("(")) { //left parenthesis
      //If we are in parentheses, we "start over"
          getsym();
          result = this.parse();
          currentSym = new Character(this.sym);
          //Check for right parenthesis:
          if (!currentSym.toString().equals(")")) {
              error();
              return null;
          }
          else {
              getsym();
              return result;
          }
      }
      else return null;
  }// end method primary

  public static void main(String[] args){
    // The commented-out code was for a very basic preliminary test.
     //char[] Data = new char[12];
     /*Data[0] = '(';
     Data[1] = 'A';
     Data[2] = '+';
     Data[3] = 'B';
     Data[4] = ')'; 
     Data[5] = '*';
     Data[6] = '(';
     Data[7] = 'C';
     Data[8] = '+';
     Data[9] = 'D'; 
     Data[10] = ')';
     Data[11] = '$';*/
    //  System.out.println(args[0]);
    char[] Data = Tokenizer.scan(args[0]);
    Parser P = new Parser(Data);
    ExpTree E = P.parse();
    System.out.println("E.postorder() output: ");
    E.postorder();System.out.println();
    System.out.println("\nE.preorder() output: ");
    E.preorder();System.out.println();
    System.out.println("\nE.inorder() output: ");
    E.inorder();
  }
    
}//end Parser