Stack coding
Rajeshkc4
assg-10.pdf
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
