CSE 109 Final Examination  Thursday 14 December   2006
<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<SUGGESTED ANSWERS>>>>>>>>>>>>>>>>>>>>>>>
1.  For parts (a) and (b) below, your code should be in C, where the g++
compiler is called with the -xc option.
   (a) Write C code that prompts the user to enter an integer, reads in
       the integer, and displays the square of the integer entered.
   (b) Write a C function "minmax" which is meant to store the larger of two
       integers in the first int and the smaller in the second int.  Given
       int x, y;, write the call to the function.  After the call we should
       have x>=y.
<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<
(a)   int n;
      printf("Enter an integer, and I square it- ");
      scanf("%d",&n);
      printf("The square of %d is %d \n",n,n*n);
(b)   void minmax(int *a,int *b)
      {int temp;
       if(*a<*b)
        {temp=*a;
         *a=*b;
         *b=temp;
        }
      }

     minmax(&x,&y);
>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>

2. Write a program that determines whether a line of text entered from the
console satisfies the syntax for A below, where  () denotes ovals and []
denotes boxes.  Note that blank characters (' ') are not allowed.  Thus,
the input is processed character by character.

   A
   ------------------>[B]--->(&)----->[C]---->
       ^         |
       |         |
       +---(!)---+                C
                                  -------->(+)------->[A]----+
         +--->(a)---+               |  |         |           |
   B     |--->(b)---|               |  +-->(-)---+           |
   ------+--->[C]-------->          +--->(r)--->(s)--------------->

<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<
#include <iostream>
using namespace std;

void getch(char &ch);
void check(bool b, char *mess,char &ch);
void A(char &ch);
void B(char &ch);
void C(char &ch);

int main()
{char ch;
 getch(ch);
 A(ch);
 cout<<"Successful parse\n";
}
void getch(char &ch)
{cin.get(ch);
 cout<<ch;
}

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

void A(char &ch)
{while(ch=='!')
   getch(ch);
 B(ch);
 check(ch=='&'," '&' expected",ch);
 C(ch);
}

void B(char &ch)
{if(ch=='a' || ch=='b')
   getch(ch);
  else
   C(ch);
}

void C(char &ch)
{if(ch=='r')
  {getch(ch);
  check(ch=='s'," 's' expected",ch);
  }
 else
   {check(ch=='+' || ch=='-'," '+' or '-' expected",ch);
   A(ch);
   }
}
>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>
3.  An "association" consists of a "key" and a "value" (e.g., a dictionary
is a collection of associations, whose keys are the words to be defined, and
the values are the definitions), where the key is set at creation, but the
value may be changed later.  Write a template for an Association class.
It should have sufficient functionality (and need not have any more
functionality) so that the follow code will compile and generate the
indicated output.
      Association <int, double>  y(2,5.6),z(y);
      z.setVal(32.2);
      cout<<y.getKey()<<" "<<y.getVal()<<" "
          << (y<z) << (y.getKey()<z.getKey())
               //both comparisons always produce the same result
          <<" "<<z<<endl;
     //output: 2 5.6 0 0 {key: 2, value: 32.2}
<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<
#include <iostream>
using namespace std;

template <class X,class Y>
class Association
{public:
  Association(const X&a,const Y&b);
  Association(const Association &a);
  void setVal(const Y&a);
  X getKey()const;
  Y getVal()const;
  bool operator<(const Association & a);
  template <class U, class V>
  friend ostream & operator<<(ostream &out,const Association<U,V> & a);
private:
  X key;
  Y value;
};

template <class X, class Y>
Association<X,Y>::Association(const X&a,const Y&b):key(a),value(b){}

template <class X, class Y>
Association<X,Y>::Association(const Association &a):key(a.key),value(a.value){}

template <class X, class Y>
X Association<X,Y>::getKey()const{return key;}

template <class X, class Y>
void Association<X,Y>::setVal(const Y&a){value=a;}

template <class X, class Y>
Y Association<X,Y>::getVal()const{return value;}

template <class X, class Y>
bool Association<X,Y>::operator<(const Association & a){return key<a.key;}

template <class X, class Y>
ostream & operator<<(ostream & out, const Association<X,Y> & a)
{out<<"{key "<<a.key<<", value: "<<a.value<<"}";
return out;
}
>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>
4.  Given the class Rectangle below, write a subclass DisplayRect that adds
the ability to store the color of the rectangle, display the rectangle, and
give its area. Given the class DisplayRect, the code below Rectangle should
compile and produce the indicated output.
     class Rectangle
     {public:
        Rectangle(double w, double h):width(w),height(h){}
        double getWidth()const{return width;}
        double getHeight()const{return height;}
      private:
        double width,height;
     };

  DisplayRect a(2.1,3.0,DisplayRect::RED), b(4,3.1,DisplayRect::BLUE),
                 c(2.9,6.4,DisplayRect::GREEN);
  cout<<a<<endl;   // {Width: 2.1, Height: 3.0, Color: Red}
  cout<<"The area is "<<a.area()<<" = "<<a.getWidth()<<" x "
      <<a.getHeight()<<endl; // The area is 6.3 = 2.1 x 3.0
