COMP15 Project #3: Stack ADT

COMP 15 Project #3: Stack ADT

COMP15 Spring 20XX
Due: Monday, February 28, 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 (Stack), and
An evaluation stack class (EvalStack.)

The evaluation stack will be implemented as a separate, derived class using the simple stack class as the base class. This arrangement is called "inheritance."

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.

The stack modules will be reused and/or modified in projects #4, #5 and #6.

What needs to be done

Seven files are provided:

array_stack.h, which is the declaration of the Stack class and its interface,
array_stack.cpp, which contains the definitions of the functions in the Stack class,
eval_stack.h, which is the declaration of the EvalStack interface,
eval_stack.cpp, which contains the definitions of the functions in the EvalStack class,
Two files, array_main.cpp and eval_main.cpp, for testing your stack classes.
A makefile, which is to be used for building the test programs.

These files will help get you started with the project. You need to copy these files from the directory /g/15/class/project3 to your own working directory and use them as the starting point for development.

You will need to implement the Stack class (array_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 the makefile to build your solution. Using this makefile produces 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 "smoke test" for the base class is provided in array_main.cpp. You may extend this code. You must provide all of the testing code in eval_main.cpp to test the evaluation stack.

You will reuse all test code to exercise future implementations of the stack ADTs in later projects. 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 project #5 and do not need to know linked lists to do this project.)

Submitting your work

Use the provide system to submit the finished program:

    /local/bin/provide comp15 p3 makefile array_stack.h array_stack.cpp ...

The files to be submitted are:

    array_stack.h     Decelaration of stack interface
    array_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!

Informal interface specification: Stack

Function: 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:
    If there is not enough space for the new item
    (stack overflow), display an error message (to
    cerr) and leave the stack unchanged

Function: Stack::exchange
  Purpose: 
    Interchanges top two items on the stack
  Parameters:
    None
  Returns:
    Nothing
  Error conditions:
    If stack is empty or contains only one item, display
    error message (to cerr) and leave stack unchanged

Function: Stack::pop
  Purpose: 
    Pops the top item from the stack and returns its value
  Parameters:
    None
  Returns:
    Value from top of stack
  Error conditions:
    If stack is empty (stack underflow), display error
    message (to cerr) and return 0.0

Function: Stack::getTop
  Purpose: 
    Returns the value of the top element on the stack
  Parameters:
    None
  Returns:
    Current top of stack
  Error conditions:
    If stack is empty (stack underflow), display error
    message (to cerr) and return 0.0

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 items in the stack. Displays
    the items in order from left to right, starting
    with the current top of stack and ending with the
    bottom of the stack. Displays a "<>" symbol after all
    items to signify the bottom of the stack.
  Parameters:
    None
  Returns:
    Nothing
  Error conditions:
    None

Function: Stack::showTop
  Purpose: 
    Displays the top item on the stack (without popping);
    Displays "<>" when the stack is empty
  Parameters:
    None
  Returns:
    Nothing
  Error conditions:
    None

Informal interface specification: EvalStack

Function: 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 and stack overflow inherited from the
    Stack base class

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 and stack overflow inherited from the
    Stack base class

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

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 and stack overflow inherited from the
    Stack base class; If division by zero is attempted, display
    an error message (to cerr) and leave the stack unchanged

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

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

Function: EvalStack::sqroot
  Purpose: 
    Pop value, takes thesquare root and push the result
  Parameters:
    None
  Returns:
    Nothing
  Error conditions:
    Stack underflow and stack overflow inherited from the
    Stack base class; if operand is negative, display error
    message (to cerr) and leave stack unchanged