Fall 2000 PIC 10b HW4 Solutions Page

Return to homework page.

//
// File: pic10bhw4file1.h
//
// Contents: Contains interface for the Stack class.
//
//


#ifndef STACK_H
#define STACK_H


template <class Item>
class Stack
{
   public:
	Stack(int s); //constructor creates a stack whose array has s many
		      //Item's.

	~Stack(); //destructor frees up memory used by Stack's array.

	void push(Item i); // pushes the Item onto the top of the Stack.

	Item pop(); // pops one Item from the Stack.

	Item peek(); // returns the tops Item on the Stack but does not delete
             		// delete it from the stack.

	bool empty() const; //returns true if Stack empty.

	bool full() const; //returns true if Stack full.

   private:
	int top; // array index of top of Stack.

	int maxSize; // how many elements the Stack's array can hold.

	Item *array; // where Items stored in Stack.
 	
};

#endif

//
// File: pic10bhw4file2.cpp
//
// Contents: Contains implementations of the Stack Class.
//
//

#ifndef STACK_CPP
#define STACK_CPP

#include<iostream>
#include<cstddef>
#include<cstdlib>
#include "Stack.h"

// Member Function name: Stack(int size)
//
// Purpose:  constructor creates a stack whose array has s many item     
//
// Known Bugs: none

template<class Item>
Stack<Item>::Stack(int size)
{

	array = new Item[size];
	if(array == NULL)
	{
		cerr <<"Out of memory\n";
		exit(1);
	}	
	maxSize=size;
	top=0;
}


// Member Function name: ~Stack()
//
// Purpose:  destructor frees up memory used by Stack's array.             
//
// Known Bugs: none
template<class Item>
Stack<Item>::~Stack()
{
	delete [] array;
}


// Member Function name: push(Item i)
//
// Purpose: pushes the Item onto the top of the Stack.                    
//
// Known Bugs: none
template<class Item>
void Stack<Item>::push(Item i)
{
	if(full())
	{
		cerr<<"Stack overflow.\n";
		exit(1);
	}

	array[top++] = i;
}

// Member Function name: pop()
//
// Purpose: pops one Item from the Stack.   
//                    
// Known Bugs: none
template<class Item>
Item Stack<Item>::pop()
{
	if(empty())
	{
		cerr<<"Stack underflow.\n";
		exit(1);
	}
	
	return array[--top];
}

// Member Function name: peek()
//
// Purpose:  returns the tops Item on the Stack but does not delete it 
//                    
//
// Known Bugs: none
template<class Item>
Item Stack<Item>::peek()
{
	if(empty())
	{
		cerr<<"Peek of empty stack.\n";
		exit(1);
	}
	
	return array[top];
}

// Member Function name: empty() 
//
// Purpose: returns true if Stack has no elements.  
//                    
// Known Bugs: none
template<class Item>
bool Stack<Item>::empty() const
{
	return top <= 0;
}

// Member Function name: full()
//
// Purpose: returns true if Stack can hold no more elements.   
//                    
// Known Bugs: none
template<class Item>
bool Stack<Item>::full() const
{
	return top>=maxSize;
}

#endif

//
// File: pic10bhw4file3.cpp
//
// Contents: Contains the main driver program that check whether a string
//           has matching ()'s, and []'s
//


#include<iostream>
#include<cstddef>
#include<cstdlib>
#include"Stack.cpp"

int GetInput(char input[]); //get a string of less than 256 characters
                          //from the user and stores them in input. 
                          //the int returned how many characters
                          //till the first carriage return

bool CheckValid(const char input[], int size); //checks if the characters
                         // in the array input use () and [] in a legitimate
                         // C++ way. The length of input is size.

// Function name: main()
//
// Purpose:  driver program. gets a string from the user than check to see 
//           it it uses (), [] correctly then allows another string to
//           be tested.         
//
// Known Bugs: none

int main()
{
	int size;
	char input[256], tmp, tmp2;
	bool flag=true;

	while(flag)
	{

		cout << "Please enter a string to test:\n";
		size = GetInput(input);

		if(CheckValid(input, size))
		{
		    cout << "\nThat string used [] and () correctly\n";
		}
		else
		{
		   cout << "\nThat string did not used [] and ()"
			     << " correctly\n";
 		}
		cout << "To test another string type y/Y < ret >\n";
		cin.get(tmp);
		cin.get(tmp2);
		if(tmp != 'y' && tmp != 'Y') flag =false;

	}
	return 0;
}

// Function name: GetInput
//
// Purpose: get a string of less than 256 characters
//          from the user and stores them in input. 
//          the int returned how many characters
//          till the first carriage return  
//                    
// Known Bugs: none

