In: Computer Science
In C++, please. Thank you!
Perhaps you remember the popular TV show, Deal or No Deal, with Howie Mandel as the host, that ran several years ago. In honor of the show returning in its original form (and renewed for a fifth season in 2019!) this lab is called Stack or No Stack.
As we studied in Chapter 1, imagine again a bag data structure into which we can insert and remove elements. This bag has two operations, defined as:
1 x | Insert an element (with value x) into the bag |
2 x | Take an element from the bag (the value x) |
This time the bag is somewhat mysterious. Given a sequence of inserts and removals, the bag may operate like a LIFO stack, or it may not.
Your program must guess whether or not the bag is operating as a stack given a series of operations and the corresponding return values.
Program Input
The input to your program will be a series of test cases in a file. Each test case begins with a line containing a single integer n (1 < n < 100). Following the operations defined in the above table, each of of the next n lines is either a type-1 command followed by an integer x (which inserts the value x) or a type-2 command followed by an integer x which means the command retrieves the value x. The value of x is always a positive integer not larger than 100. There will be no ambiguous test cases. In other words, you will be able to fully determine the output based on the input alone. The input is terminated by an end-of-file (EOF).
Your code may use anything in the standard C++ library -- including the STL stack container. This is, of course, optional.
Program Output
For each test case, output one of the following:
stack not stack
which will indicate whether or not the bag is determined to be operating as a stack, given the series of operations.
What to Submit
Please submit a .cpp file which contains your solution to the problem. Your program should take its input from a file. You will want to write some test driver code but you are not required to submit it as part of the assignment Do so only if it is convenient.
How to Earn Full Credit
Your code should compile, run, and pass all of the below test cases.
Code that does not compile or pass at least the below test cases will have points deducted. Your professor has held back a few extra cases that your program must also pass to receive full credit. Your program should output only 'stack' or 'not stack' once per line, with one line for each test case.
Sample Input
Create a file with the following lines and use it as input into your program. Please use at least these as your test cases before submitting your code in Canvas.
4 1 2 1 1 2 1 2 2 6 1 5 1 10 1 12 2 10 2 5 2 12 2 1 8 2 8
Sample Output
stack not stack stack
here is a code for the problem
I am reading the input from file
#include<bits/stdc++.h>
using namespace std;
int main(){
ifstream fin("file");//reads input from the file
string ch;
vector<string>input; // to store values of input that is type
of 1
vector<string>output; //to stroe values of output that is
type if 2
while(fin){ //reading file data
getline(fin, ch); // getting data from fin and writing it to ch
line bt line
cout<<ch<<endl;
if(ch.size()==1){ // when it size of input line 4 in first input
test case
if(output.size()==0) // if output file is empty ie for first
case
continue;
reverse(output.begin(),output.end()); // reversing output , because
stack is LIFO ie last in first out so we will check if they are
same or not
if(input==output){
cout<<"stack"<<endl;
}
else{
cout<<"not stack"<<endl;
}
input.clear();// clearing input and output for next input
output.clear();
}
else{
if(ch[0]=='1'){ //checking type if type 1 or type 2
string data = "";
for(int i = 2;i<ch.size();i++){
data+=ch[i];
}
input.push_back(data); // stroing data for input
}
else {
string data = "";
for(int i = 2;i<ch.size();i++){
data+=ch[i];
}
output.push_back(data); //storing data for output
}
}
}
//its for the last case when file end so that we can check the
output
if(output.size()!=0){
output.pop_back(); //i am removing last element for output because
it is reading it two time in every case ans this
//is the cornor case we have to check.. it might be because of
comiler of what . you must check it once if it working for you or
not
// but its working for me
reverse(output.begin(),output.end());
if(input==output){
cout<<"stack"<<endl;
}
else{
cout<<"not stack"<<endl;
}
}
}
output-file
file image I used to read input
if any doubt. comment below.