Today's exercise has two parts:
Begin by creating a new project for this week's files. Download tester.cpp, StackTester.h, StackTester.cpp, Stack.h, and Stack.cpp. Import them into your project, open the files, and take a moment to look them over, to become familiar with their contents.
As you can see, this Stack class contains three instance variables:
unsigned myCapacity; unsigned mySize; Item* myArray;We will be storing the address of a dynamically allocated array in myArray. We will be storing the length of that array in myCapacity, and in mySize, we will be storing the number of items in the array. As we shall see, this value will correspond to the index of the spot in that array where the next Item that we push() will be stored.
As we have seen in class, the primary Stack operations are:
To let you focus on these Stack operations, the Stack class already contains prototypes and definitions for:
Note that part of the test is commented out. Leave this part commented out for now; we will be uncommenting it in Part II.
Run the project, and verify that everything works correctly at the outset.
Our explicit constructor gives us the ability to define Stack objects with a given capacity. Since these Stack objects are initially empty (i.e., they contain no items), the first operation we will build is the isEmpty() method.
In StackTester.cpp, uncomment the call to and definition of the testIsEmpty() method. Compile and run the test. You should see an error message indicating that isEmpty() does not exist.
In Stack.h, add a prototype for isEmpty() to the class. Recompile and rerun. You should now see a linking error, since isEmpty() has been prototyped but not defined.
In Stack.cpp, add a definition for isEmpty() that will pass testIsEmpty(). This definition should be as simple as possible (e.g., a single line). If you get stuck, here is a hint, but don't use it unless you have to.
Recompile and rerun your test. Continue when you pass the test.
The other operations only work correctly on a non-empty Stack, so before we can test them, we need to be able to add items to a Stack. Since the push() method allows us to add items to a Stack, we will build that method; and since pushing items onto a stack can fill it, we will also build the isFull() and peekTop() methods.
In StackTester.cpp, uncomment the call to and definition of the testPushPeekTopAndIsFull() method. Take a moment to look over the tests it contains. The first test constructs a stack with capacity 1 and pushes an item onto it. We might visualize this stack as follows:
The second test constructs a stack with capacity 3 and pushes an item onto it. We might visualize this stack as follows:
The test then pushes a second item onto the stack:
The test then pushes a third item onto the stack, filling it:
Compile and run the test. You should see error messages indicating that push(), peekTop(), and isFull() do not exist.
In Stack.h, add a prototype for isFull() to the class. Recompile. Next, add a prototype for peekTop() to the class. Recompile. You should now see just the error for push(). Add a prototype for push(); then recompile. You should now get only linking errors, since isFull(), peekTop(), and push() have been declared in Stack.h but not defined.
In Stack.cpp, add a definition for isFull(). This definition should be as simple as possible (e.g., a single line).
Save/compile, and verify that the linking error for isFull() goes away. (The errors for peekTop() and push() should still be there.)
Define the peekTop() method. Save/recompile, and verify that what you have written compiles without errors. (You should still see a linking error for push().)
Define the push() method. Save/recompile, and verify that what you have written compiles and links without errors.
Run the tests. If you pass the tests, congratulations! If not, use the diagrams above to go back and fix your push(), peekTop(), and/or isFull() methods. If you get stuck, here are hints for push(), peekTop(), and isFull(), but only use them if you have to.
Continue when your methods pass all the tests.Our sole remaining operation is the pop() method, that removes and returns the top value from the Stack.
In StackTester.cpp, uncomment the call to and definition of the testPop() method. Compile and run the test. You should see an error message indicating that pop() does not exist.
In Stack.h, add a prototype for pop() to the class. Recompile and rerun. You should now see a linking error, since pop() has a prototype but no definition.
In Stack.cpp, add a definition for pop() that will pass testPop(). For now, this definition should be as simple as possible (e.g., it can be as short as a single line). If you get stuck, here is a hint, but don't use it unless you have to.
Recompile and rerun your test. Continue when you pass the test.
We now have a working Stack class, but it is lacking any error-handling capability. For example, what happens if a person pops an empty stack, or pushes an item onto a full stack? In Part II of today's exercise, we introduce C++'s programmer-defined exception mechanism, which provides a graceful way of handling such problems.
As we have seen with the C++ standard exceptions, an exception is an out-of-the-ordinary occurrence. The C++ standard exception classes in <stdexcept> are necessarily very general, describing broad categories of things that might go wrong. When you want to more precisely indicate what is going wrong, C++ lets us create our own exception classes.
In C++, a method that wants to indicate that something exceptional has occurred can throw an exception object back to the caller of the method. The pattern for the throw statement is:
throw ExceptionType(arguments);This constructs an exception object of type ExceptionType and throws it to the caller -- the subprogram that invoked the currently running method, terminating that method.
Back in the caller, the call to that method can be "wrapped" in a try-catch block, whose form is as follows:
try {
// risky code -- might throw an exception
} catch ( const ExceptionType & exceptionParameter ) {
// handler code -- to be executed if the exception occurs
}
The try block tries to perform the "risky code".
If that code works without throwing the exception,
control skips past the catch block to whatever follows it.
But if the "risky code" throws the exception named in the catch,
then control is transferred to the "handler" code in the catch block,
which does whatever is appropriate.
Note that since ExceptionType is pretty much always a class, it is preferable to define the catch block's parameter as a const-reference parameter. This has two advantages over using a value parameter: (i) it avoids the copying associated with a value parameter, and (ii) it lets this catch block catch exceptions of this exception-class or any subclasses derived from that class. We make it a const reference (i.e., read-only reference) parameter because the catch block should not make any changes to that parameter.
In StackTester.cpp, uncomment the very first try-catch block in method testPop():
try {
s1.peekTop();
cerr << "\npeekTop() worked on empty Stack" << flush;
exit(1);
} catch (const StackException& se) {
cout << se << endl;
cout << " 0a " << flush;
}
This block tries to send the peekTop() message to an empty stack,
and then catches the exception that should be thrown.
If the exception is not thrown, the statements that follow the
peekTop() message will execute, terminating the program.
If the exception is thrown,
control transfers from the statement invoking peekTop()
to the catch block, which displays the exception,
and then displays the
" 0a " that indicates our test has succeeded.
An alternative, simpler approach is to just display the " 0a "
in the catch block,
so if you wish, feel free to comment out that first line
that displays the exception.
Save/recompile your project. You should get several errors, because StackException has not been defined. Verify that that is the cause of your errors, then continue.
One way to provide exceptions for our Stack class is to define a separate StackException class that our Stack class can use when something goes wrong. The file: StackException.h, contains such a class:
class StackException {
public:
StackException(const string& whereThrown,
const string& message) {
myLocation = whereThrown;
myMessage = message;
}
string asString() const {
return "*** StackException in " +
myLocation + ": " + myMessage;
}
private:
string myLocation;
string myMessage;
}; // StackException
Save and import a copy of this file into your project, and personalize its opening comment.
The class has two instance variables:
StackException("pop()", "stack is empty")
If at the beginning of the the push() method, we find that the stack is full, we can build an exception like this:
StackException("push()", "stack is full")
The asString() method generates a string representation of these values, accompanied by some descriptive labels.
At the bottom of StackException.h, there is a definition of operator<< that lets us output a StackException using the usual C++ stream-insertion operator.
At the beginning of Stack.h, uncomment the #include directive that includes StackException.h.After making these changes, save/recompile your project. If all is well, your project should compile correctly. If not, find and correct the error(s).
When your project compiles correctly, run it. You should see execution halt in the testGetTop() method. The problem is that our testPop() method now expects a StackException to be thrown when we send the peekTop() message to an empty Stack. Continue, and we will see how to accomplish this.
Now that we have created a StackException class by which we can precisely describe unusual circumstances, we can use that class in our Stack methods. As mentioned previously, a method that detects a problematic circumstance can throw an exception. For example, if the stack is empty, there is no top item for the peekTop() method to return, in which case we might make it throw a StackException, as follows:
Item Stack::peekTop() const {
if ( isEmpty() ) {
throw StackException("peekTop()", "stack is empty");
}
return myArray[mySize - 1];
}
Recompile and rerun your project.
With these changes, what you have written should pass all the tests.
Continue when it does so.
Uncomment the try-catch block in the testConstructor() method. Then save/compile your project. Run it, and verify that it fails inside the try block.
Using what we did with peekTop() as a model, modify the Stack constructor so that when its precondition is false, the constructor throws a StackException with the message Stack(capacity): capacity must be positive!.
Once you have seen that the try-catch is working correctly, feel free to comment out the line in the catch block that displays the exception. Continue when your project passes all tests.
Uncomment the try-catch blocks in the testPop() method. Then save/compile your project. Run it, and verify that it fails inside one of the try blocks.
Using what we did with peekTop() as a model, modify pop() so that it throws a StackException with the message pop(): stack is empty!. In case you get stuck, here is a hint, but don't use it unless you need to. Continue when your project passes all tests.
Our final operation is the push() operation. Uncomment the try-catch blocks in testPushPeekTopAndIsFull(). Then save/recompile, and verify that your project no longer passes the test.
Using what we did previously as a model, modify push() so that it throws a StackException with the message push(): stack is full!. In case you get stuck, here is a hint, but don't use it unless you need to. Continue when your project passes all tests.
Now that you have tested the stack operations, uncomment the remaining test-methods and verify that the other Stack operations pass their tests.
Congratulations! You now have a full-featured dynamic (array-based) Stack class at your disposal!
Copy your lab folder to a new /home/cs/112/current/yourUserName/lab7 folder.
If time permits, you may begin working on this week's project.