Operational Objectives: Create two generic container classes fsu::Stack and fsu:

Question

Operational Objectives: Create two generic container classes fsu::Stack and fsu::Queue that satisfy the interface requirements given below, along with appropriate test harnesses for these classes.

Deliverables: four files stack.t, queue.t, fstack.cpp, fqueue.cpp

Application: Converting Infix to Postfix Notation

As one example of the use of stacks and queues in computing, consider the following function that illustrates an algorithm for converting arithmetic expressions from infix to postfix notation:

This is a complex algorithm, but not beyond your capability to understand. The main points to displaying it here are: (1) to illustrate how stacks and queues may be used in implementing applications, and (2) to let you know that your code must be compatible with such apps. in2post.cpp is one of our tests!

Stack Implementation Plan

We will implement the stack abstraction as a C++ class template

with the following public methods:

There should be a full complement of self-management features:

The element and size data will be maintained in private variables:

The class constructors will have responsibility for initializing variables. Note that capacity_ is a constant, so it must be initialized by the constructor in the initialization list and it cannot be changed during the life of a stack object; capacity_ should be given the value passed in as the second template argument N. Because all class variables are declared at compile time, the destructor will have no responsibilities. Values stored in the data_ array and the size_ variable will be correctly maintained by the push and pop operations, using the "upper index" end of the data as the top of the stack. The data in the stack should always be the array elements in the range [0..size_), and the element data_[size_ - 1] is the top of the stack (assuming size_ > 0).

Please note that the data_ array is automatically allocated at compile time and remains allocated during the lifetime of the object. It is implicitly de-allocated just like any statically declared array, when it goes out of scope. Thus the underlying "footprint" of the stack object remains fixed as the size changes, even when the size is changed to zero. There should be no calls to operators new or delete in this implementation.

This implementation will have the requirement on clients that the maximum size required for the stack is known in advance and determined by the second template argument - see requirements below.

Queue Implementation Plan

We will implement the queue abstraction as a C++ class template Queue with the following public methods:

There should be a full complement of self-management features:

Unlike Stack, Queue requires access to data at both the front and back, which makes an array implementation impractical. We will use a linked list implementation using a link class defined as follows:

Note that all members of class Link are private, which means a Link object can be created or accessed only inside an implementation of its friend class Queue. The only method for class Link is its constructor, whose implementation should just initialize the two variables. (This can be done inside the class definition, as shown below.)

The private Queue variables for this implementation will be exactly two pointers to links, the first and last links created. Including the definition of the helper class Link, the private section of the class definition should be like the following (with implementor-chosen private variable names):

The class constructor will have responsibility for initializing the two variables to zero. These two pointers will be zero exactly when there is no data in the queue (the queue is empty). Links for data will be allocated as needed by Push() and de-allocated by Pop(). These operations will also need to re-direct appropriate link pointers in the dynamically allocated links, and maintain the class variables firstLink_ and lastLink_ correctly pointing to the links containing the first and last elements of the queue. The destructor should de-allocate all remaining dynamically allocated links in the queue. The Size() method will have to loop through the links to count them, whereas the Empty() method can do a simple check for emptiness of the queue.

Because this implementation relies on dynamically allocated memory, the container makes no restrictions on the client program as to anticipated maximum size of the queue.

Procedural Requirements

Define and implement the class template fsu::Stack in the file stack.t. Be sure to make log entries for your work sessions.

Devise a test client for Stack that exercises the Stack interface for at least one native type and one user-defined type T. Repair your code as necessary. Put this test client in the file fstack.cpp. Be sure to make log entries for your work sessions.

Define and implement the class template fsu::Queue in the file queue.t. Be sure to make log entries for your work sessions.

Devise a test client for Queue that exercises the Queue interface for at least one native type and one user-defined type T. Put this test client in the file fqueue.cpp. Be sure to make log entries for your work sessions.

Test Stack and Queue using the supplied application in2post.cpp. Again, make sure behavior is appropriate and make corrections if necessary. Log your activities.

Code Requirements and Specifications

