C++ Stack related. Computer science

Assg 10: Applications of Stacks

COSC 2336 Spring 2019

March 12, 2019

Dates:

Due: Sunday March 31, by Midnight

Objectives

� More practice with recursion.

� Practice writing some template functions.

� Use stack ADT to implement given algorithms.

� Look at some common applications of stacks.

Description

In this assignment, you will be using the Stack abstract data type we devel- oped this week and discussed in our weeks 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 suc- cessfully use our Stack type for this assignment and the function you are asked to write.

For this assignment you need to perform the following tasks.

1. In the �rst 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

1

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 migth be

for each charcter c in expression

do

if c is an open paren '('

push it on stack

if c is a close paren ')':

do

if stack is empty

answer is false, because we can't match the current ')'

else

pop stack, because we just matched an open '(' with a close ')'

done

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:

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".

2

sequence output

IIII -> 12345

DDDD -> 54321

ID -> 132

IDIDII -> 1325467

IIDDIDID -> 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, becase in order to then decrease, and also only have 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 di�cult to think of any solution involving a simple iterative loop (though a recursive function is not too di�cult).

However, the algorithm is relatively simple if we use a stack. Here is the pseudo-code:

for each 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)

do

pop each index from stack and append it to the end of result

done

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

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 �rst 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 accmplish the task. The pseudo-code to accomplish this insertion is relatively simple:

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

4

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 in- stead 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.

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 �nal 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 �rst for strings, then try and templatize the function. This is a void funciton, 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 recursize algorithm is as follows:

5

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)

Once you have it working for <string> type stacks, also templatize your sortStack() function, so that it will actually work to sort a Stack of any type.

In this assignment you will only be given 2 �les, an assg-10-tests.cpp �le with a main function and unit tests of the functions you are to write. You will also use the Stack.hpp header �le that was developed and shown in the videos for class this week. You should not have to add or change any code in Stack.hpp. You just need to use the Stack class to implement your code/functions for this assignment. As usual, the tests have been commented out. I strongly suggest you implement the functions one at a time, in the order described above, and uncomment each test 1 at a time to test your work incrementally. If you implement your code correctly and uncomment all of the tests, you should get the following correct output:

-------------- Test doParenthesisBalance() ----------------------

<doParenthesisBalance()> testing balanced expression: '()'

balanced: true

<doParenthesisBalance()> testing balanced expression: '(()((())))'

balanced: true

<doParenthesisBalance()> testing balanced expression: '((((()))(()((()))))()(()))'

balanced: true

<doParenthesisBalance()> testing empty expression, should evaluate as balanced: ''

balanced: true

<doParenthesisBalance()> simple unbalanced expression: '('

balanced: false

6

<doParenthesisBalance()> simple unbalanced expression: ')'

balanced: false

<doParenthesisBalance()> complex unbalanced expression: '((()(())())'

balanced: false

<doParenthesisBalance()> complex unbalanced expression: '((((()))(()((())))()(()))'

balanced: false

-------------- Test decodeIDSequence() --------------------------

<decodeIDSequence()> testing simple increase sequence: 'IIII'

result: 12345

<decodeIDSequence()> testing simple decrease sequence: 'DDDD'

result: 54321

<decodeIDSequence()> testing empty: ''

result: 1

<decodeIDSequence()> testing general sequence: 'IDIDII'

result: 1325467

<decodeIDSequence()> testing general sequence: 'IIDDIDID'

result: 125437698

-------------- Test insertItemOnSortedStack() ------------------

<insertItemOnSortedStack()> general test, insert in middle:

before inserting:

--TopTop--

8

7

5

3

1

--Bottom--

after inserting:

--TopTop--

8

7

5

7

4

3

1

--Bottom--

<insertItemOnSortedStack()> test inesrtion to empty stack:

before inserting:

--TopTop--

--Bottom--

after inserting:

--TopTop--

5

--Bottom--

<insertItemOnSortedStack()> test insertion to top of stack:

before inserting:

--TopTop--

5

--Bottom--

after inserting:

--TopTop--

9

5

--Bottom--

<insertItemOnSortedStack()> test insertion to bottom of stack:

before inserting:

--TopTop--

9

5

--Bottom--

after inserting:

--TopTop--

9

