COMP15 Project #4: Stack ADTs

COMP 15 Project #4: Stack ADTs

COMP15 Fall 20XX
Due: Wednesday, October 20, 11:00PM

Overview

Stacks are useful in a large number of computing applications. One of the most basic stack applications is the evaluation of expressions, like the operand stack in PostScript or the floating point evaluation stack in the Intel Pentium processor.

An evaluation stack with arithmetic operations is a specialization of a stack abstract datatype (ADT) with ordinary push and pop operations. This is an example of an is-a relationship between two classes where the evaluation stack is a special kind of stack ADT.

This project will develop two reusable stack modules:

A simple stack class, and
An evaluation stack class.

The evaluation stack will be implemented as a separate, derived class using the simple stack class as the base class. This arrangement is often called "inheritance" because the derived class inherits the member (method) functions and data members of the base class.

Objectives

The objectives for this project are:

To construct a reusable module to perform stack operations.
To construct a reusable module to evaluate RPN expressions.
To test both modules systematically and rigorously.
To use inheritance to extend the stack ADT into an evaluation stack ADT.

This module will be reused in the fifth, sixth and seventh assignments.

What needs to be done

Two files are provided: stack.h, which is the declaration of the Stack class and its interface, and eval_stack.h, which is the declaration of the EvalStack interface. These two files will help get you started with the project. You need to copy these files from the directory /g/15/class/project4 to your own working directory and use them as the starting point for development.

You will need to implement the Stack class (stack.cpp) and the EvalStack class (eval_stack.cpp.) Informal interface specifications are given below for each module. Here are some additional requirements to be satisfied:

You must use and provide a makefile to build your solution.
You must thoroughly and systematically test the stack and evaluation stack interfaces. You will reuse this test code to exercise future implementations of the evaluation stack interface in later assignments. It's a smart investment to develop thorough tests now.

Add comments to the source code to describe your approach and solution. Don't forget to fill out the header comments with your name, section and e-mail address.

On-line resources

The on-line C++ tutorial by Tom Anderson has a section devoted to classes and inheritance. The example in that section is a stack implemented using linked lists. (You will implement a linked list version of the stack in assignment #6 and do not need to know linked lists to do this assignment.)

Submitting your work

Use the provide system to submit the finished program:

    provide comp15 a4 stack.h stack.cpp ...

The files to be submitted are:

    stack.h          Decelaration of stack interface
    stack.cpp        Definition of stack
    eval_stack.h     Declaration of evaluation stack interface
    eval_stack.cpp   Definition of evaluation stack
    main.cpp         Test code
    makefile         makefile to build everything

Be sure you are completely satisfied with your work before submitting!

Informal interface specification: Stack

Function: Stack::Stack()
  Purpose: 
    Constructor that creates and initializes a new stack object;
    The stack is initially empty
  Parameters:
    None
  Returns:
    Nothing
  Error conditions:
    None

Function: Stack::clear()
  Purpose: 
    Resets the stack to its empty state
  Parameters:
    None
  Returns:
    Nothing
  Error conditions:
    None

Function: Stack::push
  Purpose: 
    Pushes the specified value onto the stack
  Parameters:
    value: Value to be pushed on top of the stack
  Returns:
    Nothing
  Error conditions:
    Stack overflow

Function: Stack::pop
  Purpose: 
    Pops the top element from the stack and returns its value
  Parameters:
    None
  Returns:
    Value from top of stack
  Error conditions:
    Stack underflow

Function: Stack::getTop
  Purpose: 
    Returns the value of the top element on the stack
  Parameters:
    None
  Returns:
    Current top of stack
  Error conditions:
    Stack empty

Function: Stack::isEmpty
  Purpose: 
    Detects the empty stack condition
  Parameters:
    None
  Returns:
    True if stack is empty; otherwise false
  Error conditions:
    None

Function: Stack::showAll
  Purpose: 
    Displays all of the elements in the stack. Displays
    the elements in order from left to right, starting
    with the current top of stack and ending with the
    bottom of the stack. Displays a "<>" symbol to
    signify the bottom of the stack.
  Parameters:
    None
  Returns:
    Nothing
  Error conditions:
    None

Function: Stack::showTop
  Purpose: 
    Displays the top element on the stack (without popping)
  Parameters:
    None
  Returns:
    Nothing
  Error conditions:
    Stack empty

Informal interface specification: EvalStack

Function: EvalStack::EvalStack()
  Purpose: 
    Constructor that creates and initializes a new evaluation
    stack object
  Parameters:
    None
  Returns:
    Nothing
  Error conditions:
    None

Function: EvalStack::add
  Purpose: 
    Pop and add top two items, push sum
  Parameters:
    None
  Returns:
    Nothing
  Error conditions:
    Stack underflow, stack overflow

Function: EvalStack::sub
  Purpose: 
    Pop and subtract top two items, push difference; ; Top of
    stack at time of call is the subtrahend to be subtracted
    from the minuend
  Parameters:
    None
  Returns:
    Nothing
  Error conditions:
    Stack underflow, stack overflow

Function: EvalStack::mul
  Purpose: 
    Pop and multiply top two items, push product
  Parameters:
    None
  Returns:
    Nothing
  Error conditions:
    Stack underflow, stack overflow

Function: EvalStack::div
  Purpose: 
    Pop and divide top two items, push quotient; Top of
    stack at time of call is the divisor (denominator)
  Parameters:
    None
  Returns:
    Nothing
  Error conditions:
    Stack underflow, stack overflow, division by zero

Function: EvalStack::mod
  Purpose: 
    Pop and divide top two items, push remainder; Top of
    stack at time of call is the divisor (denominator)
  Parameters:
    None
  Returns:
    Nothing
  Error conditions:
    Stack underflow, stack overflow, division by zero

Function: EvalStack::neg
  Purpose: 
    Pop and take arithmetic negative of top item, push result
  Parameters:
    None
  Returns:
    Nothing
  Error conditions:
    Stack underflow, stack overflow

Function: EvalStack::abs
  Purpose: 
    Pop and take absolute value, push result
  Parameters:
    None
  Returns:
    Nothing
  Error conditions:
    Stack underflow, stack overflow