<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<
#include <iostream>
using namespace std;
class DisplayRect:public Rectangle{
public:
  static const int RED=0, GREEN=1, BLUE=2;
  DisplayRect(double w, double h,int c);
  double area()const;
  friend ostream & operator<<(ostream &out,const DisplayRect &d);
private:
  int color;
  static void check(bool b,char * mess);
};

DisplayRect::DisplayRect(double w, double h,int c):Rectangle(w,h),color(c)
{check(c>=RED && c<=BLUE,"Color out of range");}						
double DisplayRect:: area()const {return getHeight()*getWidth();}

ostream & operator<<(ostream &out,const DisplayRect &d)
{char *col[]={"Red","Green","Blue"};
  out<<"{Width: "<<d.getWidth()<<", Height: "<<d.getHeight()<<", Color: "
     <<col[d.color]<<"}";
  return out;
}

void DisplayRect::check(bool b,char * mess)
{if(!b)
  {cerr<<"ERROR: "<<mess<<endl;
  exit(1);
  }
}
>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>
5. Given the function enig() defined below, state the output when the
code below the function is executed.
  void enig(int a, int &b, int *p, int *&q, char *&t)
  {a=5;
   b=a+2;
   *p=9;
   q=p;
    t+=2;
  }

int x,y,*z,*w;
char f[]="onehour",*g=f;
 x=1;
 y=2;
 z=&x;
 enig(x,y,z,w,g);
 cout<<x<<" "<<y<<" "<<*z<<" "<<*w<<" "<<g<<endl;
<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<
9 7 9 9 ehour
>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>
6.  Given the declarations below, assume that root points to a trinary tree
such that for every Node a<=b, all entries (a and b) in the tree with root
"left" arevall <=a, all entries in the tree with root "middle" are all
between a and b, and the entries in the tree with root "right" are all >=b.
(Don't ask how you would build such a tree). Write a function list()
such that the call list(root) displays to the console the entries in the
tree in ascending order.
  struct Node
  {int a,b;
   *Node left,middle,right;
  };
  struct Node* root;
<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<
#include <iostream>
using namespace std;
struct Node
  {int a,b;
    struct Node *left,*middle,*right;
  };

void list(struct Node *rt){
  if(rt!=NULL)
    {list(rt->right);
    cout<<rt->a<<endl;
    list(rt->middle);
    cout<<rt->b<<endl;
    list(rt->left);
    }
}
>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>
7.  Write a class Less whose only purpose is to reasonably safely determine
whether one string is "less" than another.  Write (only enough) code so that
the following will compile and produce the expected result.  Don't worry
about memory leaks and such.
   cout<< (Less("abalone")<"tuna") << ("tuna"<Less("abalone")
       << (NULL<Less("one")) << (Less("two")<NULL) <<endl;  //output: 1010
<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<
#include <iostream>
using namespace std;

class Less
{public:
  Less(char * x){str=x;}
  friend bool operator < (const Less &a, const Less &b);
private:
  char * str;
};


bool operator < (const Less &a, const Less &b){
  if(a.str==NULL && b.str==NULL || b.str==NULL)
    return false;
  return a.str==NULL || strcmp(a.str,b.str)<0;
}
>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>
8. Assume Lex is defined as in class.  Write a function A that parses a line
of text and generates the corresponding MACH1 code, storing the code in a
file, where the text is supposed to satisfy the syntax of the diagram below.
If we have    ofstream fin("afile");
]             Lex lex(cin,cout);
              ofstream code("CODE");
the call to A() should be A(lex,code).  Assume that upon entry lex.newLine()
has been called but the first symbol on the new line has not been retrieved
with a call to lex.next().  For example, if the line read
2 + 3 + 4
A() should generate the code that computes the sum of 2, 3, and 4.
Recall the MACH1 operations   READ(0), WRITE(1), LOAD(2), STORE(3), CLEAR(4),
ADD(5), SUB(6), MUL(7), DIV(8), ADDIMMED(9), SUBIMMED(10), MULIMMED(11),
DIVIMMED(12), JUMPLE(13), JUMPGE(14) HALT(15).

        A
        --------[NUMBER]-------------------------->
                           ^                |
                           |                |
                           +--[NUMBER]--(+)-+
<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<
void check(bool b,char *mess){
  if(!b){
    cerr<<" <--ERROR: "<<mess<<endl;
    exit(1);
  }
}

void getAnum(Lex &lex,ostream &code,int &sym)
{
 check(sym==Lex::NUMBER," a number expected");
 check(lex.getValue()<512,"Value out of range");
 code<<9<<" "<<lex.getValue()<<endl;  //add the number
 sym=lex.next();
}

void A(Lex & lex,ostream & code)
{int sym;
 code<<"4 0"<<endl;  //clear
 sym=lex.next();
 getAnum(lex,code,sym);
 while(sym==Lex::SPLUS){
   sym=lex.next();
   getAnum(lex,code,sym);
 }
 check(sym=Lex::EOLN,"End of line expected");
}