8

5

1

--Bottom--

-------------- Test sortStack() --------------------------------

<sortStack()> general test:

before sorting:

--TopTop--

Chris

Bobbie

Allan

Tom

Susan

--Bottom--

after sorting:

--TopTop--

Tom

Susan

Chris

Bobbie

Allan

--Bottom--

<sortStack()> sort an empty stack:

before sorting:

--TopTop--

--Bottom--

after sorting:

--TopTop--

--Bottom--

<sortStack()> sort single item sized stack:

before sorting:

9

--TopTop--

Alice

--Bottom--

after sorting:

--TopTop--

Alice

--Bottom--

<sortStack()> sort already sorted stack:

before sorting:

--TopTop--

Dave

Carol

Bob

Alice

--Bottom--

after sorting:

--TopTop--

Dave

Carol

Bob

Alice

--Bottom--

Assignment Submission

A MyLeoOnline submission folder has been created for this assignment. You should attach and upload your completed assg-10.cpp source �les to the sub- mission folder to complete this assignment. I didn't put the code/functions in a separate .cpp/.hpp �le, but feel free to make a �le named StackApplica- tions.[hpp|cpp] with function prototypes and your 4 functions implementa- tions if you like, and submit it that way, though I will accept the functions simply above the main() in the assg-10.cpp �le this week, if you prefer.

10

Requirements and Grading Rubrics

Program Execution, Output and Functional Requirements

1. Your program must compile, run and produce some sort of output to be graded. 0 if not satis�ed.

2. (25 pts.) doParenthesisMatch() is implemented correctly and is pass- ing all of the tests. Used a stack of from our class Stack.hpp to imple- ment the algorithm.

3. (25 pts.) decodeIDSequence() implemented and correct. Used a stack from our class Stack.hpp stack implemenation to implement the asked for algorithm.

