For this assignment you will implement stacks and queues ADT. A stack and a queu
ID: 3806324 • Letter: F
Question
For this assignment you will implement stacks and queues ADT. A stack and a queue are the same if they have the same number of elements and the elements at the corresponding positions are the same. The program also outputs whether the elements do have the same matching group symbols. Matching symbols are (,), {,}, [,], The program displays a menu on the screen allowing the user to enter the elements of stack and queue. The program terminates when the user enters 9. Validations: The program accepts only integer data type when selecting from the menu (1 or 9). Everything else should be rejected with an invalid option message. *** Welcome to My stack/Queue Program *** The function of this program is to: Validate that a stack and a queue is identical. Stacks/queues are same if they have the same number of elements, symbols, and the their elements and symbols at the corresponding positions are the same. The program also outputs whether the elements do have the same matching group symbols. Select from the following menu Enter Stack/Queue Values. Terminate the program. 1 Enter Stack Values terminated by; 5+(12+7)/8-2*9; Enter Queue Values terminated by; 5+(12+7)/8-2*9; Stack and Queue are identical First Expression does have matching grouping symbols. Select from the following menu Enter Stack/Queue Values. Terminate the program. 1 Enter Stack Values terminated by; 5+{12 +7 >/8 - 2*9; Enter Queue Values terminated by; 5 + {12 + 7 >/8 - 2*9; Stack and Queue are identical First Expression does not have matching grouping symbols.Explanation / Answer
#include <iostream>
#include <list>
#include <sstream>
#include <string>
using namespace std;
template <typename T> //to enable stacks of any data type
class Stack //implement a stack that the user adds elements to
{
private:
list<T> stackList; //list contains values of the stack
int stackSize; //number of elements in the stack
T front; //element at the front of the list
T rear; //element at the back of the list
public:
Stack(); //constructor
T getFront(); //get element at front of the stack
int getSize(); //get stackSize
bool isEmpty(); //true if there are no elements in the stack
void makeEmpty(); //empty the stack
void pop(); //remove front element from stack
void push(T); //add element to front of the stack
};
/*******************************************************************************
function: constructor, sets size to 0
*******************************************************************************/
template <typename T>
Stack<T>::Stack()
{
stackSize = 0; //set stackSize to 0
}
/*******************************************************************************
function: get element at front of the stack
return:
stackList.front(): element at front of the stack
********************************************************************************/
template <typename T>
T Stack<T>::getFront()
{
return stackList.front(); //get element at front of stack
}
/*******************************************************************************
function: gets the number of elements in the stack
return:
stackList.size(): number of elements in the stack
*******************************************************************************/
template <typename T>
int Stack<T>::getSize()
{
return stackList.size(); //return number of elements in the stack
}
/*******************************************************************************
function: determine whether the stack has any elements or not
return:
stackList.empty(): true if there are no elements, false otherwise
*******************************************************************************/
template <typename T>
bool Stack<T>::isEmpty()
{
if( stackList.empty() )
return true; //no elements in the stack
else
return false; //there is at least one element in the stack
}
/*******************************************************************************
function: clear the stack of all elements
*******************************************************************************/
template <typename T>
void Stack<T>::makeEmpty()
{
if( !stackList.empty() ) //only empty if there are elements
{
stackList.clear(); //clear the stack
stackSize = 0; //reset size to 0
}
}
/*******************************************************************************
function: remove an element from the front of the stack
*******************************************************************************/
template <typename T>
void Stack<T>::pop()
{
stackList.pop_front(); //remove element from the stack
stackSize--; //decrease size by one
front = stackList.front(); //change the front element
}
/*******************************************************************************
function: add an element to the front of the stack
arguement:
val: value to be added to the stack
*******************************************************************************/
template <typename T>
void Stack<T>::push(T val)
{
stackList.push_front(val); //add element to the stack
stackSize++; //increase the size by 1
front = val; //change the front to reflect the increase
}
template <typename T> //enables a queue of any data type
class Queue //implement a queue that the user adds element to
{
private:
list<T> queueList; //list holds the elements in the queue
int queueSize; //number of elements in the queue
T front; //element at the front of the queue
T rear; //element at the back of the queue
public:
Queue(); //constructor
void dequeue(); //removes element from back of queue
T getFront(); //get the element at the front of the queue
T getRear(); //get the element at the back of the queue
int getSize(); //get the number of elements in the queue
void enqueue(T); //add element to the front of queue
bool isEmpty(); //determine whether queue has any elements or not
void makeEmpty(); //clear the queue of all elements
};
/*******************************************************************************
function: constructor, sets size to 0
*******************************************************************************/
template <typename T>
Queue<T>::Queue()
{
queueSize = 0; //set size to 0
}
/*******************************************************************************
function: remove element at back of the queue
*******************************************************************************/
template <typename T>
void Queue<T>::dequeue()
{
if( !queueList.empty() ) //only empty queue while there are elements
{
queueList.pop_back(); //decrease queue by 1
queueSize--; //decrease size by 1
rear = queueList.back(); //change rear to reflect the decrease
}
return;
}
/*******************************************************************************
function: get the element at the front of the queue
return:
queueList.front(): element at the front of the queue
*******************************************************************************/
template <typename T>
T Queue<T>::getFront()
{
return queueList.front(); //get element at the front of the queue
}
/*******************************************************************************
function: get the element at the back of the queue
return:
queueList.back(): element at the back of the queue
*******************************************************************************/
template <typename T>
T Queue<T>::getRear()
{
return queueList.back(); //return element at the back of the queue
}
/*******************************************************************************
function: get the number of elements in the queue
return:
queueList.size(): number of elements in the queue
*******************************************************************************/
template <typename T>
int Queue<T>::getSize()
{
return queueList.size(); //return number of elements in the queue
}
/*******************************************************************************
function: add an element to the front of the queue
*******************************************************************************/
template <typename T>
void Queue<T>::enqueue(T val)
{
queueList.push_front(val); //add element to queue
queueSize++; //increase size by 1
if( queueSize == 1 ) //set the front and rear elements to the first element
{
front = val; //set front element to first element pushed
rear = val; //set rear element to first element pushed
}
}
/*******************************************************************************
function: determine whether the queue is empty or not
return:
queueList.empty(): true if there are no elements, false otherwise
*******************************************************************************/
template <typename T>
bool Queue<T>::isEmpty()
{
if( queueList.empty() ) //determine if there are elements or not
return true; //true if there are no elements
else
return false; //false if there are elements
}
/*******************************************************************************
function: clear the queue of all elements
*******************************************************************************/
template <typename T>
void Queue<T>::makeEmpty()
{
if( !queueList.empty() ) //clear queue if there are elements to be cleared
{
queueList.clear(); //clear the queue of all elements
queueSize = 0; //reset size to 0
}
return;
}
//function prototypes
void outputIntro(); //outputs welcome message and intro for user
void outputMenu(); //outputs the menu and allows the user to select a choice
int checkMenuChoice( string menuChoice ); //checks whether user choice is valid
//determine whether the stack and queue are identical
bool isIdentical( Stack<char> stackToCompare, Queue<char> queueToCompare );
int main()
{
Stack<char> stackToCompare; //stack to compare with queue
Queue<char> queueToCompare; //queue to compare with stack
string menuChoice; //choice user selects from menu
string SQInput = ""; //stores stack/queue vals during getline
int choice = 0; //valid choice user selects from menu
bool choiceIsValid = true; //true if the user's choice is valid
//bool stackIsValid, queueIsValid; //true if the stack/queue have good inputs
outputIntro(); //output introduction to user
do //until program is terminated
{
do //allow user to choose whether to input values or terminate program
{
outputMenu(); //output menu
cin >> menuChoice; //receive user's choice
cout << endl; //formatting endl
choice = checkMenuChoice( menuChoice ); //check if choice is valid
} while( choice != 1 && choice != 9 );
if( choice == 1 ) //allow user to input values and verify if equal
{
//clear the stack and queue for next values
stackToCompare.makeEmpty();
queueToCompare.makeEmpty();
//enter stack values
cout << "Enter stack values and append with a semicolon: ";
getline(cin, SQInput, ';'); //get values from user
for( int i = 1; i < SQInput.size(); i++ )
stackToCompare.push(SQInput[i]);
//enter queue values
cout << "Enter queue values and append with a semicolon: ";
getline(cin, SQInput, ';'); //get values from user
for( int i = 1; i < SQInput.size(); i++ )
queueToCompare.enqueue(SQInput[i]);
//output whether they are identical or not
cout << endl;
cout << "The stack and the queue are ";
//output whether the stack and queue are valid
if( !isIdentical( stackToCompare, queueToCompare) )
cout << "not ";
cout << "identical." << endl << endl;
}
} while( choice != 9 ); //while user does not wish to terminate
//output end message (Gina Chiodo is the only one who did work)
cout << "*** The program written by Gina Chiodo has terminated. ***";
cout << endl << endl;
return 0;
}
/*******************************************************************************
function: output the welcome message and introduction for the user
*******************************************************************************/
void outputIntro()
{
//output welcome message
cout << endl;
cout << "*** Welcome to the Stack/Queue Program ***";
cout << endl << endl;
//output introduction
cout << "The function of this program is to validate whether a stack and"
<< endl
<< "are identical. They are identical if they have the same number of"
<< endl
<< "elements stored in equivalent positions.";
cout << endl << endl;
return;
}
/*******************************************************************************
function: output the menu for the user
*******************************************************************************/
void outputMenu()
{
//output the menu for the user
cout << "Select from the following choices:"
<< endl
<< "1: Enter the stack and queue values"
<< endl
<< "9: Terminate the program ";
return;
}
/*******************************************************************************
function: make sure that the user entered 1 or 9 from the menu
argument:
input: user input from menu options
return:
choice: the int-converted user input
*******************************************************************************/
int checkMenuChoice( string input )
{
int choice = 0; //holds integer-converted value inputted by user
stringstream convert( input ); //convert string to int
//if input is alphabetic or is not 1 or 9, output error message
if( !( convert >> choice ) || ( choice != 1 && choice != 9 ) )
cout << "ERROR: invalid input" //output error message
<< endl << endl;
return choice;
}
/*******************************************************************************
function: determines whether the stack and queue are identical
arguments:
stackToCompare: stack to compare to the queue
queueToCompare: queue to compare to the stack
return:
identical: true if the stack and queue are identical; false otherwise
*******************************************************************************/
bool isIdentical( Stack<char> stackToCompare, Queue<char> queueToCompare )
{
bool identical = true; //true if the stack and queue are identical
int stackSize = stackToCompare.getSize(); //number of elements in stack
int queueSize = queueToCompare.getSize(); //number of elements in queue
char stackArray[stackSize], queueArray[queueSize]; //hold values of stack
//and queue for comparing
if( stackSize != queueSize )
identical = false; //false if sizes aren't equal
else
{
//place elements in stack in array
for( int i = stackSize; i > 0; i-- )
{
stackArray[i-1] = stackToCompare.getFront(); //put front in array
stackToCompare.pop(); //remove element to get to next element
}
//place elements in stack in array
for( int i = 0; i < queueSize; i++ )
{
queueArray[i] = queueToCompare.getRear(); //put rear in array
queueToCompare.dequeue(); //remove element to get to next element
}
//compare each element in the arrays
for( int i = 0; i < stackSize; i++ )
{
if( stackArray[i] != queueArray[i] )
{
identical = false; //false if elements aren't equal
}
}
}
return identical;
}
Related Questions
drjack9650@gmail.com
Navigate
Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.