Both Stack and Queue should be a proper type, with full copy support. That is, they should have a public default constructor, destructor, copy constructor, and assignment operator. Be sure that you test the copy constructor and assignment operator.

The Stack constructor should create a stack that is empty but has the capacity to hold N elements, where N is the second template parameter with type size_t. Note that this parameter should be given the default value of 100. This has the effect of making a declaration such as

fsu::Stack s;

legal and create a stack with capacity 100.

The Queue constructor should create an empty queue with no dynamic memory allocation.

The Queue::Push(t) operation must dynamically allocate memory required for storing t in the queue. Similarly, the Queue::Pop() operation must de-allocate memory used to store the element being removed from the queue.

As always, the class destructors should de-allocate all dynamic memory still owned by the object. The stack and queue implementations will be very different.

Use the implementation plans discussed above. No methods or variables should be added to these classes, beyond those specified above and in the implementation plans.

The Display(os, ofc) methods are intended to regurgitate the contents out through the std::ostream object os. The second parameter ofc is a single output formatting character that has the default value ''. (The other three popular choices for ofc are ' ', ' ' and ' '.) The implementation of Display must recognize two cases:

ofc == '': send the contents to output with nothing between them

ofc != '': send the contents to output with ofc separating them

Thus, for example, S.Display(std::cout) would send the contents of S to standard output.

The output operator should be overloaded as follows:

The overload of operator <<() should be placed in your stack/queue header file immediately following the class definition.

The classes Stack amd Queue should be in the fsu namespace.

The files stack.t and queue.t should be protected against multiple reads using the #ifndef ... #define ... #endif mechanism.

The test client programs fstack.cpp and fqueue.cpp should adequately test the functionality of stack and queue, respectively, including the output operator. It is your responsibility to create these test programs and to use them for actual testing of your stack and queue data structures.

Hints

Your test clients can be modelled on the harness fbitvect.cpp distributed as part of a previous assignment.

It is recommended that you carry the stack portion of the project through to completion, including implementation and testing, before starting on the queue portion. The implementation plan for Stack uses design and methodology that you already have experience with. The implementation plan for Queue uses design and methodology that is very different and new.

Keep in mind that the implementations of class template methods are in themselves template functions. For example, the implementation of the Stack method Pop() would look something like this:

and the Queue method Pop() would look something like this:

We will test your implementations using (1) your supplied test clients, (2) in2post, and (3) test clients of our own design.

There are two versions of Stack::Top() and Queue::Front(). These are distunguished by "const" modifiers for one of the versions. The implementation code is identical for each version. The main point is that "Top()" can be called on a constant stack, but the returned reference may not be used to modify the top element. This nuance will be tested in our assessment. You can test it with two functions such as:

Note that ShowTop has a const reference to a stack, so would be able to call the const version of Top() but not the non-const version, but that suffices. ChangeTop would need to call the non-const version in order to change the value at the top of the stack. A simple test named "constTest.cpp" is posted in the distribution directory.

Explanation / Answer

#include <iostream>
#include <conio.h>
#include <tqueue.h>
#include <tstack.h>

const int BATCH = 0;
const unsigned int colsize = 25;

class Symbol
{
public:
int Isopr ();
unsigned char ch;
} ;

int Symbol::Isopr ()
{
int getval = 0;
if (ch == '+' || ch == '-' || ch == '*' || ch == '/' || ch == '%')
getval = 1;
return getval;
}

int opr >= (Symbol t1, Symbol t2)
{
int getval = 0;
if (t1.ch == t2.ch)
getval = 1;

else
switch (t1.ch)
{
case '*': case '/': case '%':
switch (t2.ch)
{
case '+': case '-':
getval = 1;
break;
}
break;
}
return getval;
}

int opr == (Symbol t1, Symbol t2)
{
return t1.ch == t2.ch;
}

int opr != (Symbol t1, Symbol t2)
{
return t1.ch != t2.ch;
}

int opr <= (Symbol t1, Symbol t2)
{
return (t2 >= t1);
}

int opr < (Symbol t1, Symbol t2)
{
return (t2 >= t1 && t1 != t2);
}

