Assg
1
0: Applications of Stacks
COSC
2
3
3
6
Spring 201
9
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 -> 1234
5
DDDD -> 54321
ID -> 132
IDIDII -> 132546
7
IIDDIDID -> 12543769
8
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
of integers) for the tests. You can originally create your function to
use a Stack
that the stack be a reference parameter here. Also notice that in-
stead of specifying an AStack
class Stack
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
creating function templates in a previous assignment. Here it should
be relatively simple, you simply need to add the
template
before the function, and change the
you do this, you function should still work and pass the tests using an
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
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
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() ———————-
balanced: true
balanced: true
balanced: true
balanced: true
balanced: false
6
balanced: false
balanced: false
balanced: false
————– Test decodeIDSequence() ————————–
result: 12345
result: 54321
result: 1
result: 1325467
result: 125437698
————– Test insertItemOnSortedStack() ——————
before inserting:
–TopTop–
8
7
5
3
1
–Bottom–
after inserting:
–TopTop–
8
7
5
7
4
3
1
–Bottom–
before inserting:
–TopTop–
–Bottom–
after inserting:
–TopTop–
5
–Bottom–
before inserting:
–TopTop–
5
–Bottom–
after inserting:
–TopTop–
9
5
–Bottom–
before inserting:
–TopTop–
9
5
–Bottom–
after inserting:
–TopTop–
9
8
5
1
–Bottom–
————– Test sortStack() ——————————–
before sorting:
–TopTop–
Chris
Bobbie
Allan
Tom
Susan
–Bottom–
after sorting:
–TopTop–
Tom
Susan
Chris
Bobbie
Allan
–Bottom–
before sorting:
–TopTop–
–Bottom–
after sorting:
–TopTop–
–Bottom–
before sorting:
9
–TopTop–
Alice
–Bottom–
after sorting:
–TopTop–
Alice
–Bottom–
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
/**
* @author Derek Harter
* @cwid 123 45 678
* @class COSC 2336, Spring 2019
* @ide Visual Studio Community 2017
* @date January 18, 2019
* @assg C++ Stacks videos
*
* @description A Stack ADT with two concrete impelementation
* examples: an array based stack implementaiton (AStack), and
* a linked list based implementation (LStack).
*/
#include
#include
#include
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 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 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 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 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
virtual const T& operator[](int index) const = 0;
// overload output stream operator for all stacks using tostring()
template
friend ostream& operator<<(ostream& out, const Stack& 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
bool Stack
{
// 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
ostream& operator<<(ostream& out, const Stack& 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 AStack : public Stack
{
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
AStack
{
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
AStack
{
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
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
void AStack
{
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
bool AStack
{
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
void AStack
{
// 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
T AStack
{
//assert(topIndex != 0);
if (topIndex == 0)
{
throw EmptyStackException(“AStack
}
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
void AStack
{
// assert(topIndex != 0);
if (topIndex == 0)
{
throw EmptyStackException(“AStack
}
else
{
topIndex–;
}
}
/** Stack (array) size
* Return the current size (number of items) on this stack.
*
* @returns int Returns the current stack size.
*/
template
int AStack
{
return topIndex;
}
/** Stack (array) tostring
* Represent this stack as a string.
*
* @returns string Returns the contents of stack as a string.
*/
template
string AStack
{
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
const T& AStack
{
// bounds checking, we will throw our stack exception if fails
if (index < 0 || index >= topIndex)
{
throw InvalidIndexStackException(“AStack
}
// 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
struct Node
{
T item;
Node
};
/** 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 LStack : public Stack
{
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
int numItems;
};
/** stack (list) constructor
* Constructor for linked list version of stack.
*/
template
LStack
{
stackTop = NULL;
numItems = 0;
}
/** stack (list) destructor
* Destructor for linked list version of stack.
*/
template
LStack
{
clear();
}
/** stack (list) clear
*
*/
template
void LStack
{
Node
// 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
bool LStack
{
return stackTop == NULL;
}
/** stack (list) push
*
*/
template
void LStack
{
// dynamically allocate space for the new Node to hold
// this newItem
Node
// 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
T LStack
{
//assert(stackTop != NULL)
if (stackTop == NULL)
{
throw EmptyStackException(“LStack
}
else
{
return stackTop->item;
}
}
/** stack (list) pop
*
*/
template
void LStack
{
//assert(stackTop != NULL)
if (stackTop == NULL)
{
throw EmptyStackException(“LStack
}
else
{
// keep track of the current top, so we can deallocate
Node
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
int LStack
{
return numItems;
}
/** stack (list) tostring
* Represent this stack as a string.
*
* @returns string Returns the contents of stack as a string.
*/
template
string LStack
{
ostringstream out;
Node
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
const T& LStack
{
// bounds checking, we will throw our stack exception if fails
if (index < 0 || index >= numItems)
{
throw InvalidIndexStackException(“LStack
}
// 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
while (currentIndex != index)
{
currentIndex–;
currentNode = currentNode->link;
}
return currentNode->item;
}
}
/**
* @author Jane Programmer
* @cwid 123 45 678
* @class COSC 2336, Spring 2019
* @ide Visual Studio Community 2017
* @date March 8, 2019
* @assg Assignment 10
*
* @description Assignment 10 Applications of stacks. Implement
* the given functions and algorithms using a stack data type.
*/
#include
#include
#include “Stack.hpp”
using namespace std;
// you can put your function implementations here, or alternatively
// create a header named StackApplications.hpp and implementation file
// named StackApplicaitons.cpp and include the header file here
// #include “StackApplications.hpp”
/** 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)
{
// ———————————————————————–
cout << "-------------- Test doParenthesisBalance() ----------------------"
<< endl << endl;
string expression = "()";
cout << "
<< expression << "'" << endl;
//bool balanced = doParenthesisBalance(expression);
//cout << " balanced: " << boolalpha << balanced << endl;
//assert(balanced);
expression = "(()((())))";
cout << "
<< expression << "'" << endl;
//balanced = doParenthesisBalance(expression);
//cout << " balanced: " << boolalpha << balanced << endl;
//assert(balanced);
expression = "((((()))(()((()))))()(()))";
cout << "
<< expression << "'" << endl;
//balanced = doParenthesisBalance(expression);
//cout << " balanced: " << boolalpha << balanced << endl;
//assert(balanced);
expression = "";
cout << "
<< expression << "'" << endl;
//balanced = doParenthesisBalance(expression);
//cout << " balanced: " << boolalpha << balanced << endl;
//assert(balanced);
expression = "(";
cout << "
<< expression << "'" << endl;
//balanced = doParenthesisBalance(expression);
//cout << " balanced: " << boolalpha << balanced << endl;
//assert(!balanced);
expression = ")";
cout << "
<< expression << "'" << endl;
//balanced = doParenthesisBalance(expression);
//cout << " balanced: " << boolalpha << balanced << endl;
//assert(!balanced);
expression = "((()(())())";
cout << "
<< expression << "'" << endl;
//balanced = doParenthesisBalance(expression);
//cout << " balanced: " << boolalpha << balanced << endl;
//assert(!balanced);
expression = "((((()))(()((())))()(()))";
cout << "
<< expression << "'" << endl;
//balanced = doParenthesisBalance(expression);
//cout << " balanced: " << boolalpha << balanced << endl;
//assert(!balanced);
cout << endl << endl;
// -----------------------------------------------------------------------
cout << "-------------- Test decodeIDSequence() --------------------------"
<< endl << endl;
string result;
string sequence = "IIII";
cout << "
<< sequence << "'" << endl;
//result = decodeIDSequence(sequence);
//cout << " result: " << result << endl;
//assert(result == "12345");
sequence = "DDDD";
cout << "
<< sequence << "'" << endl;
//result = decodeIDSequence(sequence);
//cout << " result: " << result << endl;
//assert(result == "54321");
sequence = "";
cout << "
<< sequence << "'" << endl;
//result = decodeIDSequence(sequence);
//cout << " result: " << result << endl;
//assert(result == "1");
sequence = "IDIDII";
cout << "
<< sequence << "'" << endl;
//result = decodeIDSequence(sequence);
//cout << " result: " << result << endl;
//assert(result == "1325467");
sequence = "IIDDIDID";
cout << "
<< sequence << "'" << endl;
//result = decodeIDSequence(sequence);
//cout << " result: " << result << endl;
//assert(result == "125437698");
cout << endl << endl;
// ----------------------------------------------------------------------
cout << "-------------- Test insertItemOnSortedStack() ------------------"
<< endl << endl;
LStack
sortedStack.push(1);
sortedStack.push(3);
sortedStack.push(5);
sortedStack.push(7);
sortedStack.push(8);
// general test
cout << "
<< endl << endl;
cout << "before inserting: " << endl
<< sortedStack << endl;
//insertItemOnSortedStack(4, sortedStack);
cout << "after inserting: " << endl
<< sortedStack << endl;
//int stackSize = 6;
//int expectedItems1[] = {1, 3, 4, 5, 7, 8};
//AStack
//assert(sortedStack == expectedStack1);
// test insert on empty stack
sortedStack.clear();
cout << "
//assert(sortedStack == expectedStack2);
// test insert at top of stack
cout << "
//assert(sortedStack == expectedStack3);
// test insert at bottom of stack
cout << "
//assert(sortedStack == expectedStack4);
cout << endl << endl;
cout << "-------------- Test sortStack() --------------------------------"
<< endl << endl;
LStack
aStack.push(“Susan”);
aStack.push(“Tom”);
aStack.push(“Allan”);
aStack.push(“Bobbie”);
aStack.push(“Chris”);
// general test of stackSort() function
cout << "
//assert(aStack == expectedStack5);
// sort an empty stack
aStack.clear();
cout << "
//assert(aStack == expectedStack6);
// sort stack with single item
aStack.push(“Alice”);
cout << "
//assert(aStack == expectedStack7);
// sort already sorted stack
aStack.push(“Bob”);
aStack.push(“Carol”);
aStack.push(“Dave”);
cout << "
//assert(aStack == expectedStack8);
// return 0 to indicate successful completion
return 0;
}