Description
In today’s lab we will design and implement the Stack ADT using linked list.
stacktype.h
#ifndef STACKTYPE_H_INCLUDED
#define STACKTYPE_H_INCLUDED
class FullStack
{};
class EmptyStack
{};
template
class StackType
{
struct NodeType
{
ItemType info;
NodeType* next;
};
public:
StackType();
~StackType();
void Push(ItemType);
void Pop();
ItemType Top();
bool IsEmpty();
bool IsFull();
private:
NodeType* topPtr;
};
#endif // STACKTYPE_H_INCLUDED
stacktype.cpp
#include
#include “stacktype.h”
using namespace std;
template
StackType::StackType()
{
topPtr = NULL;
}
template
bool StackType::IsEmpty()
{
return (topPtr == NULL);
}
template
ItemType StackType::Top()
{
if (IsEmpty())
throw EmptyStack();
else
return topPtr->info;
}
template
bool StackType::IsFull()
{
NodeType* location;
try
{
location = new NodeType;
delete location;
return false;
}
catch(bad_alloc& exception)
{
return true;
}
}
template
void StackType::Push(ItemType newItem)
{
if (IsFull())
throw FullStack();
else
{
NodeType* location;
location = new NodeType;
location->info = newItem;
location->next = topPtr;
topPtr = location;
}
}
template
void StackType::Pop()
{
if (IsEmpty())
throw EmptyStack();
else
{
NodeType* tempPtr;
tempPtr = topPtr;
topPtr = topPtr->next;
delete tempPtr;
}
}
template
StackType::~StackType()
{
NodeType* tempPtr;
while (topPtr != NULL)
{
tempPtr = topPtr;
topPtr = topPtr->next;
delete tempPtr;
}
}
Ge
nerate the driver file (main.cpp) where you perform the following tasks. Note that you cannot make any change to
the header file or the source file.
Operation to Be Tested and Description of Action Input Values Expected Output
• Take infix expressions from the user as input,
determine the outcome of the expression and gives
that back to user as output, or the text “Invalid
expression” if the expression is not a valid one.
You will have to solve this problem in two steps. First, you
have to convert the expression from infix notation to
postfix notation. You are going to need a stack in
order to do so. In the next step, you will have to
evaluate the postfix expression and determine the
final result.
Again, you will need a stack in order to
do this. All the operands in the infix expressions are
single digit non-negative operands and the operators
include addition (+), subtraction (-), multiplication (*)
and division (/).
10 + 3 * 5 / (16 – 4)
(5 + 3) * 12 / 3
3 + 4 / (2 – 3) * / 5
7 / 5 + (4 – (2) * 3
11.25
32
Invalid expression
Invalid expression