CSE 109 Final Examination Tuesday  6 May 2008
>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>SUGGESTED ANSWERS<<<<<<<<<<<<<<<<<<<<<<<<<<
1.  In this question I ask you to develop a class Scan for use in question 2.
Class Scan should read from a textfile and implement (at least) two methods:
   next() - ignores the character '\r' and returns the next character from the
            input stream, unless ther is no next character (end of file), in
            which case it should return '#'.
   good() - returns true if and only if there is another character to be
            returned when next() is subsequently called.
Below is an example of how an instance of Scan is created:
    ifstream f("aFile");
    check(f!=NULL," Failure to open 'aFile'");
    Scan  s(f);
>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>
#include <iostream>
using namespace std;
class Scan{
public:
  Scan(istream &in);
  char next();
  bool good();
private:
  char ch;
  istream *fin;
  bool firstTime;
  void getch();
};

Scan::Scan(istream &in):fin(&in),firstTime(true){}

char Scan::next(){
  char temp;
  if(firstTime){
    getch();
    firstTime=false;
  }
  temp=ch;
  getch();
  return temp;
}

void Scan::getch(){
  fin->get(ch);
  while(fin->good() && ch=='\r')
    fin->get(ch);
  if(!fin->good())
    ch='#';
}

bool Scan::good(){
  return fin->good();
}
<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<
2.  Write the rest of the program that I started below. It is meant to
determine whether the contents of a file satisfy the syntax diagrams for
P below. In the diagrams I indicate circles with parentheses, (), and rectangles
with square braces, [].  No blanks, tabs, or newlines are allowed.
                                      +----('a')-----------------+
       P                              |                          |
       ----->[S]--->('#')-->      S-->+----('b')--[T]--------------->
                                      |                          |
           +---('a')--[T]--('s')--+   +----('q')---[S]---('a')---+
       T   |                      |
       ----+--('b')--('s')--[T]--------->
           |                      |
           +--------('c')---------+

    void check(bool b,char *mess){if (!b) {cerr<<"ERROR: "<<mess<<endl;
                                           exit(1);} }
    int main(){
      ifstream f("x.dat");
      check(f!=NULL,"Failure to open the file 'x.dat'");
      Scan s(f);
      parse(s);
      cout<<"Parse succeeds\n"; //exit before here if parse fails
    }
>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>
#include <fstream>
#include <iostream>
using namespace std;
void parse(Scan &s); //plays the role of P
void S(Scan &s,char &ch);
void T(Scan &s,char &ch);

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

int main(){
  ifstream f("x.dat");
  check(f!=NULL,"Failure to open the file 'x.dat'");
  Scan s(f);
  parse(s);
  cout<<"Parse succeeds\n"; //exit before here if parse fails
}

void parse(Scan &s){
  char ch;
  ch=s.next();
  S(s,ch);
  check(ch=='#'," '#' expected");
}

void S(Scan &s,char &ch){
  switch(ch){
  case 'a': ch=s.next(); break;
  case 'b': ch=s.next();
    T(s,ch);
    break;
  case 'q': ch=s.next();
    S(s,ch);
    check(ch=='a'," 'a' expected");
    ch=s.next();
    break;
  default: check(false," 'a', 'b', or 'q' expected");
  }
}

void T(Scan &s,char &ch){
  switch(ch){
  case 'a': ch=s.next();
    T(s,ch);
    check(ch=='s'," 's' expected");
    ch=s.next();
    break;
  case 'b': ch=s.next();
    check(ch=='s'," 's' expected");
    ch=s.next();
    T(s,ch);
    break;
  case 'c': ch=s.next(); break;
  default: check(false," 'a', 'b', or 'c' expected");
  }
}
<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<
3.  Below is my start on the declaration of the class Word.  Provide the
declaration and definition for the subclass of Word, FWord, that has the
functionality indicated by the code below.
class Word
{public:
  static const int LENGTHMAX=12;
  Word(char *st="");
  const Word & operator=(const Word &w);
  friend ostream & operator <<(ostream &out,const Word &w);
 protected:
  char str[LENGTHMAX];
  static void check(bool ok,char *mess);
};

void x(const FWord &a, FWord &b) { b[0]=a[0];}
int main(){
  FWord a("James"), b("Hello");
  x(a,b);
  cout<<b<<" has "<<b.size()<<" letters\n";//OUTPUT: Jello has 5 letters
}
>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>
#include <iostream>
using namespace std;
class FWord:public Word{
public:
  FWord(char *st="");
  int size()const;
  char & operator[](int index);
  char operator[](int index)const;
};

FWord::FWord(char *st):Word(st){}
int FWord::size()const{return strlen(str);}
char& FWord::operator[](int ind){
  check(ind>=0 && ind <=size(),"Range error");
  return str[ind];
}
char FWord::operator[](int ind)const{
  check(ind>=0 && ind <size(),"Range error");
  return str[ind];
}
<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<
4.  Write a template for a class Sequence that can store a sequence of up
to 100 items. It should have the functionality indicated by the code below.