int opr > (Symbol t1, Symbol t2)
{
return (t2 > t1);
}

std::ostream& opr << (std::ostream& os, const Symbol& t)
{
os << t.ch;
return os;
}

typedef fsu::TQueue < Symbol > SymbolQ;
typedef fsu::TStack < Symbol > SymbolStack;

void ShowHeader (std::ostream& os = std::cout)
{
int i;
os << "S"; for (i = 0; i < colsize - 1; ++i) os << ' ';
os << "Q1"; for (i = 0; i < colsize - 2; ++i) os << ' ';
os << "Q2 ";
os << "--"; for (i = 0; i < colsize - 2; ++i) os << ' ';
os << "--"; for (i = 0; i < colsize - 2; ++i) os << ' ';
os << "-- ";
}

int i2p (SymbolQ & Q1, SymbolQ & Q2)
{
Symbol L, R;
L.ch = '(';
R.ch = ')';
SymbolStack S;
Q2.Clear();
ShowHeader();
Show(S, Q1, Q2);
while (!Q1.Empty())
{
if (Q1.Rear() == L)

{
S.Push(Q1.Rear());
Q1.Pop();
Show(S, Q1, Q2);
}
else if (Q1.Rear().Isopr())
{
while (!S.Empty() && S.Top() >= Q1.Rear())
{
Q2.Push(S.Top());
S.Pop();
Show(S, Q1, Q2);
}

S.Push(Q1.Rear());
Q1.Pop();
Show(S, Q1, Q2);
}
else if (Q1.Rear() == R)

{
while (!S.Empty() && !(S.Top() == L))
{
Q2.Push(S.Top());
S.Pop();
Show(S, Q1, Q2);
}
if (S.Empty())
{
std::cout << "Error: too many right parens ";
return 0;
}
S.Pop();
Q1.Pop();
Show(S, Q1, Q2);
}
else

{
Q2.Push(Q1.Rear());
Q1.Pop();
Show(S, Q1, Q2);
}
}
while (!S.Empty())
{
if (S.Top() == L)
{
std::cout << "Error: too many left parens ";
return 0;
}
Q2.Push(S.Top());
S.Pop();
Show(S, Q1, Q2);
}
return 1;
}

void Show (SymbolStack& S, SymbolQ& Q1, SymbolQ& Q2, std::ostream& os = std::cout)
{
int i;
if (!S.Empty())
{
os << S;
if (colsize > S.Size())
for (i = 0; i < colsize - S.Size(); ++i)
os << ' ';
}
else
{
os << "NULL";
if (colsize > 4)
for (i = 0; i < colsize - 4; ++i)
os << ' ';
}
if (!Q1.Empty())
{
os << Q1;
if (colsize > Q1.Size())
for (i = 0; i < colsize - Q1.Size(); ++i)
os << ' ';
}
else
{
os << "NULL";
if (colsize > 4)
for (i = 0; i < colsize - 4; ++i)
os << ' ';
}
if (!Q2.Empty())
{
os << Q2;
}
else
{
os << "NULL";
}
os << ' ';
}

int main()
{
std::cout<< " This program dispalys the conversion of infix to postfix expressions. "
<< " No arithmetic is done. The purposes is to show algorithm in effective way, "
<< " only single-character symbols are assumed. ";

char c;
SymbolQ Q1, Q2;
Symbol t;
while(1)
{
std::cout << "Enter 0 to quit: ";
std::cin.get(c);
if (BATCH) std::cout.put(c);
if (c == '0')
{
if (BATCH) std::cout.put(' ');
break;
}
while (c != ' ')
{
t.ch = c;
Q1.Push(t);
std::cin.get(c);
if (BATCH) std::cout.put(c);
}
std::cout.put(' ');
if (i2p(Q1, Q2))
{
std::cout << " postfix conversion: " << Q2 << ' ';
}
else
{
std::cout << " syntax error in infix expression" << ' ';
}
}
return 0;
}

Related Questions

Navigate

• Browse (All)
• Browse O
• Subjects

Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.