[Data Structure C++]

Excercise description: Use LinkedStack to determine whether a string is in the language L, where

a. L = {s : s contains equal numbers of As and Bs}

b. L = {s : s is of the form AⁿBⁿfor some n>= 0}

Need to create a main for the code to test part a. and b. of the excercise and debug if necesary. Thank you!

Code:

#ifndef STACK_INTERFACE_H

#define STACK_INTERFACE_H

#include // std::cout

#include // std::stack

#include // std::vector

#include // std::deque

using namespace std;

#include

template

class StackInterface

{

public:

/** Sees whether this stack is empty.

@return True if the stack is empty, or false if not. */

virtual bool isEmpty() const = 0;

/** Adds a new entry to the top of this stack.

@post If the operation was successful, newEntry is at the top of the stack.

@param newEntry The object to be added as a new entry.

@return True if the addition is successful or false if not. */

virtual bool push(const ItemType& newEntry) = 0;

/** Removes the top of this stack.

@post If the operation was successful, the top of the stack

has been removed.

@return True if the removal is successful or false if not. */

virtual bool pop() = 0;

/** Returns the top of this stack.

@pre The stack is not empty.

@post The top of the stack has been returned, and

the stack is unchanged.

@return The top of the stack. */

virtual ItemType peek() const = 0;

}; // end StackInterface

#endif

//////////////////////////////////////////////////////////////

#ifndef NODE_H

#define NODE_H

template

class Node

{

private:

ItemType item; // A data item

Node* next; // Pointer to next node

public:

Node();

Node(const ItemType& anItem);

Node(const ItemType& anItem, Node* nextNodePtr);

void setItem(const ItemType& anItem);

void setNext(Node* nextNodePtr);

ItemType getItem() const ;

Node* getNext() const ;

}; // end Node

#endif

///////////////////////////////////////////////////////////////////////////////////

//#include "Node.h"

//#define nullptr NULL

#include

template

Node::Node() : next(nullptr)

{

} // end default constructor

template

Node::Node(const ItemType& anItem) : item(anItem), next(nullptr)

{

}

// end constructor

template

Node::Node(const ItemType& anItem, Node* nextNodePtr) :

item(anItem), next(nextNodePtr)

{

} // end constructor

template

void Node::setItem(const ItemType& anItem)

{

item = anItem;

} // end setItem

template

void Node::setNext(Node* nextNodePtr)

{

next = nextNodePtr;

} // end setNext

template

ItemType Node::getItem() const

{

return item;

} // end getItem

template

Node* Node::getNext() const

{

return next;

} // end getNext

///////////////////////////////////////////////////////////////////////////////////

#ifndef _LINKED_STACK

#define _LINKED_STACK

//#include "StackInterface.h"

//#include "Node.cpp"

//#define nullptr NULL

template

class LinkedStack : public StackInterface

{

private:

Node* topPtr; // Pointer to first node in the chain;

// this node contains the stack's top

public:

// Constructors and destructor:

LinkedStack(); // Default constructor

LinkedStack(const LinkedStack& aStack);// Copy constructor

virtual ~LinkedStack(); // Destructor

// Stack operations:

bool isEmpty() const;

bool push(const ItemType& newItem);

bool pop();

bool checkString(string s);

ItemType peek() const;

}; // end LinkedStack

#endif

///////////////////////////////////////////////////////////////

#include // For assert

//#include "LinkedStack.h" // Header file

template

LinkedStack::LinkedStack() : topPtr(nullptr)

{

} // end default constructor

template

LinkedStack::LinkedStack(const LinkedStack& aStack)

{

// Point to nodes in original chain

Node* origChainPtr = aStack.topPtr;

if (origChainPtr == nullptr)

topPtr = nullptr; // Original stack is empty

else

{

// Copy first node

topPtr = new Node();

topPtr->setItem(origChainPtr->getItem());

// Point to last node in new chain

Node* newChainPtr = topPtr;

// Advance original-chain pointer

origChainPtr = origChainPtr->getNext();

// Copy remaining nodes

while (origChainPtr != nullptr)

{

// Get next item from original chain

ItemType nextItem = origChainPtr->getItem();

// Create a new node containing the next item

Node* newNodePtr = new Node(nextItem);

// Link new node to end of new chain

newChainPtr->setNext(newNodePtr);

// Advance pointer to new last node

newChainPtr = newChainPtr->getNext();

// Advance original-chain pointer

origChainPtr = origChainPtr->getNext();

} // end while

newChainPtr->setNext(nullptr); // Flag end of chain

} // end if

}

// end copy constructor

template

LinkedStack::~LinkedStack()

{

// Pop until stack is empty

while (!isEmpty())

pop();

}

// end destructor

template

bool LinkedStack::isEmpty() const

{

return topPtr == nullptr;

} // end isEmpty

template

bool LinkedStack::push(const ItemType& newItem)

{

Node* newNodePtr = new Node(newItem, topPtr);

topPtr = newNodePtr;

newNodePtr = nullptr;

return true;

} // end push

template

bool LinkedStack::pop()

{

bool result = false;

if (!isEmpty())

{

// Stack is not empty; delete top

Node* nodeToDeletePtr = topPtr;

topPtr = topPtr->getNext();

// Return deleted node to system

nodeToDeletePtr->setNext(nullptr);

delete nodeToDeletePtr;

nodeToDeletePtr = nullptr;

result = true;

} // end if

return result;

} // end pop

template

ItemType LinkedStack::peek() const

{

assert(!isEmpty()); // Enforce precondition

// Stack is not empty; return top

return topPtr->getItem();

} // end getTop

// End of implementation file.

/////////////////////////////////////

//a. L = {s : s contains equal numbers of As and Bs}

template

bool LinkedStack ::checkString(string s)

{

//variables to store the count of A and B

int countA=0, countB=0;

//create the instance of linked stack to hold characters

LinkedStack *stackObj= new LinkedStack();

//loop invariant

int i=0;

//push the characters of the string into the stack

while(i

{

//push the character into the stack

stackObj->push(s[i++]);

}

//pop the characters from the stack

while(!stackObj->isEmpty())

{

//extract the top element

char top=stackObj->peek();

stackObj->pop();

//if the character is A increment count of A

if(top =='A')

countA++;

stackObj->pop();

//if the character is B increment count of B

if(top=='B')

countB++;

stackObj->pop();

}

//check the count of A and B, whether they are same

if(countA == countB)

return true;

else

return false;

}

/////////////////////

//b. L = {s : s is of the form A^n B^n for some n>= 0}

template

bool LinkedStack ::checkString(string s)

{

//create the instance of linked stack to hold characters

LinkedStack *stackObj= new LinkedStack();

//loop invariant

int i=0;

//push the character of the string into the stack if it is 'A'

while(i

{

//push the character into the stack

stackObj->push(s[i++]);

}

//pop an 'A' from stack for each occurence of 'B' in the string

while(iisEmpty())

{

stackObj->pop();

}

//check if the stack is empty and the string is also finished

if(i == s.length() && stackObj->isEmpty())

return true;

else

return false;

}

///////////////////////////////////////////////////////////////////////////////////

///////////////////////////////////////////////////////////////////////////////////

//MainProgram

#include

//#include "LinkedStack.cpp"

using namespace std;

int main()

{

return 0;

}