CSE 109 Final Examination   Wednesday  11 May 2005
>>>>>>>>>>>>>>>>>>>>>>>>>>>SUGGESTED ANSWERS<<<<<<<<<<<<<<<<<<<<<<<<<<<<
1. Write the prototypes and declarations for the functions called in the
program below, which I intend to compile with the gcc compiler using the
-xc option. The program should read two integers from the text file
"final.inp" and store them, the larger first, in the text file "final.out".
   int main()
   {int a,b;
    getdata(&a,&b);
    storedata(a,b);
   }
>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>
#include <stdio.h>
void getdata(int *a, int *b);
void storedata(int a, int b);
void getdata(int *a, int *b)
{FILE *in;
 in=fopen("final.inp","r");
 if(in==NULL)
   {printf("Failure to open input file\n");
    exit(1);
   }
 fscanf(in,"%d %d",a,b);
}

void storedata(int a, int b)
{FILE *out;
 out=fopen("final.out","w");
 if(out==NULL)
   {printf("Failure to open output file\n");
    exit(2);
   }
 fprintf(out," %d %d ", a>b?a:b,a>b?b:a);
}
<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<
2.  Write a template for (the definition and code for) a class called Range
that maintains the largest and smallest values it has been given, discarding
the rest.  It should have a constructor that takes two values of the base
type to set the initial range.  It should overload += to enable (the potential)
addition of new values to the range, it should have methods max() and min() for
access to the largest and smallest value, and it should overload << for display
of the largest and smallest value, e.g., "[12, 23]".  The class can assume
that instances of the base type enable '<' and '>'. Here is some sample
code.
    Range<int> x(10,20); //constructor requires min before max, min<max
    x+=3; //range changed to [3,20]
    x+=17; //range unaffected
    cout<<x,min()<<" "<<x.max()<<" "<<x<<endl; //"3 20 [3,20]"
>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>
#include <fstream.h>

template <class X>
class Range
{public:
  Range(const X &a, const X&b);
  Range();
  X min()const;
  X max()const;
  Range & operator+=(const X&x);
  template <class Y>
  friend ostream & operator<<(ostream & out,const Range<Y> &r);
 private:
  X small,large;
  static void check(bool b, char*mess);
};

template <class X>
Range<X>::Range(const X&a, const X&b):small(a),large(b)
{check(a<b,"Bad initial range"); }

template <class X>
Range<X>::Range(){check(false,"No range specified");}

template <class X>
X Range<X>::min()const{return small;}

template <class X>
X Range<X>::max()const{return large;}

template <class X>
Range<X> & Range<X>::operator+=(const X &x)
  {if(x<small)
    small=x;
   else if(x>large)
    large=x;
   return *this;
}

template <class X>
ostream & operator<<(ostream & out,const Range<X> &r)
{out<<"["<<r.small<<", "<<r.large<<"]";
 return out;
}

template <class X>
void Range<X>::check(bool b,char*mess)
 {if(!b)
   {cerr<<"ERROR: "<<mess<<endl;
    exit(1);
   }
 }
<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<
3.  Assume that the following data structures were used to create a hash
table for social security numbers, where the number itself was used for
the hash number and where the quadratic probe was used to resolve collisions.
Write the function value() that returns a copy of the string that corresponds
to the given social security number if it is in the table and returns NULL
otherwise. The call to value() would be of the form
   value(230304467,table,37);

  struct Rek
  {int  SSNumber;
   char *name;
   };
  Rek *table[37];  //initially all NULL entries
>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>
char * value(int n,Rek *r[],int size)
{int h,rep;
 char *temp;
 rep=1;
 h=n%size;
 while(rep<size && r[h]!=NULL && r[h]->SSNumber!=n)
  {h=(h+rep)%size;
   rep+=2;
  }
 if(r[h]==NULL || r[h]->SSNumber!=n)
   return NULL;
 temp=new char[strlen(r[h]->name)+1];
  if(temp==NULL)
    {cerr<<"Heap overflow\n";
     exit(1);
    }
 strcpy(temp,r[h]->name);
 return temp;
 }
<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<
4.  My implementation of mcall depends upon a number of files that have the
following relationships.
 parse.h has the declaration of class Parser, which has a data member of type
     Lex.
 parse.cc has the code for class Parser and uses the constants in emulate.h.
 fullparse.h has the declaration for the class FullParser, which is a subclass
   of class Parser
 fullparse.cc has the code for class FullParser
 lex.h has the declaration of class Lex. Class Lex has a data member that is
   of type Table<Word>
 lex.cc has the coder for class Lex.
 table.h has templates for class Table<>.
 word.h has the declaration of the class Word
 word.cc has the code for class Word
 mcall.cc contains the main program, which has a variable of type FullParser

 Write the makefile for compiling the code files and linking them to create the
 executable file mcall.
>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>
OPT= -c -Werror -Wall
mcall: mcall.o parse.o fullparse.o word.o lex.o
       g++ -o mcall mcall.o parse.o fullparse.o word.o lex.o

mcall.o: mcall.cc parse.h fullparse.h word.h lex.h table.h emulate.h
       g++ $(OPT) mcall.cc