int GetInput(char input[])
{
	int cnt=0;
	char tmp='0';
	
	while(tmp != '\n')
	{
		cin.get(tmp);
		if(tmp != '\n') input[cnt]=tmp;
		cnt++;
	}
	return cnt; 
}

// Function name: CheckValid
//
// Purpose: checks if the characters
//          in the array input use () and [] in a legitimate
//          C++ way. The length of input is size.                     
//
// Known Bugs: none

bool CheckValid(const char input[], int size)
{
	Stack<char> s(size);
	char tmp, tmp2;

	for(int i=0; i < size; i++)
	{
		tmp = input[i];
		switch(tmp)
		{
			case '[':
			case '(':
			    s.push(tmp);
			    break;

			case ')':
			case ']':
			   if(s.empty()) return false;
			   tmp2 = s.pop();
			   if((tmp == ')' && tmp2 == '[') ||
			      (tmp == ']' && tmp2 == '(')) 
                                       return false;   
		}
	}

	return s.empty();
}

//
// File: pic10bhw4file4.h
//
// Contents: Contains interface for the Randomized Queue class.
//
//

#ifndef RQUEUE_H
#define RQUEUE_H


template <class Item>
class RQueue
{
   public:
	RQueue(int s); //constructor creates a stack whose array has s many
		      //Item's.

	~RQueue(); //destructor frees up memory used by RQueue's array.

	void insert(Item i); // pushes the Item onto the RQueue.

	Item remove(); // does a randomized remove of one Item from the RQueue.


	bool empty() const; //returns true if RQueue empty.

	bool full() const; //returns true if RQueue full.

   private:
	int top; // array index of top of RQueue.

	int maxSize; // how many elements the RQueue's array can hold.

	Item *array; // where Items stored in RQueue.
 	
};

#endif

//
// File: pic10bhw4file5.cpp
//
// Contents: Contains implementations of the Randomized Queue Class.
//
//

#ifndef RQUEUE_CPP
#define RQUEUE_CPP

#include<iostream>
#include<cstddef>
#include<cstdlib>
#include<ctime>
#include "RQueue.h"

// Member Function name: RQueue(int size) 
//
// Purpose:constructor. creates an RQueue able to store size many Items       
//
// Known Bugs: none

template<class Item>
RQueue<Item>::RQueue(int size)
{

	array = new Item[size];
	if(array == NULL)
	{
		cerr <<"Out of memory\n";
		exit(1);
	}	
	maxSize=size;
	top=0;

}

// Member Function name: ~RQueue()
//
// Purpose: frees up memory used by RQueue's storage array                     
//
// Known Bugs: none

template<class Item>
RQueue<Item>::~RQueue()
{
	delete [] array;
}


// Member Function name: insert(Item i)
//
// Purpose: inserts the Item i into the RQueue                     
//
// Known Bugs: none

template<class Item>
void RQueue<Item>::insert(Item i)
{
	if(full())
	{
		cerr<<"RQueue overflow.\n";
		exit(1);
	}

	array[top++] = i;
}

// Member Function name: remove()
//
// Purpose: selects one Item at random from RQueue and removes it             
//
// Known Bugs: none

template<class Item>
Item RQueue<Item>::remove()
{
	int index;
	Item tmp;

	if(empty())
	{
		cerr<<"RQueue underflow.\n";
		exit(1);
	}
	
	index = (int) (maxSize*rand()/(RAND_MAX+1.0));  

	tmp = array[index];
	array[index]=array[--top];

	return tmp;
}


// Member Function name: empty()
//
// Purpose: returns true if 0 items stored in RQueue 
//                    
// Known Bugs: none

template<class Item>
bool RQueue<Item>::empty() const
{
	return top <= 0;
}

// Member Function name: full()
//
// Purpose: returns true if RQueue has maxSize many Items stored             
//
// Known Bugs: none

template<class Item>
bool RQueue<Item>::full() const
{
	return top>=maxSize;
}

#endif

//
// File: pic10bhw4file5.cpp
//
// Contents: Contains the main driver program that let's user insert edges
//           into a randomized queue, removes the edges to make
//           a connectivety array  using weighted quick union
//           and let's user determine if two vertices are connected
//
//

#include<iostream>
#include<cstddef>
#include<cstdlib>
#include"RQueue.cpp"

//
// Global constants and struct definitions
//

static const int GRAPH_SIZE= 10; //Stores max number of vertices for graphs
                                 // that can be input

struct Edge 
{
	int left;
	int right;
}; // struct for the edge of a graph.


void GetEdges(RQueue<Edge>& r); // gets the edges of the graph from user
                                      // into the randomized queue r

int GetNumber(int lo, int hi); // reads one number from user between lo and hi

void WQUnion(RQueue<Edge>& r, int graph[], int size);
        // removes edges one at a time from r and uses them to make
        // the connectivety array graph[] using weighted quick union algorithm 

