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;
}
|