COMP15 Project #5: Stack ADT using linked list

COMP 15 Project #5: Stack ADT using linked list

COMP15 Spring 20XX
Due: Thursday, March 17, 11:00PM

Overview

One of the chief advantages of the abstract datatype (ADT) approach is the encapsulation of design and implementation decisions within reusable modules. Through encapsulation, the developer has the freedom to change the implementation of an ADT without modifying either the interface to the ADT or the code that uses it.

The goal of this project is to reimplement the stack ADT using a linked list to store and manipulate items on the stack. You must reuse the testing code developed in Project #3 to test and validate your new implementation.

Objectives

The objectives for this project are:

To implement the stack ADT using a linked list.
To learn about and apply dynamic storage allocation, pointers and linked lists.
To implement a destructor and copy constructor for a class using dynamic storage allocation.
To gain further experience with software reuse and testing.

What needs to be done

Several files are provided:

list_stack.h, which is the declaration of the Stack class and its interface.
list_stack.cpp, which contains the definitions of the functions in the Stack class.
eval_stack.h, which is the declaration of the EvalStack interface.
list_main.cpp and eval_main.cpp, for preliminary testing of the two stack classes.
makefile, which is to be used for building the test programs.

All files are available in the directory /g/15/class/project5. You must reuse the evaluation stack class and any testing code developed in Project #3.

You will need to reimplement the stack ADT using the files list_stack.h and list_stack.cpp. The new implementation must use a linked list to maintain the contents of the stack. Stack items should be allocated and deallocated dynamically. You will need to add private data members to list_stack.h to manage the linked list. You must provide a copy constructor for the new stack class that makes a complete copy of the stack when called.

The stack ADT implementation must allocate storage for each item when it's needed and deallocate storage for each item when the item is no longer needed. Your code must catch and handle exceptions thrown by new using try/catch blocks. The stack destructor, the clear operation and the pop operation must deallocate (delete) any dynamic storage to prevent memory leaks.

You should use your evaluation stack module and testing code from Project #3 to check out the new implementation. You may, of course, add new tests.

Just for fun, try the new stack ADT with the RPN evaluator developed in Project #4. Everything should work together!

Here are some additional requirements to be satisfied:

You must use the supplied makefile to build your solution. Using this makefile will produce two executable programs: stacktest and evaltest. The stacktest program tests the base class (Stack) and the evaltest program tests the derived class (EvalStack.)
You must thoroughly and systematically test the stack and evaluation stack interfaces. A basic "smoke test," that you may extend, is included in list_stack.cpp. You must provide all of the testing code for eval_stack.cpp.
Add comments to the source code to describe your approach and solution.

Don't forget to fill out any header comments with your name, section and e-mail address.

Submitting your work

Use the provide system to submit your finished program:

    /local/bin/provide comp15 p5 makefile list_stack.h ...

The files to be submitted are:

    list_stack.h      Declaration of stack interface
    list_stack.cpp    Definition of stack
    eval_stack.h      Declaration of evaluation stack interface
    eval_stack.cpp    Definition of evaluation stack
    array_main.cpp    Test code for the base class
    eval_main.cpp     Test code for the derived class
    makefile          makefile to build everything

Be sure you are completely satisfied with your work before submitting! Build and test your program on comp15.cs.tufts.edu before submitting your work. This system is the target build and test platform for all course projects. Projects which do not build correctly receive a score of zero.

Extra credit

Here is an additional requirement for extra credit:

Implement and test an overloaded assignment operator for the stack base class.

Informal interface specification: Stack

See the informal interface specification for Project #3 for the other functions in the Stack class. The push, pop and clear operations must use the C++ new and delete operations to allocate and release storage dynamically. Remember to check for exceptions using try/catch blocks.

Function: Stack(const Stack &old)
  Purpose: 
    Copy constructor that makes a complete copy of an old
    exisiting stack
  Parameters:
    old: Existing stack to be copied (reference parameter)
  Returns:
    Nothing
  Error conditions:
    Dynamic storage exhausted (new operation failed)

Function: ~Stack()
  Purpose: 
    Deallocates (deletes) any items in the stack
  Parameters:
    None
  Returns:
    Nothing
  Error conditions:
    None