CSE 109 Finaly Exam  Saturday  5 May 2007   4:00-7:00 PM
>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>SUGGESTED ANSWERS<<<<<<<<<<<<<<<<<<<<<<<
1.  Assume the definition of class Link below, meant to be used to construct
a linked list ending in a NULL pointer.  Write a function remove() that removes
the first link it encounters containing a given number.  If the number is not
in the list, remove() does nothing. Give the declaration   Link *hd; the call
to remove the first link, if any, containing 10 would look like remove(hd,10).
class Link{
public:
  int j;
  Link *next;
};
>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>
void remove(Link *&h,int t){
  Link * temp;
  if(h==NULL)
    return;
  if(h->j==t){
      temp=h;
      h=h->next;
      delete temp;  //avoid memory leak
  }
  else
      remove(h->next,t);
}
<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<
2. Write a template for the class Magnitude that stores an instance of some
variable or object for which "<", "==", and "<<" are defined. Instances of the
class should respond to the binary operators "<", "==", and "<=".  Below is
some sample code.
  Magnitude <int> m(5), n(3);
  cout<<"("<<m<<"=="<<n<<")=="<<(m==n)<<endl; //OUTPUT: (5==3)==0
>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>
template <class C>
class Mag{
public:
  Mag(const C&c=NULL);
  template <class A>
  friend bool operator<(const Mag<A>&a, const Mag<A> &b);
  template <class A>
  friend bool operator<=(const Mag<A>&a, const Mag<A> &b);
  template <class A>
  friend bool operator==(const Mag<A>&a, const Mag<A> &b);
  template <class A>
  friend ostream & operator<<(ostream &out,const Mag<A> &m);
private:
  C x;
};

template <class A>
Mag<A>::Mag(const A &c):x(c){}

template <class A>
 bool operator<(const Mag<A>&a, const Mag<A> &b){
   return a.x<b.x;
}
template <class A>
bool operator<=(const Mag<A>&a, const Mag<A> &b){
  return a.x<b.x || a.x==b.x;
}
template <class A>
bool operator==(const Mag<A>&a, const Mag<A> &b){
  return a.x==b.x;
}
template <class A>
ostream & operator<<(ostream &out,const Mag<A> &m){
  out<<m.x;
  return out;
}
<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<
3.  This questions refers to a language with the syntax given
by the following syntax diagram A and associated diagrams (where
parentheses, (), indicate circles and brackets, [], indicate boxes):

       A                      +--(+)--+
      ---------------->[B]----|--(-)--|--->[C]--->
                              +--(/)--+

       B
      ---------------->(s)->[C]------->

       C
      ---------------->(t)-->[A]-->(u)------->
                 |
                 +---->(u)------------------->
Write a program that reads a single line from the console and determines
whether the characters in the line satisfy the syntax of A.  Spaces and
tabs are not acceptable characters.
>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>
#include <iostream>
using namespace std;

void a(char&ch);
void b(char&ch);
void c(char &ch);
void check(bool b, char *mess);

int main(){
  char ch;
  cout<<"Enter a line of text, and I check its syntax\n";
  cin.get(ch);
  a(ch);
  check(ch=='\n',"EOLN expected");
  cout<<"Good syntax\n";
}
void a(char&ch){
  b(ch);
  check(ch=='+' || ch=='-' || ch=='*',"'+', '-', or '*' expected");
  cin.get(ch);
  c(ch);
}
void b(char&ch){
  check(ch=='s',"'s' expected");
  cin.get(ch);
  c(ch);
}
void c(char &ch){
  check(ch=='t' || ch=='u',"'u' or 't' expected");
  if(ch=='t'){
    cin.get(ch);
    a(ch);
    check(ch=='u',"'u' expected");
  }
  cin.get(ch);
}
void check(bool b, char *mess){
  if(!b){
    cerr<<"ERROR: "<<mess<<endl;
    exit(1);
  }
}
<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<
4.  Given the SLA++ program below, write the corresponding SML program.
Recall the SML opcodes: read(10), write(11), load(20), store(21),
add(30), subtract(31), divide(32), multiply(33), branch(40), branchless(41),
brancheqaul(42), halt(43).
    read x
    read y
    write (y-x)*(3-y)
    halt
    x 0
    y 0
    end
>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>
10021          0   I avoid obvious shortcuts and follow
10022          1     the way SAL++ probably generates code
20022          2  load y
21999          3  push y
20021          4  load x
21998          5  push x
20999          6  get stk+1
31998          7  sub stk
21999          8  pop and store
20023          9  load 3
21998         10  push 3
20022         11  load y
21997         12  push y
20998         13  load stk+1
31997         14  sub stk
21998         15  pop and store
20999         16  load stk+1
33998         17  multiply
21999         18  pop and store
11999         19  write stk
43999         20  halt
0             21  x
0             22  y
3             23  const
END
<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<
5.  Write a program that reads from two text files specified at the command
line and determines whether the two files are identical. If the executable
program is stored in "same", the call would be
    same someFile someOtherFile
