CSE 109 Final Exam  Wednesday  12 December 2007   8:00-11:00 AM
>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>SUGGESTED ANSWERS<<<<<<<<<<<<<<<<<<<<<<<
1.  Read both this question and question 2 before starting this question.
Write a class Lex to be used by class Parse in question 2.  Class Parse
is used to parse a single line of text from the console. The only
symbols allowed by class Parse are '<', '>', '[', ']', '{', '}', '0',
'1', '.', and '\n'.  The method Lex::next() should return an int corresponding
to the above symbols, 0 for '<', 1 for '>', ... , 9 for '\n', and 10 for
anything else.  The program below indicates how class Lex should behave.
If the input line is
  t < > 01. {    [
then the output would be
t('JUNK') <('<') >('>') 0('0') 1('1') .('.') {('{') [('[')
where blanks and tabs are ignored
int main(){
  char* table[]={"<", ">",  "[", "]", "{", "}", "0", "1", ".", "\n","JUNK"};
  //the entries in 'table' are arranged according to the value that should
  //be returned by next(). a.getCh() returns the most recent character read
  Lex a;
  int tok;
  tok=a.next();
  while(tok!=Lex::EOLN){
    cout<<a.getCh()<<"('"<<table[tok]<<"') ";
    tok=a.next();
  }
  cout<<endl;
}
<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<
#include <iostream>
using namespace std;

class Lex{//Ignore blanks and tabs, return one of the constants below
public:
  Lex();
  static const int LANGL=0,RANGL=1,LSQB=2,RSQB=3,LCURL=4,RCURL=5,
    ZERO=6,ONE=7,PERIOD=8,EOLN=9,JUNK=10;
  int next();
  char getCh()const;
private:
  char ch;
};

Lex::Lex(){ch=' ';}

int Lex::next(){
  char table[]="<>[]{}01.\n";
  if(ch!='\n'){
    cin.get(ch);
    while(ch==' ' || ch=='\t')
      cin.get(ch);
    for(int j=0;j<10;j++)
      if(ch==table[j])
        return j;
    return JUNK;
  }
  else return EOLN;
}

char Lex::getCh()const{
  return ch;
}

>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>
2. Write a class Parse that uses class Lex above to determine whether
a line entered at the console obeys the syntax of the diagrams for P given
below.  Below the digrams is a program that illustrates the use of the
class Parse.  In the diagrams parentheses indicate a circle and square
brackets indicate a rectangle.
int main(){
  Parse p;
  p.parse();//diagnose error or write out "Successful parse"
  return 0;
}                                 +---( < )--[ A ]--( > )--+
                            A     |                        |
P                           ------|---( [ )--[ B ]--( ] )--|------>
-->[ A ]------------->            |                        |
         ^        |               +---( { )--[ C ]--( } )--+
         |        |         B
         +--[ A ]-+         --------( 0 )--------------------------->
                                |          |     ^              |
                                +-->( 1 )->+     |              |
  C                                              |<-----( 0 )<--|
  ------( 0 )--( . )--[ B ]------------>         |              |
      |                        |                 +<-----( 1 )<--+
      +->( [ )--[ P ]--( ] )-->+
<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<
class Parse{
public:
  Parse();
  void parse();
private:
  int tok;
  Lex lex;
  void p();
  void A();
  void B();
  void C();
  void check(bool b,char *mess);
  void next();
};

Parse::Parse(){}

void Parse::next(){
  tok=lex.next();
  cout<<lex.getCh();
}

void Parse::parse(){
  next();
  p();
  check(tok==Lex::EOLN,"Junk at end of line");
  cout<<"Successful parse\n";
}

void Parse::p(){
  A();
  while(tok==Lex::LANGL || tok==Lex::LSQB || tok==Lex::LCURL)
    A();
}

void Parse::A(){
  switch(tok){
  case Lex::LANGL:
    next();
    A();
    check(tok==Lex::RANGL," '>'");
    break;
  case Lex::LSQB:
    next();
    B();
    check(tok==Lex::RSQB," ']' ");
    break;
  case Lex::LCURL:
    next();
    C();
    check(tok==Lex::RCURL," '}' ");
    break;
  default:
    check(false, " '<', '[', or '{' ");
  }
  next();
}

void Parse::B(){
  check(tok==Lex::ZERO || tok==Lex::ONE," '0' or '1' ");
  while(tok==Lex::ZERO || tok==Lex::ONE)
    next();
}

void Parse::C(){
  switch(tok){
  case Lex::ZERO:
    next();
    check(tok==Lex::PERIOD," '.' ");
    next();
    B();
    break;
  case Lex::LSQB:
    next();
    p();
    check(tok=Lex::RSQB," ']' ");
    next();
    break;
  default:
    check(false," '0' or '[' ");
  }
}

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

>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>
3. Write the sml program corresponding to the following spl++ program,
assuming that the code is generated by the kind of parser developed for
p7. Recall the SML instructions: READ(10), WRITE(11), LOAD(20), STORE(21),
ADD(30), SUB(31), DIV(32), MULT(33), BRANCH(40), BRANCHNEG(41),
BRNACHZERO(42), HALT(43).

   read x
   write 2*x + 3*(x-7)
   halt
   end
   -56
<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<
10019             0 read x
20020             1 load 2
21999             2 push 2
20019             3 load x
33999             4 (shortcut) 2*x
21999             5 store 2*x
20021             6 load 3
21998             7 push 3
20019             8 load x
21997             9 push x
20022            10 load 7
21996            11 push 7
20019            12 load x
31996            13 (shortcut) sub 7
33998            14 (shortcut) mult by 3
30999            15 (shortcut) add 2*x
21999            16 push result
11999            17 write result
43000            18 halt
0                19 x
2                20 2
3                21 3
7                22 7
END
-56
>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>
4.  Below is the class Name, used for storing the first and family names
of people.  Write a subclass of Name called Student that also stores
a person's age and which enables one to determine when one instance of
Student is less than (<) another instance of Student. Below the declaration
of the class Name is a short program (with indicated output) that shows how
class Student is used.  You need only provide Student with the methods that
will enable the class to be used in the program below.

#include "word.h"

class Name{
public:
  Name(char* famName,char * fstName);
  Word getFirst()const;
  Word getFam()const;
protected:
  Word familyName,firstName;
  static void check(bool b, char*mess);
};
int main(){
  Student a("Mix","Thom",43),b("Mix","Alfred",27),c("Jones","Henry",83);
  cout<<"'"<<a.getFirst()<<" "<<a.getFam()<<"' < '"<<b.getFirst()<<" "<<
     b.getFam()<<"': "<<(a<b)<<endl;
  cout<<"'"<<c.getFirst()<<" "<<c.getFam()<<"' < '"<<b.getFirst()<<" "<<
     b.getFam()<<"': "<<(c<b)<<endl;
  cout<<b.getFirst()<<" "<<b.getFam()<<" is "<<b.getAge()<<" years old\n";
  Student d("Hal","Esperance",220);//should crash
}
OUTPUT:
'Thom Mix' < 'Alfred Mix': 0
'Henry Jones' < 'Alfred Mix': 1
Alfred Mix is 27 years old
ERROR:  Age out of range [1, 129]
<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<
class Student:public Name{
public:
  Student(char * famName,char* fstName,int ag);
  friend bool operator<(const Student &s,const Student&t);
  int getAge()const;
private:
  int age;
};

Student::Student(char * famName,char* fstName,int ag):
  Name(famName,fstName),age(ag){
  check(ag>0 && ag< 130," Age out of range");
}

int Student::getAge()const{
  return age;
}

bool operator<(const Student &s,const Student&t){
  return s.getFam()<t.getFam() ||
    s.getFam()==t.getFam() && s.getFirst() < t.getFirst();
}
>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>
5.  Below is the declaration developed in class for class Link.  Write the
functions inOrder() and reverseOrder(). Given Link *head; and assuming that
head points to a linked list that terminates in NULL, then inOrder(head)
display on the screen the links in the order in which they appear in the
list, while reverseOrder() displays on the screen the links in reverse
order (last link first).  
#include <iostream>
using namespace std;

//implement the ADT for a "Link"
class Link{
public:
  Link(int k=0,double d=0,Link*nxt=NULL);
  ~Link();
  int key;
  double data;
  Link *next;
};
<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<
void inOrder(Link * hd){
  while(hd!=NULL){
    cout<<"{"<<hd->data<<", "<<hd->key<<"} ";
    hd=hd->next;
  }
}

void reverseOrder(Link *hd){
  if(hd!=NULL){
    reverseOrder(hd->next);
    cout<<"{"<<hd->data<<", "<<hd->key<<"} ";
  }
}
>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>
6. Consider the ADT for a set, a collection of objects (of the same
type) where any object appears at most once. Thus when an object is
added a second time, the set does not change, because it already has
the given object in the set. Write a template for a class that implements
this ADT. Your template need only include sufficient declarations so that
the code below compiles and produces the indicated output when run

#include <iostream>
using namespace std;
#include "word.h"

int main(){
  Set<Word> s(9); //set that can hold a maximum of 9 instances of Word
  s.add("Hello").add("Goodbye").add("Friend").add("Hello");
  cout<<s<<endl;  //OUTPUT: {Hello Goodbye Friend}
}
<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<
template <class X>
class Set{
public:
  Set(int k);
  ~Set();
  Set & add(const X&x);
  template <class Y>
  friend ostream &operator<<(ostream &out,const Set<Y> & s);
  bool inSet(const X&x)const;
private:
  X *obj;
  static  void check(bool b, char *mess);
  int count,size;
};

template <class X>
Set<X>::Set(int k):count(0),size(k){
  check(k>0,"Bad set size");
  obj=new X[size];
  check(obj!=NULL,"Heap overflow:");
}

template <class X>
Set<X>::~Set(){
  delete [] obj;
}

template <class X>
Set<X> &  Set<X>::add(const X&x){
  if(!inSet(x)){
    check(count<size,"Set overflow");
    obj[count]=x;
    count++;
  }
  return *this;
}

template <class X>
bool Set<X>::inSet(const X&x)const{
  for(int j=0;j<count;j++)
    if(obj[j]==x)
      return true;
  return false;
}

template <class Y>
ostream &operator<<(ostream &out,const Set<Y> & s){
  out<<"{";
  for(int j=0;j<s.count;j++){
    if(j>0)
      out<<" ";
    out<<s.obj[j];
  }
  out<<"}";
  return out;
}
   
template <class Y>
void Set<Y>::check(bool b, char *mess){
  if(!b){
    cerr<<"ERROR: "<<mess<<endl;
    exit(1);
  }
}
>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>
7.  Write a C program that will compile with the -xc option for the g++
compiler. The program should read five ints from the textfile 'DATA' and
write out to the console the sum of the squares of the numbers. It can
assume there are at least five ints.
<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<
#include <stdio.h>

int main(){
  FILE *f;
  f=fopen("DATA","r");
  if(f==NULL){
    printf("Failure to open the file 'DATA'\n");
    exit(1);
  }
  int j,x,sum;
  sum=0;
  for(j=0;j<5;j++){
    fscanf(f," %d",&x);
    sum+=x*x;
  }
  printf("The sum of the squares is %d\n",sum);
}
>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>
8.  Write a program that when called with one command line argument tries to
open a file whose name is given by the argument and then writes out to the
screen the number of non-white characters in the file. The white characters
are the blank, the tab, the line-feed, and the carriage return.  If the
C++ program is stored in the file a.cc and the compiled program is stored in
the a.out, then the call
   a.out a.cc
should display something like
  The file 'a.cc' has 593 non-white character(s)
<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<
#include <iostream>
#include <fstream>
using namespace std;

void openFile(int ct,char**argv,ifstream &f);
void check(bool b,char*mess,char*a="",char*c="");
int size(istream & f);

int main(int ct,char **argv){
  ifstream f;
  openFile(ct,argv,f);
  cout<<"The file '"<<argv[1]<<"' has "<<size(f)<<" non-white character(s)\n";
}

void openFile(int ct,char**argv,ifstream &f){
  check(ct==2,"Usage: ",argv[0]," <inputFile>");
  f.open(argv[1]);
  check(f!=NULL,"Failure to open input file");
}
  
void check(bool b,char*mess,char *a, char*c){
  if(!b){
    cerr<<mess<<a<<c<<endl;
    exit(1);
  }
}

int size(istream & f){
  int ct;
  char ch;
  ct=0;
  f>>ch;
  while(f.good()){
    ct++;
    f>>ch;
  }
  return ct;
}

>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>