Fluent Essays

Objectives    Assignment 09: Applications of Stacks  COSC 2336: Data Structures and Algorithms Fall 2020    • More practice with recursion. • Practice writing some template functions. • Use stack ADT to implement given algorithms. • Practice using Stack class container given as a library in a separate file. • Look at some common applications of stacks.  Description  In this assignment, you will be using the Stack abstract data type we developed for this unit and discussed in our lectures, to implement 4 functions that use a stack data type to accomplish their algorithms. The functions range from relatively simple, straight forward use of a stack, to a bit more complex. But in all 4 cases, you should only need to use the abstract stack interface functions push(), pop(), top(), and isEmpty() in order to successfully use our Stack type for this assignment and the function you are asked to write.  NOTE You are to use the Stack ADT abstraction give to you for this assignment. If you are familiar with STL stack containers, you are not to use them for this assignment. Part of the assignment is to look over and learn the Stack ADT implementation we give you here based on our textbook Stack examples.  Setup  For this assignment you will be given the following files:    File Name  assg09-tests.cpp assg09-stackfun.hpp assg09-stackfun.cpp Stack.hpp  Stack.cpp  Description  Unit tests for the member functions you are to write. Header file where function prototypes for the functions you write using stacks should go. Implementaiton file, the implementation of the 4 functions you write for this assignment go here. Header file defining a Stack ADT for use in implementing the functions for this assignment. You will not make any modifications in this file, you are only going to be using the given Stack. Implementation file for the Stack ADT template class. You also do not make any changes in this file either.    Set up a multi-file project to compile the .cpp source files and run them as shown for the class. The Makefile you were given should be usable to create a build project using the Atom editor as required in this class. You will only be adding code to the assg09-stackfun.[hpp|cpp] file in this assignment. The Stack.[hpp|cpp] file contains a Stack container. You are to use this Stack ADT for the 4 functions you are to write for this assignment.    1     The general approach you should take for this assignment, and all assignment is:    Set up your project with the given starting code. The files should compile and run, but either no tests will be run, or tests will run but be failing.   For this project, start by uncommenting the first TEST_CASE in the assg09-tests.cpp file. These are the unit tests to test the functionality of your doParenthesisMatch() function, the member function you are to implement.   AddthecorrectfunctionprototypeforthedoParenthesisMatch()memberfunctionintheassg09-stackfun.hpp header file. The prototype consists of the name of the function, its input parameters and their types, and the return value of the function.   Add a stub for your doParenthesisMatch() member function to the assg09-stackfun.cpp implementation file. The function should have the same signature as the prototype you gave in the header file. Documentation for the function has not been given for you this time, so add documentation of your function first. This function is supposed to return a bool result, so you should just initially return true so you can get your code to compile.   Your code should compile and run now. Make sure after adding the function prototype and stub your code compiles and runs. However, your unit tests will be failing initially.   Incrementally implement the functionality of your doParenthesisMatch() member function. You should try to add no more than 2 or 3 lines of code, and then make sure your program still compiles and runs. Start by adding code to get the first failing test to pass. Then once that test passes, move on to the next failing tests until you have all tests passing. If you write something that causes a previously passing test to fail, you should stop and figure out why, and either fix it so that the original test still passes, or remove what you did and try a new approach.   Once you have the doParenthesisMatch() member function implemented and all unit tests passing, you should then move on to the other functions in the order suggested. Some functions use previous ones in this assignment, so do them in the order given for you in the tasks below.   Tasks  You should set up your project/code as described in the previous section. In this section we give some more details on implementing the member functions for this assignment. You should perform the following tasks for this assignment:  1. In the first task, we will write a function that will check if a string of parenthesis is matching. Strings will be given to the function of the format “(()((())))”, using only opening “(” and closing “)”. Your function should be named doParenthesisMatch(). It takes a single string as input, and it returns a boolean result of true if the parenthesis match, and false otherwise.  The algorithm to check for matching parenthesis using a stack is fairly simple. A pseudo-code description might be      for each charcter c in expression     do        if c is an open paren (          push it on stack        if c is a close paren ):        then           if stack is empty              answer is false, because we cant match the current )           else              pop stack, because we just matched an open ( with a close ) endif done  Your function will be given a C++ string class as input. It is relatively simple to parse each character of a C++ string. Here is an example for loop to do this:    2      s = (()); for (size_t index = 0; index < s.length(); index++) {  char c = s[index]; // handle char c of the string expression s here  }    2. In the next task, we will also write a function that decodes a string expression. Given a sequence consisting of ‘I’ and ‘D’ characters, where ‘I’ denotes increasing and ‘D’ denotes decreasing, decode the given sequence to  construct a “minimum number” without repeated digits. An example of some inputs and outputs will make it clear what is meant by a “minimal number”.    sequence IIII -> DDDD -> ID -> IDIDII -> IIDDIDID ->  output 12345 54321 132 1325467 125437698   If you are given 4 characters in the input sequence, the result will be a number with 5 characters, and further only the digits ‘12345’ would be in the “minimal number” output. Each ‘I’ and ‘D’ in the input denotes that the next digit in the output should go up (increase) or go down (decrease) respectively. As you can see for the input sequence “IDI” you have to accommodate the sequence, thus the output goes from 1 to 3 for the initial increase, because in order to then decrease, and also only use the digits ‘123’, we need 3 for the second digit so the third can decrease to 2.  Take a moment to think how you might write an algorithm to solve this problem? It may be difficult to think of any solution involving a simple iterative loop (though a recursive function is not too difficult).  However, the algorithm is relatively simple if we use a stack. Here is the pseudo-code:   for each index, character c in input sequence  do     push character index+1 onto stack (given 0 based index in C) if we have processed all characters or c == I (an increase) then         pop each index from stack and append it to the end of result     endif done  Your function should be named decodeIDSequence(). It will take a string of input sequence, like “IDI” as input, and it will return a string type, the resulting minimal number. Notice we will be constructing a string to return here, so simply start with an empty string string result = and append the digits to the end when you pop them from the stack as described.  3. In the third task, you will write two functions that will be able to sort a stack. First of all, you should write a simpler method that, given an already sorted stack as input, and an item of the same type as the stack type, the item should be inserted into the correct position on the sorted stack to keep it sorted. For example, the stacks will be sorted in ascending order, where the item at the bottom of the stack is the smallest value, and the item at the top is the largest, like this:   top: 8 7 5 3 1 :bottom If we call the function to insert a 4 into this sorted stack, the result should be:  top: 8 7 5 4 3 1  Your function should be called insertItemOnSortedStack(). This function takes an item as its first parameter, and a reference to a Stack as its second parameter. You should create and use another temporary stack in your function in order to accomplish the task. The pseudo-code to accomplish this insertion is relatively simple:    3      given inputStack  and create temporaryStack for this algorithm  while top of inputStack > item we want to insert  do     pop topItem from inputStack     push topItem onto the temporaryStack  done at this point, items on inputStack are <= to the item we want to insert so push item onto inputStack   now put items back from temporaryStack to original inputStack  while temporaryStack is not empty  do     pop topItem from temporaryStack     push topItem onto the inputStack  done The tests given for the insert function use an AStack<int> (a stack of integers) for the tests. You can originally create your function to use a Stack<int> & as its second input parameter. It is important that the stack be a reference parameter here. Also notice that instead of specifying an AStack<int> &, we specify the abstract base class Stack<int> &. This is to demonstrate the power of using virtual classes and class abstractions. If you specify the base class, you can pass an AStack or an LStack or any class that is derived from the base Stack class, as long as that class implements all of the virtual functions of the abstract Stack interface. Once you have your function working for Stack<int> &, templatize your function. We practiced creating function templates in a previous assignment. Here it should be relatively simple, you simply need to add the  template <class T> before the function, and change the <int> to <T> to templatize. Once you do this, you function should still  work and pass the tests using an <int> type.  4. Once you have your insertItemOnSortedStack() template function working, it is even easier to use this function to create a sortStack() function. We could implement this function again using a temporary stack, but for this fourth and final function I want you instead to create a recursive function. A recursive function in this case is going to work in essentially the same way, but we will be using the OS/system function call stack implicitly to perform the algorithm, rather than explicitly creating and using our own temporary stack.  Create a function called sortStack(). This function should take a Stack<string> & (a reference to a Stack of <string> types) as its only parameters. You will later templatize this function as well, but all of the tests of sortStack() use stacks of strings, so get it working first for strings, then try and templatize the function. This is a void function, it doesn’t return a result, but it implicitly causes the stack it is given to become sorted.  The function, as the name implies, will take an unsorted stack, and will sort them in the same order we used previously, e.g. in ascending order with the smallest item at the bottom of the stack, and the largest at the top. The pseudo-code to accomplish this using a recursive algorithm is as follows:   given inputStack as an input parameter  # the base case  if inputStack is empty, do nothing (return)  # the general case  take top item from inputStack and save it in a local variable  call sortStack(inputStack) recursively on this now smaller stack  # on return, the stack should be sorted, so  insertItemOnSortedStack(my item I popped, inputStack)   4     Once you have it working for type stacks, also templatize your sortStack() function, so that it will actually work to sort a Stack of any type.  Example Output  Here is the correct output you should get from your program if you correctly implement all the class functions and successfully pass all of the unit tests given for this assignment. If you invoke your function with no command line arguments, only failing tests are usually shown by default. In the second example, we use the -s command line option to have the unit test framework show both successful and failing tests, and thus we get reports of all of the successfully passing tests as well on the output.  $ ./test =============================================================================== All tests passed (47 assertions in 4 test cases)  $ ./test -s  -------------------------------------------------------------------------------  test is a Catch v2.7.2 host application. Run with -? for options  -------------------------------------------------------------------------------  <doParenthesisMatch()> test doParenthesismatch function ------------------------------------------------------------------------------- assg09-tests.cpp:28 ...............................................................................  assg09-tests.cpp:33: PASSED: CHECK( doParenthesisMatch() )  with expansion:  true ... output snipped ...  =============================================================================== All tests passed (47 assertions in 4 test cases)  Assignment Submission  A MyLeoOnline submission folder has been created for this assignment. There is a target named submit that will create a tared and gziped file named assg02.tar.gz. You should do a make submit when finished and upload your resulting gzip file to the MyLeoOnline Submission folder for this assignment.  $ make submit tar cvfz assg09.tar.gz assg09-tests.cpp assg09-main.cpp  assg09-stackfun.hpp assg09-stackfun.cpp Stack.hpp Stack.cpp assg09-tests.cpp assg09-main.cpp assg09-stackfun.hpp  assg09-stackfun.cpp Stack.hpp Stack.cpp    5     Requirements and Grading Rubrics Program Execution, Output and Functional Requirements  Your program must compile, run and produce some sort of output to be graded. 0 if not satisfied.   (25 pts.) doParenthesisMatch() is implemented correctly and is passing all of the tests. Used a stack of from our class Stack.hpp to implement the algorithm.   (25 pts.) decodeIDSequence() implemented and correct. Used a stack from our class Stack.hpp stack implementation to implement the asked for algorithm.   (25 pts.) insertItemOnSortedStack() implemented and working. The function is correctly templatized. The function takes a reference to the Stack abstract class as it second parameter.   (25 pts.) sortStack() implemented as described and working. The function was implemented using recursion as required. The function was templatized as asked for. The function takes a reference to a Stack base class as its only parameter.   Program Style  Your programs must conform to the style and formatting guidelines given for this class. The following is a list of the guidelines that are required for the assignment to be submitted this week.  Most importantly, make sure you figure out how to set your indentation settings correctly. All programs must use 2 spaces for all indentation levels, and all indentation levels must be correctly indented. Also all tabs must be removed from files, and only 2 spaces used for indentation.   A function header must be present for member functions you define. You must give a short description of the function, and document all of the input parameters to the function, as well as the return value and data type of the function if it returns a value for the member functions, just like for regular functions. However, setter and getter methods do not require function headers.   You should have a document header for your class. The class header document should give a description of the class. Also you should document all private member variables that the class manages in the class document header.   Do not include any statements (such as system(pause) or inputting a key from the user to continue) that are meant to keep the terminal from going away. Do not include any code that is specific to a single operating system, such as the system(pause) which is Microsoft Windows specific./** @file assg09-tests.cpp * @brief main/debug executable for Assignment 09 using stacks. * * @author Jane Programmer * @note cwid : 123 45 678 * @note class: COSC 2336, Summer 2020 * @note ide : Atom Text Editor 1.46.0 / build package / GNU gcc tools * @note assg : Assignment 09 * @date June 1, 2020 * * Assignment 09 using stacks. Use the given Stack ADT to implement a set of * functions/algorithms. This file contains a main() function we can use to * build a debug target for debugging. */ #include <iostream> #include Stack.hpp #include assg09-stackfun.hpp using namespace std; /** main * The main entry point for this program. Execution of this program * will begin with this main function. * * @param argc The command line argument count which is the number of * command line arguments provided by user when they started * the program. * @param argv The command line arguments, an array of character * arrays. * * @returns An int value indicating program exit status. Usually 0 * is returned to indicate normal exit and a non-zero value * is returned to indicate an error condition. */ int main(int argc, char** argv) { // example of invoking some of the functions to debug them // return 0 to indicate successful completion of program return 0; }/** @file assg09-stackfun.hpp * @brief header file for function prototypes for Assignment 09 using stacks. * * @author Jane Programmer * @note cwid : 123 45 678 * @note class: COSC 2336, Summer 2020 * @note ide : Atom Text Editor 1.46.0 / build package / GNU gcc tools * @note assg : Assignment 09 * @date June 1, 2020 * * Assignment 09 using stacks. Use the given Stack ADT to implement a set of * functions/algorithms. This header file is for the function prototypes you are * to write for this assignment. You should modify this file by adding * prototypes/signatures of your 4 functions where indicated below. */ #include <string> #include Stack.hpp // only use the Stack ADT given, do not use STL stacks using namespace std; #ifndef _ASSG09_STACKFUN_H_ #define _ASSG09_STACKFUN_H_ // put your function prototypes for the assignment here // because you are defining template functions, we have to treat // this header/library as a template library, so we include // the implementation file, and we do not separately compile // these files in the build #include assg09-stackfun.cpp #endif // _ASSG09_STACKFUN_H_/** @file assg09-tests.cpp * @brief Unit tests for Assignment 09 using stacks. * * @author Jane Programmer * @note cwid : 123 45 678 * @note class: COSC 2336, Summer 2020 * @note ide : Atom Text Editor 1.46.0 / build package / GNU gcc tools * @note assg : Assignment 09 * @date June 1, 2020 * * Assignment 09 using stacks. Use the given Stack ADT to implement a set of * functions/algorithms. This file has catch2 unit tests you need to test and * implement the functions for your assignment. */ #define CATCH_CONFIG_MAIN #include catch.hpp #include Stack.hpp #include assg09-stackfun.hpp using namespace std; /** test doParenthesisMatch() functions. This is the first function * you are to implement for this assignment. */ /* uncomment the test cases 1 at a time. This test case tests implementation * of the some doParenthesisMatch() function. TEST_CASE(<doParenthesisMatch()> test doParenthesismatch function, [function]) { // by definition an empty expression should be considered as balanced. // Does your function handle an empty expression correctly? CHECK( doParenthesisMatch() ); // test balanced expressions, from simple cases to more complex ones. // All of these match so the function should return true for all of them CHECK( doParenthesisMatch(()) ); CHECK( doParenthesisMatch(()()) ); CHECK( doParenthesisMatch((())) ); CHECK( doParenthesisMatch((())((()))) ); CHECK( doParenthesisMatch((()((())))) ); CHECK( doParenthesisMatch(((((()))(()((()))))()(()))) ); // now test detects unbalanced expressions CHECK_FALSE( doParenthesisMatch(() ); CHECK_FALSE( doParenthesisMatch()) ); CHECK_FALSE( doParenthesisMatch(()() ); CHECK_FALSE( doParenthesisMatch((()))) ); CHECK_FALSE( doParenthesisMatch(((()(())())) ); CHECK_FALSE( doParenthesisMatch(((((()))(()((())))()(()))) ); } */ /** test decodeIDSequence() functions. */ /* uncomment the test cases 1 at a time. This test case tests implementation * of the some decodeIDSequence() function. TEST_CASE(<decodeIDSequence()> test decodeIDSequence function, [function]) { // the empty squence should return simply 1 as the sequence CHECK( decodeIDSequence() == 1 ); // simple cases of only I increase CHECK( decodeIDSequence(I) == 12 ); CHECK( decodeIDSequence(II) == 123 ); CHECK( decodeIDSequence(III) == 1234 ); CHECK( decodeIDSequence(IIIIII) == 1234567 ); // simple cases of only D decrease CHECK( decodeIDSequence(D) == 21 ); CHECK( decodeIDSequence(DD) == 321 ); CHECK( decodeIDSequence(DDDD) == 54321 ); CHECK( decodeIDSequence(DDDDDDD) == 87654321 ); // general case with mixed I and D increases and decreases CHECK( decodeIDSequence(ID) == 132 ); CHECK( decodeIDSequence(DI) == 213 ); CHECK( decodeIDSequence(IDIDII) == 1325467 ); CHECK( decodeIDSequence(IIDD/** @file Stack.cpp * @brief implementation file for Stack class for Assignment 09 using stacks. * * @author Derek Harter * @note cwid : 123 45 678 * @note class: COSC 2336, Summer 2020 * @note ide : Atom Text Editor 1.46.0 / build package / GNU gcc tools * @note assg : Assignment 09 * @date June 1, 2020 * * NOTE: Do not edit this file for Assignment 09. You are to use the Stack * ADT as given for the assignment. * * Assignment 09 using stacks. Use the given Stack ADT to implement a set of * functions/algorithms. This implementation file contains the actual * implementation of the functions for the Stack ADT given for this assignment. */ #include <sstream> #include Stack.hpp //------------------------------------------------------------------------- // friend/helper functions of the Stack ADT /** Stack equivalence * Compare two given stacks to determine if they are equal or not. * stacks are equal if they are both of the same size, and each corresponding * item on each stack is equal at the same position on the stack. * This function relies on overloaded operator[] to access items on stack * by index for the comparison. * * @param rhs The stack on the right hand side of the boolean comparison * expression to compare this stack against to check for equivalence. * * @returns bool Returns true if the stacks are equal, and false otherwise. */ template <class T> bool Stack<T>::operator==(const Stack& rhs) const { // if number of items on the stacks dont match, then they cant // be equivalent if (this->size() != rhs.size()) { return false; } // otherwise need to check each item individually for (int index = 0; index < this->size(); index++) { if ((*this)[index] != rhs[index]) { return false; } } // if we get to this point, all items checked were equivalent, so // we are done and the answer is yes the stacks are equal return true; } /** Stack output stream operator * Friend function for Stack ADT, overload output stream operator to allow * easy output of stack representation to an output stream. * * @param out The output stream we are to stream additional output into. * @param aStack The Stack instance we are to stream a representation of * into the output stream given. * * @returns ostream& Returns a reference to the original output stream we * were given, but after we have inserted new values into the stream. */ template <typename U> ostream& operator<<(ostream& out, const Stack<U>& aStack) { out << aStack.tostring(); return out; } //------------------------------------------------------------------------- // AStack (array stack) member functions /** stack (array) constructor * Constructor for stack. Default to enough room for 100 items * * @param initialAlloc Initial space to allocate for stack, defaults to * 100. */ template <class T> AStack<T>::AStack(int initialAlloc) { allocSize = initialAlloc; topIndex = 0; item/** @file assg09-stackfun.cpp * @brief implementation file for function prototypes for * Assignment 09 using stacks. * * @author Jane Programmer * @note cwid : 123 45 678 * @note class: COSC 2336, Summer 2020 * @note ide : Atom Text Editor 1.46.0 / build package / GNU gcc tools * @note assg : Assignment 09 * @date June 1, 2020 * * Assignment 09 using stacks. Use the given Stack ADT to implement a set of * functions/algorithms. This implementation file is for the functions you are * to write for this assignment. You should modify this file by adding * implementations of the 4 functions you are to write. You need to use the * Stack ADT given to you, and included for you, for the Stack instances for * your functions. It is incorrect to include STL stacks or other containers * here to use for this assignment. */ #include Stack.hpp // only use the Stack ADT given, do not use STL stacks--- title: Assignment 09: Applications of Stacks author: COSC 2336: Data Structures and Algorithms date: Fall 2020 --- # Objectives - More practice with recursion. - Practice writing some template functions. - Use stack ADT to implement given algorithms. - Practice using Stack class container given as a library in a separate file. - Look at some common applications of stacks. # Description In this assignment, you will be using the `Stack` abstract data type we developed for this unit and discussed in our lectures, to implement 4 functions that use a stack data type to accomplish their algorithms. The functions range from relatively simple, straight forward use of a stack, to a bit more complex. But in all 4 cases, you should only need to use the abstract stack interface functions `push()`, `pop()`, `top()`, and `isEmpty()` in order to successfully use our `Stack` type for this assignment and the function you are asked to write. **NOTE** You are to use the Stack ADT abstraction give to you for this assignment. If you are familiar with STL stack containers, you are not to use them for this assignment. Part of the assignment is to look over and learn the Stack ADT implementation we give you here based on our textbook Stack examples. # Setup For this assignment you will be given the following files: | File Name | Description | |-----------------------|---------------------------------------------------| | `assg09-tests.cpp` | Unit tests for the member functions | | | you are to write. | | `assg09-stackfun.hpp` | Header file where function prototypes for the | | | functions you write using stacks should go. | | `assg09-stackfun.cpp` | Implementaiton file, the implementation of the 4 | | | functions you write for this assignment go here. | | `Stack.hpp` | Header file defining a Stack ADT for use in | | | implementing the functions for this assignment. | | | You will not make any modifications in this file, | | | you are only going to be using the given Stack. | | `Stack.cpp` | Implementation file for the Stack ADT | | | template class. You also do not make any changes | | | in this file either. | Set up a multi-file project to compile the `.cpp` source files and run them as shown for the class. The Makefile you were given should be usable to create a build project using the Atom editor as required in this class. You will only be adding code to the `assg09-stackfun.[hpp|cpp]` file in this assignment. The `Stack.[hpp|cpp]` file contains a `Stack` container. You are to use this `Stack` ADT for the 4 functions you are to write for this assignment. The general approach you should tak/** @file Stack.hpp * @brief header file for Stack class for Assignment 09 using stacks. * * @author Derek Harter * @note cwid : 123 45 678 * @note class: COSC 2336, Summer 2020 * @note ide : Atom Text Editor 1.46.0 / build package / GNU gcc tools * @note assg : Assignment 09 * @date June 1, 2020 * * NOTE: Do not edit this file for Assignment 09. You are to use the Stack * ADT as given for the assignment. * * Assignment 09 using stacks. Use the given Stack ADT to implement a set of * functions/algorithms. This header file contains the declaration of the Stack * class container that defines the ADT abstraction for Stacks to use for this * assignment. */ #include <iostream> using namespace std; #ifndef _STACK_H_ #define _STACK_H_ //------------------------------------------------------------------------- /** stack (base class) * The basic definition of the Stack Abstract Data Type (ADT) * and stack operations. All declared functions here are * virtual, they must be implemented by concrete derived * classes. */ template <class T> class Stack { public: /** clear * Method to clear out or empty any items on stack, * put stack back to empty state. * Postcondition: Stack is empty. * * @returns void Nothing returned */ virtual void clear() = 0; /** isEmpty * Function to determine whether the stack is empty. Needed * because it is undefined to pop from empty stack. This * function will not change the state of the stack (const). * * @returns bool true if stack is empty, false otherwise. */ virtual bool isEmpty() const = 0; /** push * Add a new item onto top of stack. * * @param newItem The item of template type T to push on top of * the current stack. * * @returns void Nothing is returned */ virtual void push(const T& newItem) = 0; /** top * Return the top item from the stack. Note in this ADT, peeking * at the top item does not remove the top item. Some ADT combine * top() and pop() as one operation. It is undefined to try and * peek at the top item of an empty stack. Derived classes should * throw an exception if this is attempted. * * @returns T Returns the top item from stack. */ virtual T top() const = 0; /** pop * Remove the item from the top of the stack. It is undefined what * it means to try and pop from an empty stack. Derived classes should * throw an exception if pop() from empty is attempted. * * @returns void Returns nothing */ virtual void pop() = 0; /** size * Accessor method to provide the current size of the stack. * * @returns int Returns the current stack size as an int. */ virtual int size() const = 0; /** tostring * Represent stack as a string * * @returns string Returns a string representation of the items on * this stack. */ virtual string tostring() const = 0; // operload operators, mostly to support boolean comparison Assignment 09: Applications of Stacks COSC 2336: Data Structures and Algorithms Fall 2020 Objectives • More practice with recursion. • Practice writing some template functions. • Use stack ADT to implement given algorithms. • Practice using Stack class container given as a library in a separate file. • Look at some common applications of stacks. Description In this assignment, you will be using the Stack abstract data type we developed for this unit and discussed in our lectures, to implement 4 functions that use a stack data type to accomplish their algorithms. The functions range from relatively simple, straight forward use of a stack, to a bit more complex. But in all 4 cases, you should only need to use the abstract stack interface functions push(), pop(), top(), and isEmpty() in order to successfully use our Stack type for this assignment and the function you are asked to write. NOTE You are to use the Stack ADT abstraction give to you for this assignment. If you are familiar with STL stack containers, you are not to use them for this assignment. Part of the assignment is to look over and learn the Stack ADT implementation we give you here based on our textbook Stack examples. Setup For this assignment you will be given the following files: File Name Description assg09-tests.cpp Unit tests for the member functions you are to write. assg09-stackfun.hpp Header file where function prototypes for the functions you write using stacks should go. assg09-stackfun.cpp Implementaiton file, the implementation of the 4 functions you write for this assignment go here. Stack.hpp Header file defining a Stack ADT for use in implementing the functions for this assignment. You will not make any modifications in this file, you are only going to be using the given Stack. Stack.cpp Implementation file for the Stack ADT template class. You also do not make any changes in this file either. Set up a multi-file project to compile the .cpp source files and run them as shown for the class. The Makefile you were given should be usable to create a build project using the Atom editor as required in this class. You will only be adding code to the assg09-stackfun.[hpp|cpp] file in this assignment. The Stack.[hpp|cpp] file contains a Stack container. You are to use this Stack ADT for the 4 functions you are to write for this assignment. 1 The general approach you should take for this assignment, and all assignment is: 1. Set up your project with the given starting code. The files should compile and run, but either no tests will be run, or tests will run but be failing. 2. For this project, start by uncommenting the first TEST_CASE in the assg09-tests.cpp file. These are the unit tests to test the functionality of your doParenthesisMatch() function, the member function you are to implement. 3. Add the correct function prototype for the doParenthesisMatch() member function in the assg09-stackfun.hpp header file. The prototype consists of the name of the f