CptS 122 – Data Structures                                                                         

 

Lab 11: Developing a Stack Class in C++

 

Assigned: Week of November 5, 2012

Due: At the end of the lab session

 

I. Learner Objectives:

 

At the conclusion of this programming assignment, participants should be able to:

 

II. Prerequisites:

 

Before starting this programming assignment, participants should be able to:

 

III. Overview & Requirements:

 

This lab, along with your TA, will help you navigate through designing, implementing, and testing a Stack class in C++. It will also help you with understanding how to apply a stack object to an application.

 

Labs are held in a “closed” environment such that you may ask your TA questions. Please use your TAs knowledge to your advantage. You are required to move at the pace set forth by your TA. Please help other students in need when you are finished with a task. You may work in pairs if you wish. However, I encourage you to compose your own solution to each problem. Have a great time! Labs are a vital part to your education in CptS 122 so work diligently.

For this lab you will develop a Stack class and use it to solve the parenthesis matching problem that is associated with arithmetic expressions. You will create the StackNode and Stack declarations in a single .h file, called Stack.h, and define all of the functionality in Stack.cpp.

Task 1. Defining a class, StackNode

 

Start this task by designing the StackNode class for the Stack. For the initial development you should just build the node to hold a char as its data. The StackNode class will consist of a character and a pointer to the next node. It will be able to make a new node using it’s constructor.

 

You will also overload the stream insertion operator << to output a node.

 

Finally, you will need to make the class Stack a friend of the StackNode class so that the class Stack will be able to access the member data of the StackNode, but still keep it private from every one else. Do this by including the statement:

           friend class Stack;

 Ok, now that you have this, create the forward declaration for the class stack

           class Stack;  // this is a forward declaration; required so the compiler will not report is an undeclared identifier; Stack will be declared soon after StackNode

 

Task 2. Now create the Stack class

                                               

Implement a Stack class. You are now ready to define the Stack class. You should create attribute members for the size of the Stack and a pointer that will be the top of the Stack. The pointers should be of type * StackNode.

 

You will also implement the constructor, the copy constructor, the assignment operator, and the destructor.

Additionally, you need:

          push ()  that adds an item to the stack.

          Pop ()   that removes an item from the top of the stack.

          top ()   returns the top element of the stack, the stack is unchanged.

          isEmpty ()  that is a Boolean function that indicates that the stack is empty or not.

           

You will overload the stream insertion operator << to output a stack in a elegant way.

 

Task 3. Postfix Evaluation with a stack. You have done this in C before!

 

Build a function that will complete a postfix evaluation of a given input string using your stack implementation. The function should return the value of the expression. Test your implementation on the following inputs; you can assume that the inputs are valid.

 

6  2  +  5  *  8  4  /  -

5  6  2 *  + 9  /

4  5  /  6  8  *  -

 

Algorithm for Evaluating Postfix Expressions

  1. Let S be an empty stack.
  2. If there is no character to read, then the postfix expression is malformed.  This error in the input string should be reported and the program should give up on that string.
  3. Read the next character and call it c.
  4. If c is the symbol '='
    1. If S is empty, then the postfix expression is malformed.  This error in the input string should be reported and the program should give up on that string.
    2. If S has more than one element, then the postfix expression is malformed.  This error in the input string should be reported and the program should give up on that string.
    3. If S has exactly one element, call it e.  The value of the postfix expression is e.  Return e.
  5. If c is a digit, then push c onto S and go to Step 2.
  6. If c is a binary operator, call it o
    1. If S does not have at least two elements, then the postfix expression is malformed.  This error in the input string should be reported and the program should give up on that string.
    2. Otherwise, pop two elements off of S.  Call the first one popped s2 and the second one popped s1.  I.e., s1 was below s2 in S prior to the popping.
    3. Apply the operator, o, to s1 and s2 (in that order) to obtain a value called v.
    4. push v onto S.
    5. Go to Step 2.

 

Task 4. Convert infix to postfix. Yes! You have implemented this in C before. Please take note of the differences between implementing this with a procedural language like C and an object oriented language like C++! OOP really requires a different thought process.

 

Using your stack implementation, create a function that will convert a given infix expression (string) to a postfix expression.

 

See the page infix2postfix for an explanation and algorithm.

 

IV. Submitting Labs:

 

V. Grading Guidelines: