use this code template:

#include

#include

#include

#include

using namespace std;

#define INPUT$\_$FILE "test.txt$"$

int main$()\{$

ifstream f$($INPUT$\_$FILE$)$;

string tmp;

bool failed $=$ false;

char item;

if $(!$f$.$good$())\{$

cout $<<$ "Invalid file." $<<$ endl;

exit $(-1)$;

$\}$

while $($true$)\{$

$//$ Read the number of lines in the next test

getline$($f$,$ tmp$)$;

$//$ If we are at end$-$of$-$file, the program exits

if $($f$.$eof$())$

return $(0)$;

$//$ Assume the stack test has not failed

failed $=$ false;

$//$ Convert and loop

int nl $=$ atoi$($tmp$.$c$\_$str$())$;

while $($nl$--)\{$

$//$ Read the command

getline$($f$,$ tmp$)$;

char op $=$ tmp$[0]$;

$//$ Read the string word

$//($index $0$ contains the command, index $1$ is a space$)$

string word $=$ tmp$.$substr$(2)$;

cout $<<$ "Operation: $"<<$ op $<<$ endl;

cout $<<$ "Word: $"<<$ word $<<$ endl;

$\}$

$\}$

return $0$;

$\}$

and complete the template using these instructions: This program involves testing whether a sequence of operations is in LIFO order, using a C$++$ stack with strings.

Imagine there is an "unknown" data structure that holds a collection of strings. It has two operations defined as follows:

i abc insert the string abc

r abc remove a string $($returning the value abc$)$

How this data structure works is mysterious. Given a sequence of operations, it may operate like a LIFO stack, or it may not.

Your program must determine whether or not it is operating as a stack given a series of operations and the corresponding returned strings.

Program Input and Output

Input File Format

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 $<=50).$ Following the operations defined in the above table, each of of the next n lines is either an $\text{'}$i$\text{'}$ command followed by a string $($which inserts that string$)$ or a $\text{'}$r$\text{'}$ command followed by a string which means the command retrieves that string. Each string will be a word with a minimum length of $1$ and a maximum length of $10.$ The input is terminated by reaching end$-$of$-$file $($EOF$).$

At your option, your code may use anything in the standard C$++$ library $--$ including the STL $($Standard Template Library$)$ stack container. If you use the STL stack, be sure to review the documentationLinks to an external site. on how to use it in a program. You can also use the Stack.h template in this module.

Program Output

For each test case, output one of these lines:

stack

not stack

which will indicate whether or not the series of operations are behaving like a stack $($in LIFO order$).$

Sample Input

Create a text file with the following lines and use it as input into your program.

$4$

i cat

i dog

r dog

r cat

$6$

i sunshine

i apple

i street

r apple

r street

r sunshine

$2$

i red

r red

$3$

i blue

i green

r green

Sample Output

When your program reads the above input file, it should output these four lines only: stack

not stack

stack

not stack

Explanation of the Sample Output

In the first case, 'cat' and 'dog' were pushed onto the stack. Then, a remove $(\text{'}$r$\text{'})$ operation retrieved the string 'dog', then the string 'cat'. This follows the correct ordering of a stack $($last in$,$ first out$),$ so the program should output:

stack

In the second case, 'sunshine', 'apple' and 'street' were inserted. Then a remove operation retrieved the string 'apple'. If the data structure were a stack, the first remove operation should have retrieved 'street' $($this was the most recent string inserted$).$ At that point we know that this is not a stack, so program outputs:

not stack

At this point your code can skip the remaining lines in that test case and proceed to the next one in the file.

The third case is a simple single insert followed by a remove of the same string, which conforms to how a stack would operate $($or$,$ well, it doesn't violate LIFO order rules$)$ so the output should be:

stack

The fourth case inserts two strings, then removes one in the correct order $(\text{'}$green$\text{'}$ comes out first$).$ The test case ends and the stack is not empty, so the program outputs:

not stack

Other Notes

Here are some other assumptions you can make when writing the code:

Strings are not unique within a test case. For example, the same string may be pushed onto the stack multiple times.

There will be no invalid test lengths. You can assume all of the test lengths line up with the end of the file.

There will be no invalid commands $($all commands will be either $\text{'}$i$\text{'}$ or $\text{'}$r$\text{'}).$

The stack must be empty at the end of a test. If it is not empty, output 'not stack'.

Add the filename of the input file directly into your code. For example, you can use a 'const string'. Do not prompt for the filename.

Be sure that your code pass