*With the following code*

Write a pseudocode function that uses a stack 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}

Node.h

#pragma once

#include

template < class ItemType>

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;

};

template < class ItemType>

Node::Node() : next(nullptr)

{

} // end default constructor

template < class ItemType>

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

{

} // end constructor

template < class ItemType>

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

item(anItem), next(nextNodePtr)

{

} // end constructor

template < class ItemType>

void Node::setItem(const ItemType& anItem)

{

item = anItem;

} // end setItem

template < class ItemType>

void Node::setNext(Node* nextNodePtr)

{

next = nextNodePtr;

} // end setNext

template < class ItemType>

ItemType Node::getItem() const

{

return item;

} // end getItem

template < class ItemType>

Node* Node::getNext() const

{

return next;

}

#pragma once

#include

template < class ItemType>

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;

};

template < class ItemType>

Node::Node() : next(nullptr)

{

} // end default constructor

template < class ItemType>

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

{

} // end constructor

template < class ItemType>

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

item(anItem), next(nextNodePtr)

{

} // end constructor

template < class ItemType>

void Node::setItem(const ItemType& anItem)

{

item = anItem;

} // end setItem

template < class ItemType>

void Node::setNext(Node* nextNodePtr)

{

next = nextNodePtr;

} // end setNext

template < class ItemType>

ItemType Node::getItem() const

{

return item;

} // end getItem

template < class ItemType>

Node* Node::getNext() const

{

return next;

}

StackInterface.h

#pragma once

template class StackInterface { public: virtual bool isEmpty() const = 0; virtual bool push(const ItemType& newEntry) = 0; virtual bool pop() = 0; virtual ItemType peek() const = 0; };

LinkedStack.h

#pragma once

#include "StackInterface.h"

#include "Node.h"

#include

template < class ItemType>

class LinkedStack : public StackInterface

{

private:

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

/*Node* getPointerTo(const ItemType& target) const; */ // this node contains the stacks 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();

/*void validateAB(LinkedStack& bag);*/

ItemType peek() const;

/*bool contains(const ItemType& anEntry) const;*/

}; // end LinkedStack

template < class ItemType>

LinkedStack::LinkedStack() : topPtr(nullptr)

{

} // end default constructor

template < class ItemType>

LinkedStack::

LinkedStack(const LinkedStack& aStack)

{

// Point to nodes in original chain

Node* origChainPtr = aStack->topPtr;

if (origChainPtr == nullptr)

topPtr = nullptr; // Original bag is empty

else

{

// Copy first node

topPtr = new Node();

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

// Point to first node in new chain

Node* newChainPtr = topPtr;

// Copy remaining nodes

while (origChainPtr != nullptr)

{

// Advance original-chain pointer

origChainPtr = origChainPtr->getNext();

// 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();

} // end while

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

} // end if

} // end copy constructor

template < class ItemType>

LinkedStack::~LinkedStack()

{

// Pop until stack is empty

while (!isEmpty())

pop();

} // end destructor

template < class ItemType>

bool LinkedStack::isEmpty() const

{

return topPtr == nullptr;

} // end isEmpty

template < class ItemType>

bool LinkedStack::push(const ItemType& newItem)

{

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

topPtr = newNodePtr;

newNodePtr = nullptr;

return true;

} // end push

template < class ItemType>

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 < class ItemType>

ItemType LinkedStack::peek() const

{

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

// Stack is not empty; return top

return topPtr->getItem();

} // end getTop

LinkedStackMain.cpp

#include"LinkedStack.h"

#include

#include

using namespace std;

int main() {

StackInterface* link = new LinkedStack();

string anItem = "0";

cout << "Enter a string: ";

getline(cin, anItem);

link->push(anItem);

link->peek();

cout << link->peek() << endl;

cout << "Enter a string: ";

getline(cin, anItem);

link->push(anItem);

link->peek();

cout << link->peek() << endl;

link->pop();

cout << link->peek() << endl;

system("pause");

return 0;

}