CSc 109  Final Examination  4 PM Sunday 14 May 2000  PL 455

   >>>>>>>>>>>>>>>>>>>>>>SUGGESTED ANSWERS<<<<<<<<<<<<<<<<<<<<<<<
   1.  (20 pts)  In class I presented an algorithm for converting a string
   containing an expression in infix form to a string containing an
   expression in postfix form.  The algorithm involves the input string, a
   stack, and the output string.  For the string "2+3+4*5>6*3+2", considering
   each character as a token and assuming the C++ precedence for operators,
   in the table below show the status of the stack and the output string after
   each token is read.  I have provided the list of tokens read.

    Token              Stack          Output String
    ------------------------------------------------------------------
     2    |    )                   |    2
    ------------------------------------------------------------------
     +    |    ) +                 |    2
    ------------------------------------------------------------------
     3    |    ) +                 |    2 3
    ------------------------------------------------------------------
     +    |    ) +                 |    2 3 +
    ------------------------------------------------------------------
     4    |    ) +                 |    2 3 + 4
    ------------------------------------------------------------------
     *    |    ) + *               |    2 3 + 4
    ------------------------------------------------------------------
     5    |    ) + *               |    2 3 + 4 5
    ------------------------------------------------------------------
     >    |    ) >                 |    2 3 + 4 5 * +
    ------------------------------------------------------------------
     6    |    )                   |    2 3 + 4 5 * + 6
    ------------------------------------------------------------------
     *    |    ) *                 |    2 3 + 4 5 * + 6
    ------------------------------------------------------------------
     3    |    ) *                 |    2 3 + 4 5 * + 6 3
    ------------------------------------------------------------------
     +    |    ) +                 |    2 3 + 4 5 * + 6 3 *
    ------------------------------------------------------------------
     2    |    ) > +               |    2 3 + 4 5 * + 6 3 * 2
    ------------------------------------------------------------------
     )    |                        |    2 3 + 4 5 * + 6 3 * 2 + >
    ------------------------------------------------------------------

   2.  (15 pts)  Write Simpletron code for the C++ program below,
   assuming a Simpletron machine with 100 words of memory.

     void main(){
       for(int i=1; i<=10; i++)
        cout<<(i*i);
     }
          2012
          3312
          2113
          1113
          2012
          3010
          2112
          3111
          4100
          4300
          0001
          0011
          0001
          END

   3.  (15 pts)  Write SimPL code for the following C++ program.
      void main(){
        int s=0;
        for(int i=1; i<=10; i++)
          s+=i*i;
        cout<<s;
      }
        100 let i=1
        110 let z=10
        120 let s=0
        130 let s=s+i*i
        140 let i=i+1
        150 if i<=z goto 130
        160 print s
        170 stop
        END


   4.  (30 pts)  We did not use the C++ function strtok() for parsing
   SimPL programs because it gobbles up the delimiter(s) specified when
   calling it.  If we had insisted on using tokstr(), we could have
   processed each line by adding spaces in appropriate places (e.g.,
   change "10 let x=(4+y)*3" to "10 let x = ( 4 + y ) * 3"), and then fed
   the resulting string to tokstr(), using ' ' as the delimiter.
   Write a function spaceOut() which takes a char pointer as an argument
   and returns a pointer to a string.  It is assumed that the original
   string obeys the syntax for a line of SimPL code.  The string
   returned should have the symbols of the original string, with spaces
   added between all the tokens of the original string. Note, by the way,
   that strings violating SimPL syntax would subsequently be caught by
   the parser.

   void copy(char *ch,char*buff,int &chLoc,int &buffLoc){
    buff[buffLoc]=ch[chLoc];
       buffLoc++;
       chLoc++;
   }

   char * spaceOut(char *ch){
     if(ch==NULL)
      return NULL;
     int buffLoc,chLoc;
     char *buff;
     buff = new char[2*strlen(ch)+2];
     if(buff==NULL)
      return NULL;
     chLoc=0;
     buffLoc=0;
     while(ch[chLoc]!='\0'){
      copy(ch,buff,chLoc,buffLoc);
      if(ch[chLoc-1]>='a' && ch[chLoc-1]<='z')
       while(ch[chLoc]>='a' && ch[chLoc]<='z')
         copy(ch,buff,chLoc,buffLoc);
      else if(ch[chLoc-1]>='0' && ch[chLoc-1]<='9')
       while(ch[chLoc]>='0' && ch[chLoc]<='9')
        copy(ch,buff,chLoc,buffLoc);
      else switch(ch[chLoc-1]){
         case '<':
         case '>':
         case '=':
         case '!': while(ch[chLoc]=='=' || ch[chLoc]=='!'
                        || ch[chLoc]=='<' || ch[chLoc]=='>')
                   copy(ch,buff,chLoc,buffLoc);
                   break;
         default:  ; //do nothing for single chars: +,-,/,*,),(
       }
       buff[buffLoc]=' ';
       buffLoc++;
     }
     buff[buffLoc]='\0';
     return buff;
   }

   5.  (35 pts)  In designing our tables of records, our table entries
   consisted of the nominal information stored in a record, plus a variable
   for storing the key (usually a string).  A second approach consists
   of having a record class and then creating a subclass of the record
   class which adds a data member for the key and which adds methods for
   accessing the key (the subclass inherits the methods for accessing
   the record).  Below is the declaration of a record class Rek.  Write the
   declaration and definition (code) of the class Entry as a subclass of
   Rek so that the code in the program below compiles and runs.
   class Rek{
     public:
      Rek();
      Rek(int t,int sc);
      Rek(const Rek&r);
      friend ostream &operator<<(ostream&out,const Rek &r);
      int getScore();
      int getTest();
     protected:
      int test,score;   //'test' is the number of the test
   };
   void main(){
     Entry ent1(1,90,"Tom"),ent[3]={Entry(),Entry(2,95,"Dick"),Entry(ent1)};

     if(strcmp(ent[2].getKey(),"Tom")==0)
         cout<<ent1<<endl;
     for(int j=0;j<3;j++)
         cout<<ent[j]<<endl
   }

   The following answer is templated, thus answering question 6 as well.
   template <class REK>
   class Entry: public REK{
    public:
      Entry();
      Entry(const Entry &e);
      Entry(int t,int sc,char *k);
      ~Entry();
      char * getKey();
      friend ostream &operator<<(ostream&out,const Entry &e);
    private:
      char *key;
   };

   template <class REK>
   Entry<REK>::Entry(){key=NULL;}

   template <class REK>
   Entry<REK>::Entry(const Entry &e):REK(e.test,e.score){
      if(e.key==NULL)
        key=NULL;
      else{
        key=new char[strlen(e.key)+1];
        strcpy(key,e.key);
      }
   }

   template <class REK>
   Entry<REK>::Entry(int t,int sc,char *k):REK(t,sc){
     if(k==NULL)
      key=NULL;
     else{
      key=new char[strlen(k)+1];
      strcpy(key,k);
     }
   }

   template <class REK>
   Entry<REK>::~Entry(){
     if(key!=NULL)
     delete key;
   }

   template <class REK>
   char * Entry<REK>::getKey(){
     return key;
   }

   template <class REK>
   ostream &operator<<(ostream&out,const Entry<REK> &e){
     out<<"{"<<e.key<<"--->"<<REK(e.test,e.score)<<"}";
     return out;
   }

   6.  (15 pts) It turns out that in question 5 you can use a template
   for the class of which Entry is a subclass.  Rewrite the declaration
   of Entry so that it is a subclass of a templated class.  Write the
   definition (code) of the member function getKey() for this templated
   version of Entry (but write no other definition).

   7.  (15 pts)  Assume you are using the algorithm discussed in class to
   build a BTree of integers so that an inorder traversal of the tree
   lists the numbers in ascending order.  Show the tree after each of
   the numbers 1, 3, 5, 7, 9, 10, 8, 6 is added to the tree given that the
   maximum number of entries at a node is 2.  Then do the same exercise
   given that the maximum number of entries is 4.
     1 --> 1 3 --> 1 3 5 ==>  3   -->    3      -->  3
                            1   5      1   5 7     1   5 7 9

     ==>   3  7  -->   3  7     -->    3  7       ==>   3  7  9
         1   5 9     1  5  9 10      1  5  8 9 10     1   5  8  10

     ==>      7          --->         7
          3        9            3          9
        1   5    8   10      1    5 6    8   10

     1 --> 1 3 --> 1 3 5 --> 1 3 5 7 --> 1 3 5 7 9 ==>     5
                                                      1  3   7  9

     -->      5          -->       5          -->      5
          1  3  7 9 10         1 3   7 8 9 10      1 3   6 7 8 9 10

      ==>     5      8
           1 3  6 7    9 10

   8.  (20 pts) In class I discussed creating a binary file containing
   instances of the class Junk below.  Assume that I have created such
   a file and stored it in "final.dat".  Write a program which modifies
   the contents of "final.dat" by adding 7 to the value of f for every
   record whose value for n is 3.

    class Junk{
     public:
      int n;
      double f;
      char name[5];
      Junk();
      Junk(int en, double ef, char nam[]);
    };

   void main(){
    Junk a;
    fstream f("final.dat",ios::in | ios::out);
    int loc;

    loc=0;
    while(f.read((char *)&a,sizeof(a))){
      if(a.n==3){
        a.f+=7;
        f.seekp(loc*sizeof(a));
        f.write((char*)&a,sizeof(a));
      }
     loc++;
    }
   }


   9.  (35 pts) On a consulting job I once wrote a program  whose sole
   purpose was to determine whether a very large file had any repeated
   entries.  One way to solve the problem is to hash each entry, halting
   if any duplicate is found.  Suppose the entries are all positive integers.
   Then we can use the integer itself to give the hash value.  Write a
   class HashTable which could be used to solve this problem.  It should
   simply store integers, using the integer itself for the (initial)
   hash value.  It should be of fixed size, say 101, it should store
   its data in an array, and it should use linear probing to resolve
   collisions.  Keep the answer simple.  Include a member function add(int)
   which returns a value of 0 if the number was successfully added to the
   table, a value of 1 if the table was full, and a value of 2 if the number
   was already in the table.

   class HashTable{
    public:
      HashTable();
      HashTable(const HashTable&t);
      int add(int x);
      void dump();
    private:
      int tab[101];
   };

   HashTable::HashTable(){
    for(int j=0;j<101;j++)
     tab[j]=-1;
   }

   HashTable::HashTable(const HashTable&t){
    for(int j=0;j<101;j++)
     tab[j]=t.tab[j];
   }

  int HashTable::add(int x){
    int look,loc;
    look=0;
    loc=x%101;
    while(look<101 && tab[loc]!=-1 && tab[loc]!=x){
     look++;
     loc=(loc+1)%101;
    }
    if(look>=101)
     return 1;
    if(tab[loc]==x)
     return 2;
    tab[loc]=x;
    return 0;
   }