Question & Answer: (C++ Data Structure) Having problems with ths code (Error: Use of class template 'LinkedStack' requires template argu…..

(C++ Data Structure) Having problems with ths code (Error: Use of class template ‘LinkedStack’ requires template arguments) , I’m supposed to write a pseudocode function that uses LinkedStack to determine whether a string is in the language L, where

a. L = {s : s contains equal numbers of A’s and B’s}

b. L = {s : s is of the form An Bn for some n 0}

Show output.

LinkedStack:

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

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

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

//#include “Node.cpp”

//#endif

// Created by Frank M. Carrano and Tim Henry.

// Copyright (c) 2013 __Pearson Education__. All rights reserved.

/** @file Node.cpp

Listing 4-2 */

//#include “Node.h”

#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.h”

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

ItemType peek() const;

}; // end LinkedStack

//#include “LinkedStack.cpp”

//#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.

Functions:

#include

using namespace std;

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

 

//if the character is A increment count of A

if (top ==’A’)

countA++;

//if the character is B increment count of B

if(top==’B’)

countB++;

}

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

 

if(countA==countB)

 

return true;

 

else

 

return false;

}

bool checkStringb(string s)

{

 

//variables to store the count of A and B

 

int countA=0, countB=0;

 

//create the instances of linked stack to hold characters

 

LinkedStack stackObj1= new LinkedStack();

 

LinkedStack stackObj2= new LinkedStack();

 

//loop invariant

 

int i=0;

 

//push the characters of the string into the stackObj1

 

while(i

 

{

 

//push the character into the stack

 

stackObj1.push(s[i]);

 

}

 

//Create the copy of stack

 

LinkedStack stackObj3= new LinkedStack(stackObj1);

 

//create the reverse string stack using stackObj3

 

//pop the characters from the stack

 

while (!stackObj3.isEmpty())

{

//extract the top element

char top=stackObj3.peek();

//push into the reverse stack

stackObj2.push(top);

//pop the top

 

stackObj2.pop();

}

int count=0;

//The while loop to check the stack contents

while (!stackObj1.isEmpty() && !stackObj1.isEmpty())

{

//extract the top element of stack 1

char top1=stackObj1.peek();

//extract the top element of stack 1

char top2=stackObj2.peek();

//pop the stacks

stackObj2.pop();

stackObj1.pop();

if (top2==’A’)

if(top1!=’B’)

return false;

count++;

if (top2==’B’)

break;

}

//check the count of A is half the string

if(count==(s.length()/2))

return true;

else

return false;

}

int main()

{

return 0;

}