The output might look something like
"The files 'someFile' and 'someOtherFile' are identical."
>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>
#include <iostream>
#include <fstream>
using namespace std;

void check(bool b, char *a, char *c="", char *d="");

int main(int ct,char **arg){
  char cha,chb;
  check(ct==3,"Usage: ",arg[0]," <input1> <input2>");
  ifstream a(arg[1]), b(arg[2]);
  check(a.good(),"The file '",arg[1],"' does not exist");
  check(b.good(),"The file '",arg[2],"' does not exist");
  cha=a.get();
  chb=b.get();
  while(a.good() && b.good() && cha==chb){
    cha=a.get();
    chb=b.get();
  }
  check(!a.good() && !b.good(),"The files are not the same");
  cout<<"The files are the same\n";
}

void check(bool b, char *a, char *c, char *d){
  if(!b){
      cerr<<"ERROR: "<<a<<c<<d<<endl;
      exit(1);
  }
}
<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<
6.  Write a class to represent a bank account to which one may make deposits
(with the += operator), from which one may make withdrawals (with the -=
operator), and from which one can get a report of the current balance (with
the method balance()).  Below is some sample code, where the account is
opened with an initial deposit of $50.
  Account x(50);
  x+=23;
  cout<<"The account has $"<<x.balance()<<endl;
      //OUTPUT: The account has $73
  x-=30;
  cout<<"Now the account has $"<<x.balance()<<endl;
      //OUTPUT:  Now the account has $43
>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>
#include <iostream>
using namespace std;

class Account{
public:
  Account(double j=0);
  Account & operator+=(double j);
  Account & operator-=(double j);
  double balance()const;
private:
  double money;
  void check(bool b, char *mess);
};

Account::Account(double j):money(j){
  check(money>=0,"Cannot open with a negative amount");
}

Account & Account::operator+=(double d){
  check(d>=0,"Cannot deposit a negative amount");
  money+=d;
  return *this;
}

Account & Account::operator-=(double d){
  check(d>=0,"Cannot withdraw a negative amount");
  check(money-d>=0,"Cannot overdraw account");
  money-=d;
  return *this;
}

double Account::balance()const{return money;}

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

<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<
7.  Write a subclass of the class Account (see problem 6), called Savings,
that pays interest at some given rate (per month).  An instance of Savings
responds to the message post() by accruing (simple) interest for the given
number of months.  Below is some sample code (where "<<" has been overloaded
for instances of Savings).
   Savings s(0.01),  //open an account with $0 deposit and monthly interest
                     //of 1%
           t(0.015,50); //open an account with $50 deposit and monthly interest
                        //of 1.5%
   s+=1000;
   s.post(10);  //add 10 months of interest (not compounded)
   cout<<s<<endl;  //OUTPUT: Savings(0.01, $1100)
>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>
class Savings:public Account{
public:
  Savings(double intRate=0,double amt=0);
  void post(int m);
  friend ostream & operator<<(ostream & out,const Savings & s);
private:
  double rate;
};

Savings::Savings(double intRate, double amt):Account(amt),rate(intRate){
  check(rate>=0 && rate<=1,"Rate must be between 0 and 1, inclusive");
}

void Savings::post(int m){
  check(m>0,"Must have positive number of months");
  money+=m*rate*money;
}

ostream & operator<<(ostream & out,const Savings & s){
  out<<"Savings("<<s.rate<<", $"<<s.money<<")";
  return out;
}
<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<
8.  Write a C program that compiles with the command   g++ -xc -Wall -Werror
The program should assume the struct below, should read from the console
pairs of positive ints to be stored in an array of the struct, and should then
print the pairs in reverse order, the last pair first.  The program can assume
that all entries are ints, that there are no more than 100 pairs in the list,
and that the list terminates with a negative int.
  struct Pair{
     int a,b;
  };
>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>
#include <stdio.h>
struct Pair{
  int a,b;
  };

void loadList(struct Pair list[],int *n);
void printList(struct Pair list[],int n);

int main(){
  struct Pair list[101];
  int n;
  loadList(list,&n);
  printList(list,n);
  return 0;
}

void loadList(struct Pair list[],int *n){
  *n=0;
  scanf( "%d",&list[*n].a);
  while(list[*n].a>0 && *n<100){
    scanf(" %d",&list[*n].b);
    (*n)++;
    scanf(" %d",&list[*n].a);
  }
}

void printList(struct Pair list[],int n){
  while(n>0){
      n--;
      printf(" %d   %d \n",list[n].a,list[n].b);
  }
}

<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<