4. (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.

5. (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.

1. Most importantly, make sure you �gure 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 �les, and only 2 spaces used for indentation.

2. A function header must be present for member functions you de�ne. 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.

11

3. You should have a document header for your class. The class header document should give a description of the class. Also you should doc- ument all private member variables that the class manages in the class document header.

4. 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 speci�c to a single operating system, such as the system("pause") which is Microsoft Windows speci�c.

12

sources/Stack.hpp

/** * * @description A Stack ADT with two concrete impelementation * examples: an array based stack implementaiton (AStack), and * a linked list based implementation (LStack). */ #include <iostream> #include <string> #include <sstream> using namespace std; //------------------------------------------------------------------------- /** 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. */ 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. */ 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. */ virtual void pop() = 0; /** size * Accessor method to provide the current size of the stack. */ virtual int size() const = 0; /** tostring * Represent stack as a string */ virtual string tostring() const = 0; // operload operators, mostly to support boolean comparison between // two stacks for testing bool operator==(const Stack<T>& rhs) const; virtual const T& operator[](int index) const = 0; // overload output stream operator for all stacks using tostring() template <typename U> friend ostream& operator<<(ostream& out, const Stack<U>& aStack); }; /** 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 don't match, then they can't // 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. */ template <typename U> ostream& operator<<(ostream& out, const Stack<U>& aStack) { out << aStack.tostring(); return out; } //------------------------------------------------------------------------- /** Empty stack exception * Class for empty stack exceptions */ class EmptyStackException { private: string message; public: EmptyStackException() { message = "Error: operation on empty stack"; } EmptyStackException(string str) { message = "Error: " + str + " attempted on emtpy stack"; } string what() { return message; } }; //------------------------------------------------------------------------- /** InvalidIndex stack exception * Class for InvalidIndex stack exceptions */ class InvalidIndexStackException { private: string message; public: InvalidIndexStackException() { message = "Error: invalid index attempted on stack"; } InvalidIndexStackException(string str) { message = "Error: " + str + " invalid index reference on stack"; } string what() { return message; } }; //------------------------------------------------------------------------- /** stack (array implementation) * Implementation of the stack ADT as a fixed array. This implementation * uses dynamic memory allocation, and demonstrates doubling the size * of the allocated space as needed to grow stack. * * @var allocSize The amount of memory currently allocated for this stack. * @var topIndex The index pointing to top item location on stack array. The stack * grows from 0 up, so the top also indicates the current size of the stack. * @var items The items on the stack. This is a dynamically allocated array that * can grow if needed when stack exceeds current allocation. */ template <class T> class AStack : public Stack<T> { private: int allocSize; // amount of memory allocated int topIndex; // index to top item on stack, stack T* items; public: AStack(int initialAlloc = 100); // constructor AStack(T initItems[], int length); ~AStack(); // destructor void clear(); bool isEmpty() const; void push(const T& newItem); T top() const; void pop(); int size() const; string tostring() const; const T& operator[](int index) const; }; /** 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; items = new T[allocSize]; } /** stack (array) array constructor * Constructor for stack. Copy items from an array as initial items * on the stack. * * @param items An array of items to copy/push onto the stack. The item * at index 0 of the array will be the bottom of the stack, and the * last item will end up on the top. * @param length The total number of items in the array to copy/push onto * the new stack. */ template <class T> AStack<T>::AStack(T initItems[], int length) { allocSize = length; topIndex = 0; items = new T[allocSize]; // copy the init items to our block of memory. Also // we update the topIndex to use as our iterator index // and incidentally it will be correctly set to point to // the top of the stack once this copy is finished. for (topIndex = 0; topIndex < length; topIndex++) { items[topIndex] = initItems[topIndex]; } } /** stack (array) destructor */ template <class T> AStack<T>::~AStack() { // free up currently allocated memory delete [] items; } /** stack (array) clear * Function to initialize the stack back to an empty state. * Postcondition: topIndex = 0; isEmpty() == true */ template <class T> void AStack<T>::clear() { topIndex = 0; } /** stack (array) isEmpty * Determine whether stack is currently empty or not. * * @returns returns true if the stack is empty, otherwis * returns false. */ template <class T> bool AStack<T>::isEmpty() const { return topIndex == 0; } /** stack (array) push * Add newItem to the top of the stack. * Preconditon: The stack exists * Postcondition: The stack is changed and newItem is added to the top * of the stack. * @param newItem The new item to push on top of this stack. */ template <class T> void AStack<T>::push(const T& newItem) { // if stack is full, grow it if (topIndex == allocSize) { // double the current size allocSize = 2 * allocSize; // alloc the new space T* newItems = new T[allocSize]; // and copy the stack to the new storage space for (int index = 0; index < topIndex; index++) { newItems[index] = items[index]; } // free up the old space, start using the new space delete [] items; items = newItems; } // add the item, and increment our top items[topIndex] = newItem; topIndex++; } /** stack (array) top * Peek at and return the top element of the stack. * Preconditon: The stack exists and is not empty * Postcondition: If the stack is empty, we throw StackEmpty * exception; otherwise, the top element of the stack is * returned * @param newItem The new item to push on top of this stack. */ template <class T> T AStack<T>::top() const { //assert(topIndex != 0); if (topIndex == 0) { throw EmptyStackException("AStack<T>::top()"); } else { return items[topIndex - 1]; } } /** stack (array) pop * Remove the top element from the stack. Some ADT combine pop * and top. We have two separate operations in this ADT. * Preconditon: The stack exists and is not empty. * Postcondition: If the stack is empty, we throw StackEmpty * exception; otherwise the top element of the stack is removed * from the stack. */ template <class T> void AStack<T>::pop() { // assert(topIndex != 0); if (topIndex == 0) { throw EmptyStackException("AStack<T>::pop()"); } else { topIndex--; } } /** Stack (array) size * Return the current size (number of items) on this stack. * * @returns int Returns the current stack size. */ template <class T> int AStack<T>::size() const { return topIndex; } /** Stack (array) tostring * Represent this stack as a string. * * @returns string Returns the contents of stack as a string. */ template <class T> string AStack<T>::tostring() const { ostringstream out; out << "--TopTop--" << endl; for (int index = topIndex- 1; index >= 0; index--) { out << items[index] << endl; } out << "--Bottom--" << endl; return out.str(); } /** Stack (array) indexing operator * Access internel elements of stack using indexing operator[]. * This is not a normal stack operation, we use mainly for testing * so that we can compare if two stack are equal at each internal * element of the stack. For this reason, this operator should * probably be private to the Stack class. * * @param index The index of the item onf the stack we want to access * and return, where index 0 represents the bottom of the stack and * index == size-1 is the top. * * @returns T Returns the item at "index" on the stack. */ template <class T> const T& AStack<T>::operator[](int index) const { // bounds checking, we will throw our stack exception if fails if (index < 0 || index >= topIndex) { throw InvalidIndexStackException("AStack<T>::operator[]"); } // otherwise we can directly access the asked for item from our items array else { return items[index]; } } //------------------------------------------------------------------------- /** Node * A basic node contaning an item and a link to the next node in * the linked list. */ template <class T> struct Node { T item; Node<T>* link; }; /** stack (linked list implementation) * Implementation of the stack ADT as a dynamic linked list. This implementation * uses link nodes and grows (and shrinks) the nodes as items popped and pushed * onto stack. */ template <class T> class LStack : public Stack<T> { public: LStack(); // default constructor ~LStack(); // destructor void clear(); bool isEmpty() const; void push(const T& newItem); T top() const; void pop(); int size() const; string tostring() const; const T& operator[](int index) const; private: Node<T>* stackTop; int numItems; }; /** stack (list) constructor * Constructor for linked list version of stack. */ template <class T> LStack<T>::LStack() { stackTop = NULL; numItems = 0; } /** stack (list) destructor * Destructor for linked list version of stack. */ template <class T> LStack<T>::~LStack() { clear(); } /** stack (list) clear * */ template <class T> void LStack<T>::clear() { Node<T>* temp; // iterate through Nodes in stack, freeing them up // as we visit them while (stackTop != NULL) { temp = stackTop; stackTop = stackTop->link; // dellocate this Node memory delete temp; } numItems = 0; } /** stack (list) isEmpty * */ template <class T> bool LStack<T>::isEmpty() const { return stackTop == NULL; } /** stack (list) push * */ template <class T> void LStack<T>::push(const T& newItem) { // dynamically allocate space for the new Node to hold // this newItem Node<T>* newNode = new Node<T>; // initialize the node newNode->item = newItem; newNode->link = stackTop; // now make this new node the new top of stack stackTop = newNode; numItems++; } /** stack (list) top * */ template <class T> T LStack<T>::top() const { //assert(stackTop != NULL) if (stackTop == NULL) { throw EmptyStackException("LStack<T>::top()"); } else { return stackTop->item; } } /** stack (list) pop * */ template <class T> void LStack<T>::pop() { //assert(stackTop != NULL) if (stackTop == NULL) { throw EmptyStackException("LStack<T>::pop()"); } else { // keep track of the current top, so we can deallocate Node<T>* temp; temp = stackTop; // pop off the top stackTop = stackTop->link; // deallocate the old top now delete temp; // update size after removal numItems--; } } /** Stack (list) size * Return the current size (number of items) on this stack. * * @returns int Returns the current stack size. */ template <class T> int LStack<T>::size() const { return numItems; } /** stack (list) tostring * Represent this stack as a string. * * @returns string Returns the contents of stack as a string. */ template <class T> string LStack<T>::tostring() const { ostringstream out; Node<T>* temp = stackTop; out << "--TopTop--" << endl; while (temp != NULL) { out << temp->item << endl; temp = temp->link; } out << "--Bottom--" << endl; return out.str(); } /** Stack (list) indexing operator * Access internel elements of stack using indexing operator[]. * This is not a normal stack operation, we use mainly for testing * so that we can compare if two stack are equal at each internal * element of the stack. For this reason, this operator should * probably be private to the Stack class. * * @param index The index of the item on the stack we want to access * and return, where index 0 represents the bottom of the stack and * index == size-1 is the top. * * @returns T Returns the item at "index" on the stack. */ template <class T> const T& LStack<T>::operator[](int index) const { // bounds checking, we will throw our stack exception if fails if (index < 0 || index >= numItems) { throw InvalidIndexStackException("LStack<T>::operator[]"); } // otherwise we will have to search our list for the desired item // we will search backwards, so the stackTop node is at index // numItems-1, and we iterate back through the list till we // arrive at index else { int currentIndex = numItems - 1; Node<T>* currentNode = stackTop; while (currentIndex != index) { currentIndex--; currentNode = currentNode->link; } return currentNode->item; } }