Sequence <double> x;
(((x+=5.6)+=2.3)+=1.4)+=1.7;
cout<<x<<" has "<<x.length()<<" entries\n";
    //OUTPUT: [5.6, 2.3, 1.4, 1.7] has 4 entries
>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>
#include <iostream>
using namespace std;

template <class A>
class Sequence{
public:
  static const int MAX=100;
  Sequence();
  int length()const;
  Sequence & operator+=(const A &a);
  template <class X>
  friend  ostream & operator<<(ostream &out,const Sequence<X> &s);
private:
  A x[MAX];
  int ct;
  static void check(bool ok,char *mess);
};

template <class A>
Sequence<A>::Sequence():ct(0){}

template <class X>
ostream & operator<<(ostream &out,const Sequence<X> &s){
  out<<"[";
  for(int j=0; j<s.ct; j++){
    if(j>0)
      out<<", ";
    out<<s.x[j];
  }
  out<<"]";
  return out;
}

template <class A>
int Sequence<A>::length()const{return ct;}

template <class A>
Sequence<A> & Sequence<A>::operator+=(const A&a){
  ct++;
  check(ct<MAX,"Array overflow");
  x[ct-1]=a;
  return *this;
}

template<class A>
void Sequence<A>::check(bool ok,char*mess){
  if(!ok){
    cerr<<"ERROR: "<<mess<<endl;
    exit(1);
  }
}
<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<
5.  Assume the class Node below, assume that 'root' is of type Node *, and
assume that root points to a binary tree.  Write the function count() that
returns the number of entries in the tree 'outside' two values. For example,
the call count(root,-3,4) would return the number of entries in the tree
that are either less than -3 or greater than 4.  For another example,
count(root,4,-3) would simply count all the entries in the tree, because
any int is either less than 4 or greater than -3 (or both).  For a third
example, count(root,5,5) would count all entries not equal to 5.
    class Node{
       public:
         int j;
         Node* child[2];
    }
>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>
#include <iostream>
using namespace std;

int count(Node * root,int a, int b){
  int temp;
  if(root==NULL)
    return 0;
  if(root->j<a || root->j>b)
    temp=1;
  else
    temp=0;
  return temp+count(root->child[0],a,b)+count(root->child[1],a,b);
}
<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<
6.  Assume the struct below, assume hd is of type struct Link*, and assume
that hd points to a linked list.  Write a C (NOT C++) function (that will be
compiled with the C compiler: g++ -xc), list(), such that the call list(hd,0)
displays the contents of the linked list from the first link to the last,
and the call list(hd,1) displays the contents in reverse order (last to first).
      struct Link{
          int j;
          struct Link * next;
      };
>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>
#include <stdio.h>

void list(struct Link * hd,int dir){
  if(hd==NULL)
    printf("%sNULL",dir==0?"-->":"");
  else{
    if(dir==0)
      printf("-->%d",hd->j);
    list(hd->next,dir);
    if(dir==1)
      printf("<--%d",hd->j);
  }
}
<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<
7.  Write a program that reads the entries on the command line and writes
them out in upper case. For example, if the executable code is stored in
a.out, then the call
   a.out  g++ kungFu
would display on the screen
   A.OUT G++ KUNGFU
>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>
#include <iostream>
using namespace std;

void upcase(char * ch){
  for(int j=0;j<(int)strlen(ch);j++)
    if(ch[j]>='a' && ch[j]<='z')
      ch[j]=ch[j]-'a'+'A';
}

int main(int ct,char **arg){
  for(int j=0;j<ct;j++){
    upcase(arg[j]);
    cout<<arg[j]<<' ';
  }
  cout<<endl;
}
<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<
8. Write SML code that would (reasonably) be generated when the YAPL program
   below is parsed using a recursive descent parse.
    (Recall the SML opcodes:  10(read), 11(write), 20(load), 21(store),
    30(add), 31(subtract), 32(divide), 33(multiply), 40(branch), 41(branch
    if negative), 42(branch if zero), 43(halt).)

        read x
        write 2+(x-3)*(x+4)
        halt
        end
>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>
10025             0 read x
20026             1 load 2
21999          2 push 2
20025             3 load x
21998          4 push x
20027             5 load 3
21997          6 push 3
20998          7 load stk-1
31997          8  x-3
21998          9 pop, popo, push x-3
20025            10 load x
21997         11 push x
20028            12 load 4
21996         13 push 4
20997         14 load stk-1
30996         15 x+4
21997         16 pop, pop, push x+4
20997         17 load x+4
33998         18  (x-3)*(x+4)
21998         19 push (x-3)*(x+4)
20998         20 load (x-3)*(x+4)
30999         21 add 2
21999         22 pop,pop,push result
11999         23 write result
43000         24  quit
0             25 x
2             26
3             27
4             28
END
5
<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<