CSE 109 Test 1  Wednesday  11 April 2007
<<<<<<<<<<<<<<<<<<<SUGGESTED ANSWERS>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>
1.  Assume the definition of class Link below, meant to be used to construct
a linked list ending in a NULL pointer. Overload the operator "<<" such that
the code below the definition of Link would display the linked list in the
following form:     6-->4-->3-->NULL
class Link{
public:
  int j;
  Link *next;
};

Link * t;
//some code to build the list
cout<<t<<endl;
<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<
ostream & operator<<(ostream &out,Link *k){
  while(k!=NULL){
    out<<k->j<<"--> ";
    k=k->next;
  }
  out<<"NULL";
  return out;
}
>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>
2. Write a template for the class Comaprable that stores an instance of some
variable for which "<" is defined. Instances of the class should respond to
the methods min()  (max()) by returning an instance of Comparable containing
the value from the smaller  (larger) of two instances.  For example, the code
below should produce the indicated output.
   Comparable <int> a(5),b(3);
   cout<<a.min(b)<<" "<<a.max(b)<<endl;  // [3] [5]
<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<
template <class X>
class Comparable{
public:
  Comparable(const X &x);
  Comparable min(const Comparable &t)const;
  Comparable  max(const Comparable &t)const;
  template <class V>
  friend ostream & operator<<(ostream &out,const Comparable<V> &c);
private:
  X data;
};

template <class X>
Comparable<X>::Comparable(const X &x):data(x){}

template <class X>
Comparable<X> Comparable<X>::min(const Comparable&t)const{
  if(data<t.data)
    return *this;
  return t;
}

template <class X>
Comparable<X> Comparable<X>::max(const Comparable&t)const{
  if(data>t.data)
    return *this;
  return t;
}

template <class X>
ostream &operator <<(ostream &out,const Comparable<X> &c){
  out<<"["<<c.data<<"]";
  return out;
}
>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>

3.  This and the next question refer to a language with the syntax given
by the following syntax diagrams (where parentheses, (), indicate circles
and brackets, [], indicate boxes:
       Expression                  +--(+)--+
      ---------------->[Number]-+--|--(-)--|--->[Expression]--->
                                |  +--(/)--+
                                +------------------------------>
       Number is a string of digits
Write a class Lex that performs a lexical analysis on an array of strings
passed to it from the command line.  Each time next() is called, it
returns a constant corresponding the contents of the next string in the
array (unless there are no more strings).  The values that should be
returned are NUM (0), PLUS(1), MINUS(2), DIV(3), NOMORE(4), JUNK(5). For
example, if the following program is called with the command
   a.out 2 + 3 - 4 / 5 8u i
the output would be   NUM PLUS NUM MINUS NUM DIV NUM JUNK JUNK
int main(int ct,char **arg){
  char *labs[]= {"NUM","PLUS","MINUS","DIV","NOMORE","JUNK"};
  Lex q(ct,arg);
  int k;
  k=q.next();
  while(k!=Lex::NOMORE){
    cout<<labs[k]<<" ";
    k=q.next();
  }
}
<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<
class Lex{
public:
  static const int NUM=0,PLUS=1,MINUS=2,DIV=3,NOMORE=4,JUNK=5;
  Lex(int ct,char*arg[]);
  int next();
private:
  char **list;
  int total,count;
};

Lex::Lex(int ct, char *arg[]):list(arg),total(ct),count(0){}

int Lex::next(){
  int loc;
  count++;
  if(count>=total)
    return NOMORE;
  if(lsit[count][1]=='\0')
    switch(list[count][0]){
     case '+': return PLUS;
     case '-': return MINUS;
     case '/': return DIV;
    }
  loc=0;
  while(list[count][loc]>='0' && list[count][loc]<='9')
    loc++;
  if(list[count][loc]=='\0')
    return NUM;
  else
    return JUNK;
}
>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>
4. Write a class Parse that determines whether the strings entered on the
command line for the program satisfy the syntax diagram for Expression in
question 3.  The code below indicates how the class would be used.  Class
Parse should use the class Lex from question 3, which I will assume you wrote
correctly. If the program were stored in a.out, then the command
   a.out  6 + 7 / 99
should output "Successful Parse," while the command
   a.out 6 + 7p
should output something like "Number expected."
int main(int ct,char **arg){
  Parse p(ct,arg);
  p.parse();
  cout<<"Successful Parse\n";
}
<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<
class Parse{
public:
  Parse(int ct,char **arg);
  void parse();
private:
  int tok;
  Lex lex;
  void expression();
  static void check(bool b,char*mess);
};

Parse::Parse(int ct, char**arg):lex(ct,arg){}

void Parse::parse(){
  tok=lex.next();
  expression();
}

void Parse::expression(){
    check(tok==Lex::NUM,"Number expected");
     tok=lex.next();
    if(tok!=Lex::NOMORE){
     check(tok==Lex::PLUS || tok==Lex::MINUS || tok==Lex::DIV,
           "'+', '-', or '/' expected");
    tok=lex.next();
    expression();
  }
}

void Parse::check(bool b, char *mess){
  if(!b){
    cerr<<"ERROR: "<<mess<<endl;
    exit(1);
  }
}
>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>