CSE 109 Test 2 Friday 13 March 2012
>>>>>>>>>>>>>>>>>>>>>>SUGGESTED ANSWERS<<<<<<<<<<<<<<<<<<<<<<<<<<<<<
1. Assume the class below is used to construct a binary search tree. Write
a function sum() that EFFICIENTLY returns the sum of the data for all keys
less than or equal to some given value. For example, if Node*root points
to the root of a binary search tree, sum(root,10) would return the sum of
the data in all nodes that have a key of value <=10.
class Node{
public:
  int key;
  double data;
  Node * child[2];
  static const int L=0,R=1;
  Node(int k,double d):key(k),data(d){child[L]=NULL; child[R]=NULL;}
};
========================================================================
double total(Node*rt,int max){
  if(rt==NULL)
    return 0;
  if(max<rt->key)
    return total(rt->child[Node::L],max);
  return rt->data+total(rt->child[Node::L],max)+
              total(rt->child[Node::R],max);
}
===========================================================================
2. Write a C++ program that counts the number of uppercase characters in a
file. Suppose the file was name "text" and the executable code for the
program is stored in "a.out". The call to the program would be "a.out text".
You can assume the function below.
void check(bool b,const char *mess){
  if(!b){
    cerr<<"ERROR: "<<mess<<"\n";
    exit(1);
  }
}
==========================================================================
int main(int count,char **arg){
  ifstream f;
  char ch;
  int ct;
  ct=0;
  check(count==2," Usage: a.out <file>");   
  f.open(arg[1]);
  check(f.good()," Did not open input file");
  ch=f.get();
  while(f.good()){
    if(ch>='A' && ch<='Z')
      ct++;
    ch=f.get();
  }
  cout<<"The file '"<<arg[1]<<"' has "<<ct<<" uppercase letters\n";
}
=========================================================================
3. Write a function a() that parses strings that satisfy the syntax diagram
below, where the parentheses () denote circles, and the square brackets []
denote rectangular boxes. The program below the diagram shows how the
function a() is called. To simplify the problem, assume there are no white
spaces in the string.
a                           +--(2)--+
----------+-----(1)---[a]---|       |----------------->
          |                 +--(3)--+        |
          +-----(2)----------+---------------+
                    ^        |
                    |        |
                    +---(1)--+
void check(bool b,const char *mess){
  if(!b){
    cerr<<"ERROR: "<<mess<<" expected\n";
    exit(1);
  }
}
int main(){
  char ch;
  ch=cin.get();
  a(ch);
  check(!cin.good() || ch=='\n',"eoln");// Message: "eoln or eof expected"
}
=========================================================================
void next(char &ch){
  ch=cin.get();
  if(!cin.good())
     ch='\n';
}
void a(char &ch){
  if(ch=='1'){
    next(ch);
    a(ch);
    check(ch=='2' || ch=='3',"'2' or '3'");
    next(ch);
  }
  else{
    check(ch=='2',"'2'");
    next(ch);
    while(ch=='1')
      next(ch);
  }
}
=========================================================================
4. I want to develop a class Menu that asks a user to choose among various
items in a list. I ask you to start developing the class by writing a
template for the class that behaves as indicated below. Provide nothing
more in the template than what is needed for the code below to function.
int main(){
  int j[]={4,2,3};
  Menu<int> v(j,3);
  cout<<v;
}
/*OUTPUT (NOT INCLUDING THIS LINE OR THE LAST LINE)
1: '4'
2: '2'
3: '3'
*/
==========================================================================
template <class T>
class Menu{
private:
  T*list;
  int ct;
public:
  Menu(T x[],int n);
  template <class Y>
  friend ostream & operator<<(ostream& out, const Menu<Y>&m);
};

template <class T>
Menu<T>::Menu(T x[],int n):ct(n){
  list = new T[ct];
  if(list==NULL){
    cerr<<"Error: heap overflow or bad array size\n";
    exit(1);
  }
  for(int j=0;j<n;j++)
    list[j]=x[j];
}

template <class T>
ostream & operator<<(ostream &out, const Menu<T>&m){
  for(int j=0;j<m.ct;j++)
    out<<(j+1)<<": '"<<m.list[j]<<"'\n";
  return out;
}
=======================================================================