COMP 15 Project #6: Stack ADT using linked list

COMP15 Fall 20XX
Due: Wednesday, November 10, 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 #4 to test and validate your new implementation. You must also incorporate the new ADT implementation into the RPN expression evaluator developed in Project #5.

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

Only two files are provided, list_stack.h and eval_stack.h. Both files are available in the directory /g/15/class/project6. You must also reuse the evaluation stack class and testing code developed in Project #4 and the lexical analyzer and RPN expression evaluation code in Project #5.

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 should catch and handle exceptions thrown by new. The stack destructor should deallocate any dynamic storage when it is called to prevent memory leaks.

You should use your evaluation stack module and testing code from Project #4 to check out the new implementation. You must also test your new stack ADT using the RPN evaluator developed in Project #5. You may, of course, add new tests.

Here are some additional requirements to be satisfied:

• You must use and provide a makefile to build your solution. Your makefile must build two programs: a test program for the new stack module and an RPN evaluation program, which also uses the new stack module.
• Add comments to the source code to describe your approach and solution.

Submitting your work

Use the provide system to submit your finished program:

    provide comp15 a6 makefile list_stack.h ...

    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
    lexan.h          Declaration of the lexical analysis interface
    lexan.cpp        Implementation of the lexical analyzer
    eval_main.cpp    RPN evaluation driver
    test_main.cpp    Test driver
    makefile         makefile to build everything

Extra credit

Here are two additional requirements for extra credit:

• Extend the stack ADT, evaluation stack, lexical analyzer and RPN evaluator to handle both integer and floating point arithmetic. (Yep, you get a second shot at this one! :-)
• Implement and test an overloaded assignment operator for the stack base class.