lex.o: lex.cc table.h word.h lex.h
       g++ $(OPT) lex.cc

word.o: word.h word.cc
       g++ $(OPT) word.cc

parse.o: parse.cc parse.h lex.h word.h table.h emulate.h
       g++ $(OPT) parse.cc

fullparse.o: fullparse.cc fullparse.h parse.h lex.h word.h table.h emulate.h
       g++ $(OPT) fullparse.cc

clean:
     rm -f *.o *~ mcall
<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<
5.  Assume that in developing the class Word from lecture, I have progressed
to the point of having the declaration below.  Continue the development
by slightly modifying class Word and by writing the declaration and definition
(code) of a subclass of Word, Wordy, that simply implements []. The behavior
of instances of Wordy is indicated by the code below the declaration.
class Word
{public:
  Word(char *x="");
  friend ostream & operator<<(ostream &out,const Word & t);
 private:
  static void check(bool b, char *mess);
  char *str;
};

Wordy x("One");
cout<<x[2]<<x[1]<<x[0]<<endl; //OUTPUT: enO
>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>
NOTE: IN CLASS WORD CHANGE private TO PROTECTED
class Wordy: public Word
{public:
  Wordy(char *x="");
  char & operator[](int n);
  char operator[](int n)const;
};

Wordy::Wordy(char *x):Word(x){}

char & Wordy::operator[](int n)
{check(n>=0 && n<strlen(str),"Index out of range");
 return str[n];
}

char Wordy::operator[](int n)const
{check(n>=0 && n<strlen(str),"Index out of range");
 return str[n];
}
<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<
6.Write MAC3 code that corresponds to the following MCALL program
Hint: Recall the codes HALT(0), READ(1), WRITE(2), ADD(3), SUB(4),
MUL(5), DIV(6), MOV(7), CJMP(8).
    read x
    if x>9 goto 100
    write 100
100
    halt
    end
>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>
   1080000           read x      [1]
   4000806          load x-9 into 0 [2]
   8040405           skip if >0       [3]
   2070000           write 100        [4]
   0                 halt             [5]
   9                 const 9          [6]
   100               const 100        [7]
   E                  x appears in    [8]
<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<

7.  Someone complained that the syntax diagrams for expressions were too
complicated, so I simplified them below.  For this question, to greatly
simplfy the lexical analysis, assume that identifiers are single lower case
letters, that numbers are single digits, and no spaces are allowed. First,
state how the new diagrams would change the syntax, and state how the new
diagrams would change the code generation (which might appear on next year's
final).  Then, write a program that determines whether a line of text entered
at the keyboard obeys the syntax for Expression, either diagnosing the first
error or writing "Good syntax."   Note: Parentheses indicate circles, while
square brackets indicate boxes.  The symbols are +, -, *, /, {, and }

  Expression
  ------------>[Factor]-------------------------------------+
                          ^            +--(+)<-----|
                          |            |--(-)<-----|
                          +-[Factor]<--|--(*)<-----|
                                       +--(/)<-----+
  Factor
  --------------->({)--[Expression]--(})---+
            |--->[Digit]-------------------|
            +--->[Letter]----------------------->
>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>
Aside from changing the definition of Number and Identifier, the new
diagrams will accept and reject exactly the same strings as the old
diagrams.  However, with the new diagrams, when the code is generated,
all operators will have the same precedence, rather than * and / having
precedence over + and -.
#include <fstream.h>

void expression(char &ch);
void factor(char &ch);
void check(bool b, char *mess);
void getch(char &ch);

int main()
{char ch;
 getch(ch);
 expression(ch);
 check(ch=='\n',"End of line expected");
 cout<<"Good syntax\n";
}


void expression(char &ch)
{factor(ch);
 while(ch=='+' || ch=='-' || ch=='*' || ch=='/')
  {getch(ch);
   factor(ch);
  }
}

void factor(char &ch)
{if(ch>='0' && ch<='9' || ch>='a' && ch<='z')
  getch(ch);
 else
   {check(ch=='('," digit, letter or '(' expected");
   getch(ch);
   expression(ch);
   check(ch==')'," ')' expected");
   getch(ch);
   }
}

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

void getch(char &ch)
{cin.get(ch);
 if(!cin.good())
   ch='\n';
 cout<<ch;
}
<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<

8.  Write the output of the following program.
#include <fstream.h>

class A
{public:
  A(){}
  char one(char ch)
  {return ch>='a' && ch<='z'? two(ch): (ch>='A' && ch<='Z'?three(ch):ch);}
  char two(char ch){return ch-1;}
  virtual char three(char ch){return ch-2;}
};

class B:public A
{public:
  B(){}
  char two(char ch){return ch+3;}
  char three(char ch){return ch+1;}
};

int main()
{char ch,*final="Gbwf b Fppe Ubdbujpo";
 B b;
 int loc;
 loc=0;
 while(final[loc]!='\0')
 {cout<<b.one(final[loc]);
  loc++;
 }
 cout<<endl;
  return 0;
}
<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<
Have a Good Vacation
>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>