CptS 122 –
Data Structures
Lab 11: Developing a Stack Class in C++
Assigned: Week of
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:
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;
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 / -
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: