CSE 109 FINAL EXAMINATION  Wednesday 10 December 2008
==============================SUGGESTED ANSWERS=====================
1. Write a program that expects the names of three files (other than the
name of the executable file) on the command line, that copies the contents of
the first file into the third file, and then copies the contents of the
second file into the third file.  The third file should end up with the
contents of the first file, followed by the contents of the second file.
===========================================================================
#include <fstream>
#include <iostream>
using namespace std;

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

void openFiles(char **arg,ifstream &fa, ifstream &fb,ofstream &out){
    fa.open(arg[1]);
    check(fa.good(),"Failure to open first input file");
    fb.open(arg[2]);
    check(fb.good(),"Failure to open second input file");
    out.open(arg[3]);
    check(out.good(),"Failure to open output file");
}

void copyFile(istream &in,ostream &out){
  char ch;
  ch=in.get();
  while(in.good()){
    out<<ch;
    ch=in.get();
  }
}

int main(int ct,char **arg){
  check(ct==4,"Three arguments expected");
  ifstream infa,infb;
  ofstream out;
  openFiles(arg,infa,infb,out);
  copyFile(infa,out);
  copyFile(infb,out);
}
===========================================================================
2. Write a the declaration and definition (code) for the class Lex that is
intended to tokenize the contents of a text file. The four tokens are the
four characters 'a', 'b', 'c', and '#'.  When the method next() is called
the tokenizer should return the character 'a' when 'a' or 'A' is read, should
return 'b' when 'b' or 'B' is read, should return 'c' when 'c' or 'C' is read,
and should return '#' when any other character (including ' ', '\t', and '\n')
is read. Below is an example of the use of the class, and the expected output
when the file "FINAL" contains the text for this final examination.
int main(){
  ifstream fin("FINAL");
  Lex lex(fin);
  for(int j=0;j<17;j++)
     cout<<lex.next();
//INPUT:   CSE 109 FINAL EXA
//OUTPUT:  c##########a####a
}
===========================================================================
#include <fstream>
#include <iostream>
using namespace std;

class Lex{
public:
  Lex(istream&in);
  char next();
private:
  istream *fin;
};
Lex::Lex(istream &in):fin(&in){}
char Lex::next(){
  char ch;
  ch=fin->get();
  cout<<ch;
  if(!fin->good())
    return '#';
  switch (ch){
  case 'a':
  case 'A': return 'a';
  case 'b':
  case 'B': return 'b';
  case 'c':
  case 'C': return 'c';
  default: return '#';
  }
}

===========================================================================

