/*******************************************************************
 This is the symbol table class which maps identifiers to integers.
 update is used to add new identifiers and their associated values
 to the table and lookup is used to return the value associated with
 an identifier
 *******************************************************************/

class Table {
   String id; int value; Table tail;
   Table(String i, int v, Table t) {id=i; value=v; tail=t;}
   Table update(Table t, String i, int v) {return new Table(i,v,t);}
   int lookup(Table t, String key){
      if ((t.id).equals(key))
         return t.value;
      else
         return lookup(t.tail, key);
   }
}

/*******************************************************************
 This is the abstract class for statements. Each statement should
 specify how it should be interpreted by showing how it updates the
 symbol table, Each statement should also return the maximum number
 of arguments used in any print statement
 *******************************************************************/

abstract class Stm {
   void interp() {Table t = interpStm(null);}
   abstract Table interpStm(Table t);
   abstract int maxargs();
}

class CompoundStm extends Stm {
   Stm stm1, stm2;
   CompoundStm(Stm s1, Stm s2) {stm1=s1; stm2=s2;}
   Table interpStm(Table t) {return stm2.interpStm(stm1.interpStm(t));}
   int maxargs() {return Math.max(stm1.maxargs(),stm2.maxargs());}
}

class AssignStm extends Stm {
   String id; Exp exp;
   AssignStm(String i, Exp e) {id=i; exp=e;}
   Table interpStm(Table t) {
      IntAndTable it = exp.interpExp(t);
      if (t == null)
         return new Table(id,it.i,t);
      else
         return t.update(t,id,it.i);
   }
   int maxargs() {return exp.maxargs();}
}

class PrintStm extends Stm {
   ExpList exps;
   PrintStm(ExpList e) {exps=e;}
   Table interpStm(Table t) {
      IntListAndTable ilt = exps.interpExpList(t);
      ilt.il.print();
      return ilt.t;
   }
   int maxargs() {return Math.max(exps.length(),exps.maxargs()); 
  }
}

/************************************************************
 This class specifies the result of evaluating an expression.
 This consists of an integer giving the result of evaluating 
 the expression, and an updated symbol table resulting from
 this evaluation.
 ************************************************************/

class IntAndTable {
   int i; Table t;
   IntAndTable(int ii, Table tt) {i=ii; t=tt;}
}

/*****************************************************************
 This is the abstract class for expressions. Again each expression 
 should specify how it should be interpreted and also return the 
 maximum number of arguments used in any print statement
 *****************************************************************/

abstract class Exp {
   abstract IntAndTable interpExp(Table t);
   abstract int maxargs();
}

class IdExp extends Exp {
   String id;
   IdExp(String i) {id=i;}
   IntAndTable interpExp(Table t) {return new IntAndTable(t.lookup(t,id),t);}
   int maxargs() {return 0;}
}

class NumExp extends Exp {
   int num;
   NumExp(int n) {num=n;}
   IntAndTable interpExp(Table t) {return new IntAndTable(num,t);}
   int maxargs() {return 0;}
}

class OpExp extends Exp {
   Exp left, right; int oper;
   final static int Plus=1,Minus=2,Times=3,Div=4;
   OpExp(Exp l, int o, Exp r) {left=l; oper=o; right=r;}
   IntAndTable interpExp(Table t) {
      IntAndTable arg1 = left.interpExp(t);
      IntAndTable arg2 = right.interpExp(arg1.t);
      switch(oper) {
         case Plus: return new IntAndTable(arg1.i+arg2.i,arg2.t);
         case Minus: return new IntAndTable(arg1.i-arg2.i,arg2.t);
         case Times: return new IntAndTable(arg1.i*arg2.i,arg2.t);
         case Div: return new IntAndTable(arg1.i/arg2.i,arg2.t);
         default: return new IntAndTable(0,arg2.t);
      }
   }
   int maxargs() {return Math.max(left.maxargs(),right.maxargs());}
}

class EseqExp extends Exp {
   Stm stm; Exp exp;
   EseqExp(Stm s, Exp e) {stm=s; exp=e;}
   IntAndTable interpExp(Table t) {return exp.interpExp(stm.interpStm(t));}
   int maxargs() {return Math.max(stm.maxargs(),exp.maxargs());}
}

/******************************************************
 This class is used to hold the results of evaluating a 
 list of expressions.
 ******************************************************/

class IntList {
   int head; IntList tail;
   IntList(int h, IntList t) {head = h; tail = t;}
   void print() {
      System.out.println(head);
      if (tail != null) tail.print();
   }
}

/*******************************************************************
 This class specifies the result of evaluating a list of expressions. 
 This consists of a list of integers giving the result of evaluating 
 the list of expressions, and an updated symbol table resulting from
 these evaluations.
 *******************************************************************/

class IntListAndTable {
   IntList il; Table t;
   IntListAndTable(IntList iill, Table tt) {il=iill; t=tt;}
   IntListAndTable addInt(int i, IntListAndTable ilt) {return new IntListAndTable(new IntList(i,ilt.il),ilt.t);}
}

/***************************************************************
 This is the abstract class for lists of expressions. Again each 
 expression list should specify how it should be interpreted and 
 also return the maximum number of arguments used in any print 
 statement. They should also return the number of expressions in
 the list.
 ***************************************************************/

abstract class ExpList {
   abstract IntListAndTable interpExpList(Table t);
   abstract int maxargs();
   abstract int length();
}

class PairExpList extends ExpList {
   Exp head; ExpList tail;
   public PairExpList(Exp h, ExpList t) {head=h; tail=t;}
   IntListAndTable interpExpList(Table t) {
      IntAndTable it = head.interpExp(t);
      IntListAndTable ilt = tail.interpExpList(it.t);
      return ilt.addInt(it.i,ilt);
   }
   int maxargs() {return Math.max(head.maxargs(),tail.maxargs());}
   int length() {return 1 + tail.length();}
}

class LastExpList extends ExpList {
   Exp head; 
   public LastExpList(Exp h) {head=h;}
   IntListAndTable interpExpList(Table t) {
      IntAndTable it = head.interpExp(t);
      return new IntListAndTable(new IntList (it.i,null),it.t);
   }
   int maxargs() {return head.maxargs();}
   int length() {return 1;}
}