class FullStack
{
	// Exception class used by Push when the stack is full.
};

class EmptyStack
{
	// Exception class used by Pop and Top when the stack is empty.
};

// Declaration of struct NodeType
template <typename ItemType>
struct NodeType;

// Specification part of class StackType
template <typename ItemType>

class StackType
{
private:
	int size; // The number of elements in the stack.
	NodeType<ItemType>* topPtr; // Pointer to the top element of the 
								// stack.

public:
	StackType(); // Constructor
	int getSize() const;
	bool isEmpty() const;
	bool isFull() const;
	void Push(ItemType item);
	void Pop();
	ItemType Top() const;
	ItemType findSum() const;
	void replaceItem(ItemType oldItem, ItemType newItem);
	void print() const;
	~StackType(); // Destructor
};

// Definition of struct NodeType
template <typename ItemType>
struct NodeType
{
	ItemType info;
	NodeType *next;
};

// Implementation part of class StackType

#include <cstddef>  // For NULL
#include <new>      // For bad_alloc
using namespace std;

template <typename ItemType>
StackType<ItemType>::StackType()
{
	size = 0;
	topPtr = NULL; // or topPtr = 0;
}

template <typename ItemType>
int StackType<ItemType>::getSize() const
{
	return size;
}

template <typename ItemType>
bool StackType<ItemType>::isEmpty() const
{
	return (topPtr == NULL);
}


template <typename ItemType>
bool StackType<ItemType>::isFull () const
{
	NodeType<ItemType> *location;
	try
	{
		location = new NodeType<ItemType>;
		delete location;
		return false;
	}
	catch(bad_alloc exception)
	{
		return true;
	}
}

template <typename ItemType>
void StackType<ItemType>::Push(ItemType newItem)
{
	if (isFull())
		throw FullStack();
	else
	{
		NodeType<ItemType> *location;
		location = new NodeType<ItemType>;
		location -> info = newItem;
		location -> next = topPtr;
		topPtr = location;
		size++;
	}
}




template <typename ItemType>
void StackType<ItemType>::Pop()
{
	if (isEmpty())
		throw EmptyStack();
	else
	{
		NodeType<ItemType> *tempPtr;
		tempPtr = topPtr;
		topPtr = topPtr -> next;
		delete tempPtr;
		size--;
	}
}

template <typename ItemType>
ItemType StackType<ItemType>::Top() const
{
	if (isEmpty())
		throw EmptyStack();
	else
		return topPtr -> info;
}

template <typename ItemType>
ItemType StackType<ItemType>::findSum() const
{
	if (isEmpty())
		throw EmptyStack();
	ItemType sum = 0;
	NodeType<ItemType> *tempPtr = topPtr;
	while (tempPtr != NULL)
	{
		sum = sum + tempPtr -> info;
		tempPtr = tempPtr -> next;
	}
	return sum;	
}

template <typename ItemType>
void StackType<ItemType>::replaceItem(ItemType oldItem, ItemType newItem)
{
	NodeType<ItemType> *tempPtr = topPtr;
	while (tempPtr != NULL)
	{
		if (tempPtr -> info == oldItem)
			tempPtr -> info = newItem;
		tempPtr = tempPtr -> next;
	}	
}

template <typename ItemType>
void StackType<ItemType>::print() const
{
	if (topPtr == NULL)
		cout << "The stack is empty.\n";
	else
	{
		cout << "The elements of the stack are: \n";
		NodeType<ItemType> *tempPtr = topPtr;
		while (tempPtr != NULL)
		{
			cout << tempPtr -> info << '\t';
			tempPtr = tempPtr -> next;
		}
		cout << endl;
	}
}


template <typename ItemType>
StackType<ItemType>::~StackType()
{
	NodeType<ItemType> *tempPtr;
	while (topPtr != NULL)
	{
		tempPtr = topPtr;
		topPtr = topPtr -> next;
		delete tempPtr;
	}
}
//Driver Program:

#include <iostream>
#include <string>
// #include "StackType.h"
using namespace std;

int main()
{
	StackType<float> stack;
	try
	{
			stack.Push(3.5);
			stack.Push(2.5);
	}
	catch(FullStack)
	{
		cout << "The stack is full. The element "
			<< "wasn't inserted.\n";
	}		
	
	try
	{
		cout << "Sum = " << stack.findSum() << endl;
	}
	catch (EmptyStack)
	{
		cout << "The stack is empty.\n";
	}
	stack.print();
	stack.replaceItem(3.5,8);
	cout << "Stack after replacement:\n";
	stack.print();
	cout << endl << endl;
	return 0;
}