3. Assume that you have the class Lex from question 2. Write a function
parse() (that calls other functions and) determines whether the contents of
a file satisfy the syntax of the diagrams for EXP below.  In the diagrams I
use parentheses, (), to indicate circles, and square brackets, [], to indicate
rectangles.  Next to the diagrams is a sample call to parse().  Note that if
the syntax is violated you should write an error message and exit the program
so that the last line of main() will only execute if the parse succeeds.
void check(bool b,char *mess){
  if(!b){                                       EXP
                                                 ----->(a)---(b)--[A]-+
    cerr<<"ERROR: "<<mess<<endl;                           |          |
    exit(1);                                               +-(a)--[A]-+-(#)->
  }                                                        |          |
}                                                          +-(c)------+
int main(){                                     A
 ifstream f("aFile");                            -->(a)--(b)-----------------+
 check(f.good(),"Failure to open 'aFile'");             |    ^             | |
 Lex lex(f);                                            |    |             | |
 char ch;                                               |    +-[EXP]-(b)<--+ |
 ch=lex.next();                                         |                    |
 parse(lex,ch);                                         +--(a)--->[A]--------|
 cout<<"Successful parse\n";                                                 V
}
===========================================================================
void parse(Lex &lex,char& ch);
void EXP(Lex &lex,char &ch);
void A(Lex &lex,char &ch);
void B(Lex &lex,char& ch);

void parse(Lex &lex,char &ch){EXP(lex,ch);}
void EXP(Lex &lex,char &ch){
  check(ch=='a'," 'a' expected");
  ch=lex.next();
  switch(ch){
  case 'a':
  case 'b':
    ch=lex.next();
    A(lex,ch);
    break;
  case 'c':
    ch=lex.next();
    break;
  default: check(false,"'a', 'b', or 'c' expected");
  }
  check(ch=='#',"'#' expected");
  ch=lex.next();
}

void A(Lex &lex,char &ch){
  check(ch=='a'," 'a' expected");
  ch=lex.next();
  switch(ch){
  case 'a':
    ch=lex.next();
    A(lex,ch);
    break;
  case 'b':
    ch=lex.next();
    while(ch=='b'){
      ch=lex.next();
      EXP(lex,ch);
    }
    break;
  default: check(false," 'a' or 'b' expected");
  }
}

===========================================================================
4. Write the STKM code that would be generated by a program that used  the
techniques discussed in class to generate code for programming assignment
#7 and that had the following STKMASM++ program as input.
   read x
   write 2+(x-3)*(x-4/x)
   halt
   end
   7
Recall the opcodes for STKM: Read(10), Write(11), Push(20), Pop(21), Add(30),
Sub(31), Div(32), Mul(33), Branch(40), BranchLess(41), BranchEqual(42),
Halt(43).
===========================================================================
10016         read x
20017         push 2
20016         push x
20018         push 3
31000         sub 3
20016         push x
20019         push 4
20016         push x
32000         div x
31000         sub 4/x
33000         mul x-4/x
30000         add (x-3)*(x-4/x)
21000         pop
11000         write zero
43000         halt
0             x    [16]
2                  [17]
3                  [18]
4                  [19]
END
7
===========================================================================
5. Write a C (not C++) program that (1) when stored in prog.cc will compile
and run with the command "gcc -xc prog.cc"; (2) reads in from the console 20
ints, stores them in an array, and then displays them in reverse order on the
screen; and (3) has a main program that calls one function to fill the array
and calls a second function to write out the array.
===========================================================================
void getData(int x[]);
void display(int x[]);
int main(){
  int data[20];
  getData(data);
  display(data);
}
void getData(int x[]){
  int j;
  for(j=0;j<20;j++)
    scanf(" %d ",&x[j]);
}
void display(int x[]){
  int j;
  for(j=19;j>=0;j--)
    printf(" %d",x[j]);
}
===========================================================================
6. Write the template for a class that implements the ADT for a "safe
variable."  A safe variable requires that a value be assigned to it before
it is accessed.  Your template need only have the functionality needed for
the program below to compile and run as indicated.
int main(){
  Safe<double> d;
  //cout<<d<<endl;  WOULD CRASH BECAUSE d HAS NOT BEEN ASSIGNED A VALUE
  d.set(42.0);
  cout<<d<<" has the value "<<d.get()<<endl;
    //OUTPUT: Safe(42.0) has the value 42.0
}
===========================================================================
#include <fstream>
#include <iostream>
using namespace std;

template <class X>
class Safe{
public:
  Safe();
  void set(const X &d);
  X get()const;
  template <class Y>
  friend ostream & operator<<(ostream &out,const Safe<Y> & s);
protected:
  X data;
  bool good;
  static void check(bool b, char *mess);
};

template <class X>
Safe<X>::Safe():good(false){}

template <class X>
void Safe<X>::set(const X &d){
  data=d;
  good=true;
}

template <class X>
X Safe<X>::get()const{
  check(good," Undefined variable");
  return data;
}

template <class Y>
ostream & operator<<(ostream &out,const Safe<Y> & s){
  s.check(s.good," Undefined variable");
  out<<"Safe("<<s.data<<")";
  return out;
}

template <class X>
void Safe<X>::check(bool b, char *mess){
  if(!b){
    cerr<<"ERROR: "<<mess<<endl;
    exit(1);
  }
}
===========================================================================
7. Assuming the template Safe<> from question 6, write the declaration and
definition for a subclass, SafeBool, of Safe<bool>, that has the functionality
needed for the program below to compile and to produce the indicated output.
   int main(){
      SafeBool a(true), b(a), c;
      c.set(false);
      cout<<a<<" && "<<b<<" = "<<(a && b)<<endl; // true && true = true
      cout<<"true && "<<c<<" = "<<(true && c)<<endl; // true && false = false
   }
===========================================================================
class SafeBool : public Safe<bool>{
public:
  SafeBool();
  SafeBool(bool t);
  SafeBool(const SafeBool &s);
  friend SafeBool operator&&(const SafeBool&a, const SafeBool&b);
  friend ostream &operator<<(ostream &out,const SafeBool &s);
};

SafeBool::SafeBool(){}

SafeBool:: SafeBool(bool t){
  set(t);
}

SafeBool::SafeBool(const SafeBool &s){
  good=s.good;
  data=s.data;
}

SafeBool operator&&(const SafeBool&a, const SafeBool&b){
  return SafeBool(a.get() && b.get());
}

ostream &operator<<(ostream &out,const SafeBool &s){
  s.check(s.good,"Undefined SafeBool");
  if(s.data)
    out<<"true";
  else
    out<<"false";
  return out;
}
===========================================================================
8. Given struct Node below, write the function inOrder() that checks
whether a tree with the given root has its keys stored so that an "in order"
search of the tree would list the keys in ascending order. Below the
declaration of Node is an example of how the function inOrder() is called.
struct Node{
    int key;
    double x;
    Node *child[2];
};
int main(){
 struct Node *hd;
 buildTree(hd);  //It is your good fortune that someone else wrote this
                 //function
 if(inOrder(hd))
   cout<<"The keys have been properly placed in the tree\n";
 else
   cout<<"The keys have not been properly placed in the tree\n";
}
===========================================================================
bool inOrder(struct Node *rt){
  if(rt==NULL || (rt->child[0]==NULL && rt->child[1]==NULL))
    return true;
  if(rt->child[0]==NULL)
    return rt->key<=rt->child[1]->key &&
           inOrder(rt->child[1]);
  if(rt->child[1]==NULL)
    return rt->key>=rt->child[0]->key &&
           inOrder(rt->child[0]);
  return rt->key>=rt->chuild[0]->key &&
         rt->key<=rt->chuild[1]->key &&
         inOrder(rt->child[0]) &&
         inOrder(rt->child[1]);
}
============================================================================