void PrintGraph(int graph[], int size);
        // prints the connectivety array stored in graph[].

bool IsConnected(int node1, int node2, int graph[]);
       // checks if node1 and node2 are connected in graph[].

// Function name: main
//
// Purpose: driver program. gets edges one at a time from user inserting
//          them into a randomized queue. It then removes edges from queue
//          one at a time and uses them to build a conenctivety array
//          of the graph given by these edges. It then prints out this
//          array and allows the user to enter vertices to check if
//          they are connected.   
//                    
// Known Bugs: none

int main()
{
	RQueue<Edge> r(GRAPH_SIZE*GRAPH_SIZE);

	int g[GRAPH_SIZE], node1, node2;
	char tmp;

	bool flag=true;

	cout<< "Graph Connectivety Program.\n"
	    << "===========================\n\n"
	    << "Please enter the edges of your graph "
	    << "one by one.\n";
	
	GetEdges(r);

	WQUnion(r,g, GRAPH_SIZE);

	cout << "\nThe array representing connectivety for the graph\n"
             << "you just entered is:\n\n";

	PrintGraph(g, GRAPH_SIZE);

	cout << "\n\nNow let's use this array to check if two vertices\n"
	     << "are connected.\n\n";

	while(flag)
	{
	  cout << "Enter a first node:\n";

	  node1 = GetNumber(0,GRAPH_SIZE-1);

	  cout << "Enter a 2nd node:\n";

	  node2 = GetNumber(0,GRAPH_SIZE-1);	 

	  if(IsConnected(node1,node2,g))
	  {
		cout<< "Those two nodes were connected in the graph.\n";
	  }
	  else
	  {
		cout<< "Those two nodes weren't connected in the graph.\n";
	  }

	  cout<< "Type y/Y < ret >  to test two other nodes.\n";
	  cin >>tmp ;
	  if(tmp != 'y' && tmp != 'Y') flag =false;
	}
	return 0; 
}

// Function name: GetNumber
//
// Purpose: gets a number from the user between values lo and hi  
//                    
//
// Known Bugs: none

int GetNumber(int lo, int hi)
{
	int num;

	do
	{
	  cout 
           << "Please enter a number between "
           << lo << " and " << hi
               <<"\n"; 	  
          cin >> num;
	} while(num<lo || num >hi);

	return num;
}

// Function name: GetEdges
//
// Purpose: gets the edges of the graph from user
//          into the randomized queue r
//
// Known Bugs: none

void GetEdges(RQueue<Edge>& r)
{
	Edge e;

	bool flag = true;
	char tmp;

	while(flag)
	{

	  cout << 
            "Enter the first node of the edge you are inserting:\n";

	  e.left = GetNumber(0,GRAPH_SIZE-1);

	  cout << "Enter the 2nd node of the edge you are inserting:\n";

	  e.right = GetNumber(0,GRAPH_SIZE-1);

	  r.insert(e);

	  cout<< "Type y/Y < ret >  to enter another edge.\n";
	  cin >> tmp;
	  if(tmp != 'y' && tmp != 'Y') flag =false;

	}
}

// Function name: WQUnion
//
// Purpose:  removes edges one at a time from r and uses them to make   
//           the connectivety array graph[] using weighted quick union
//           algorithm
//                     
// Known Bugs: none

void WQUnion(RQueue<Edge>& rqueue, int graph[], int size )
{
	Edge e;
	int i, l,r;

	int sz[size];	

	for(i =0; i < size ; i++)
		{ graph[i]=i; sz[i]=1;}

	while(!rqueue.empty())
	{
		e=rqueue.remove();
		for(l=e.left; l != graph[l]; l=graph[l]);
		for(r=e.right; r != graph[r]; r=graph[r]);

		if(l == r) continue;
		if(sz[l] < sz[r])
			{graph[l] = r; sz[r] += sz[l];}
		else
			{graph[r] = l; sz[l] += sz[r];}
	}
}

// Function name: PrintGraph 
//
// Purpose: prints out the connectivety array given in graph.                
//
// Known Bugs: none

void PrintGraph(int graph[], int size)
{
	cout <<"Node\t\tParent\n";
	for(int i=0; i <size; i++)
	{
		cout << i<<"\t\t"<< graph[i] << endl;
	}
}

// Function name: IsConnected
//
// Purpose:  uses the connectivety array to check if node1 and node2 are
//           connected. If connected returns true.                   
//
// Known Bugs: none

bool IsConnected(int node1, int node2, int graph[])
{
	for(; node1 != graph[node1]; node1 =graph[node1]);
	for(; node2 != graph[node2]; node2 =graph[node2]);

	return node1 == node2;
}