Examination III
Data Structures

1. Write a generic (template) procedure that would sort N elements of the generic array Alpha in descending order using the insert sort.

template <class ItemType>
void InsertSort(ItemType A[], long N)
{ for (int pass = 1; pass < N; pass++)
    { ItemType Temp = A[pass];
      int J = pass;
      while( (J > 0) && (A[J-1] > Temp)) // change < to > for smallest to largest
        {A[J] = A[J-1];
         J--;
        }
      A[J] = Temp;
    }
}

2. Write a procedure that would write N numbers from an array to an output file, with 10 numbers per line.  The parameters of the procedure are the filename, the array, and the number.

    for(int j=0; j < N; j++)
      { F << NumbArray[j];
        if(j % 10 == 9)
          F << endl;
      }

    F.close();
  }

3. Stacks
1. Write a C++ header file that would contain a generic stack declaration.

template <class ItemType>
class stack
{
 public:
  void push( ItemType );
  void pop ();
  ItemType top();

  bool empty();

  stack();
  ~stack();

 private:
  struct node
  {
   ItemType item;
   node *next;
  };

  node* head;

};

#include "stack.cpp"

2. Give the contents of a stack T after the following operations:

T.Push(24);
T.Push(35);
T.Pop();
T.Push(12);
T.Push(15);
T.Pop();
T.Pop();
T.Push(91);
T.Push(48);

head
48
91
24

3. Graphically draw the stack you had in part b.

head ® 48 ® 91 ®  24 ® NULL
 
4. Show, graphically, how you would perform the operation “T.push(75)” on the stack in part c.  Number each of the four steps.

5. Give the implementation of the push operation of part a.

template <class ItemType>
void stack<ItemType>::push(ItemType I)
{ node* Temp;
  Temp = new node;
  (Temp -> next) = head;
  (Temp -> item) = I;
  head = Temp;
}

6. Give the implementation of the empty operation of part a.

template <class ItemType>
bool stack<ItemType>::empty()
{ return (head == NULL);
}

7. Give the implementation of the constructor of part a.

template <class ItemType>
stack<ItemType>::stack()
{  head = NULL;
}

3. Evaluate the following post-fix expressions

1. 5467+-*   answer: -45

2. 5467+-     answer: incomplete expression

3. 5467+-*/   answer: operand error

5. Program to evaluate.  The following is an outline of the main program to evaluate the expressions in a file containing one post-fix expression per line as defined in assignment 7.  Fill in the requested parts with correct code (requests are written in bold).

#include <iostream.h>
#include <fstream.h>

#include "stack.h"

const int OperatorError = -32767;
const int IncompleteError = -32766;
const int IllegalCharacter = -32768;
const int DivisionByZero = -32765;
const int EmptyStack = -32764;
 

int Evaluate( char Expression[] )
{ int count = 0;
  int Operand1, Operand2;
  stack<int> ExpStack;
  while (Expression[count] != '#')
  { switch (Expression[count]) {
        case '0':
  case '1':
  case '2':
  case '3':
  case '4':
  case '5':
  case '6':
  case '7':
  case '8':
  case '9':
   ExpStack.push(Expression[count] - '0');
   break;
  case '+':
   if(!ExpStack.empty()) {
    Operand1 = ExpStack.top();
    ExpStack.pop();}
   else
    return OperatorError;

   if (!ExpStack.empty()) {
    Operand2 = ExpStack.top();
    ExpStack.pop();}
   else
    return OperatorError;

   ExpStack.push(Operand1+Operand2);
   break;

  case '-':
   if(!ExpStack.empty()) {
    Operand1 = ExpStack.top();
    ExpStack.pop();}
   else
    return OperatorError;

   if (!ExpStack.empty()) {
    Operand2 = ExpStack.top();
    ExpStack.pop();}
   else
    return OperatorError;

   ExpStack.push(Operand2-Operand1);
   break;

  case '*':
   if(!ExpStack.empty()) {
    Operand1 = ExpStack.top();
    ExpStack.pop();}
   else
    return OperatorError;

   if (!ExpStack.empty()) {
    Operand2 = ExpStack.top();
    ExpStack.pop();}
   else
    return OperatorError;

   ExpStack.push(Operand1*Operand2);
   break;

  case '/':
   if(!ExpStack.empty()) {
    Operand1 = ExpStack.top();
    ExpStack.pop();}
   else
    return OperatorError;

   if (!ExpStack.empty()) {
    Operand2 = ExpStack.top();
    ExpStack.pop();}
   else
    return OperatorError;

   if (Operand1 != 0)
    ExpStack.push(Operand2/Operand1);
   else
    return DivisionByZero;
   break;

  default:
   return IllegalCharacter;
  }
 

   count ++;
  }
 
  if (!ExpStack.empty()) {
    Operand1 = ExpStack.top();
    ExpStack.pop(); }
  else
   return EmptyStack;

  if (ExpStack.empty())
   return Operand1;
  else
   return IncompleteError;

}  // end Evaluate

void main()
{ char Exp[80];
  fstream InFile, OutFile;
  InFile.open("Test.txt", ios::in);
  OutFile.open("Result.txt", ios::out);
  while( !InFile.eof()) {
    InFile.getline(Exp, 80, '\n');
    int value = Evaluate(Exp);
    if (value == OperatorError)
     OutFile << Exp << " error -- two few operands for operator" << endl;
    else if (value == IncompleteError)
     OutFile << Exp << " error -- expression incomplete" << endl;
    else if (value == IllegalCharacter)
     OutFile << Exp << " error -- illegal character found" << endl;
    else if (value == DivisionByZero)
     OutFile << Exp << " error -- division by zero." << endl;
    else if (value == EmptyStack)
     OutFile << Exp << " error -- no value left on stack at end";
    else
     OutFile << Exp << " has a value of " << value << endl; }

  InFile.close();
 
}

6. Write a complete C++ program that would read 1000 names from the input file “Names.txt” and write the names out onto the screen.  You do not need to use a procedure.  The most efficient code gets the most points.

void main()
  { char Name[80];

    fstream F;
    F.open("Names.txt", ios::in);

    for(int j=0; j<10; j++)
      { F.getline(Name, 80, '\n');
        cout << Name << endl;
      }

    F.close();
  }

7. Insert the following values into a binary search tree.
23 12 7 5 4 30 40 50 60 70 25 27 18 19

8. Give a class declaration for a binary search tree.

  node* rootNode;
  int Size;

  void DeleteTree(node* &);
        void PrintAscending(fstream &, node*);
        void PrintDescending(fstream &, node*);
        void InsertTree(node* &, T);
};