The Programming Example, Converting a Number from Binary to Decimal, in Chapter 15, uses recursion to convert a binary number into an equivalent decimal number.

Write a program that uses a stack to convert a binary number (input by the user) into an equivalent decimal number.

********************

linkedStack.h

*******************

//Header File: linkedStack.h

#ifndef H_StackType

#define H_StackType

#include

#include

#include "stackADT.h"

using namespace std;

//Definition of the node

template

struct nodeType

{

Type info;

nodeType *link;

};

template

class linkedStackType: public stackADT

{

public:

const linkedStackType& operator=

(const linkedStackType&);

//Overload the assignment operator.

bool isEmptyStack() const;

//Function to determine whether the stack is empty.

//Postcondition: Returns true if the stack is empty;

// otherwise returns false.

bool isFullStack() const;

//Function to determine whether the stack is full.

//Postcondition: Returns false.

void initializeStack();

//Function to initialize the stack to an empty state.

//Postcondition: The stack elements are removed;

// stackTop = nullptr;

void push(const Type& newItem);

//Function to add newItem to the stack.

//Precondition: The stack exists and is not full.

//Postcondition: The stack is changed and newItem

// is added to the top of the stack.

Type top() const;

//Function to return the top element of the stack.

//Precondition: The stack exists and is not empty.

//Postcondition: If the stack is empty, the program

// terminates; otherwise, the top

// element of the stack is returned.

void pop();

//Function to remove the top element of the stack.

//Precondition: The stack exists and is not empty.

//Postcondition: The stack is changed and the top

// element is removed from the stack.

linkedStackType();

//Default constructor

//Postcondition: stackTop = nullptr;

linkedStackType(const linkedStackType& otherStack);

//Copy constructor

~linkedStackType();

//Destructor

//Postcondition: All the elements of the stack are

// removed from the stack.

private:

nodeType *stackTop; //pointer to the stack

void copyStack(const linkedStackType& otherStack);

//Function to make a copy of otherStack.

//Postcondition: A copy of otherStack is created and

// assigned to this stack.

};

//Default constructor

template

linkedStackType::linkedStackType()

{

stackTop = nullptr;

}

template

bool linkedStackType::isEmptyStack() const

{

return(stackTop == nullptr);

} //end isEmptyStack

template

bool linkedStackType:: isFullStack() const

{

return false;

} //end isFullStack

template

void linkedStackType::initializeStack()

{

nodeType *temp; //pointer to delete the node

while (stackTop != nullptr) //while there are elements in

//the stack

{

temp = stackTop; //set temp to point to the

//current node

stackTop = stackTop->link; //advance stackTop to the

//next node

delete temp; //deallocate memory occupied by temp

}

} //end initializeStack

template

void linkedStackType::push(const Type& newElement)

{

nodeType *newNode; //pointer to create the new node

newNode = new nodeType; //create the node

newNode->info = newElement; //store newElement in the node

newNode->link = stackTop; //insert newNode before stackTop

stackTop = newNode; //set stackTop to point to the

//top node

} //end push

template

Type linkedStackType::top() const

{

assert(stackTop != nullptr); //if stack is empty,

//terminate the program

return stackTop->info; //return the top element

}//end top

template

void linkedStackType::pop()

{

nodeType *temp; //pointer to deallocate memory

if (stackTop != nullptr)

{

temp = stackTop; //set temp to point to the top node

stackTop = stackTop->link; //advance stackTop to the

//next node

delete temp; //delete the top node

}

else

cout << "Cannot remove from an empty stack." << endl;

}//end pop

template

void linkedStackType::copyStack

(const linkedStackType& otherStack)

{

nodeType *newNode, *current, *last;

if (stackTop != nullptr) //if stack is nonempty, make it empty

initializeStack();

if (otherStack.stackTop == nullptr)

stackTop = nullptr;

else

{

current = otherStack.stackTop; //set current to point

//to the stack to be copied

//copy the stackTop element of the stack

stackTop = new nodeType; //create the node

stackTop->info = current->info; //copy the info

stackTop->link = nullptr; //set the link field of the

//node to nullptr

last = stackTop; //set last to point to the node

current = current->link; //set current to point to

//the next node

//copy the remaining stack

while (current != nullptr)

{

newNode = new nodeType;

newNode->info = current->info;

newNode->link = nullptr;

last->link = newNode;

last = newNode;

current = current->link;

}//end while

}//end else

} //end copyStack

//copy constructor

template

linkedStackType::linkedStackType(

const linkedStackType& otherStack)

{

stackTop = nullptr;

copyStack(otherStack);

}//end copy constructor

//destructor

template

linkedStackType::~linkedStackType()

{

initializeStack();

}//end destructor

//overloading the assignment operator

template

const linkedStackType& linkedStackType::operator=

(const linkedStackType& otherStack)

{

if (this != &otherStack) //avoid self-copy

copyStack(otherStack);

return *this;

}//end operator=

#endif

********************

stackADT.h

********************

//Header file: stackADT.h

#ifndef H_StackADT

#define H_StackADT

template

class stackADT

{

public:

virtual void initializeStack() = 0;

//Method to initialize the stack to an empty state.

//Postcondition: Stack is empty

virtual bool isEmptyStack() const = 0;

//Function to determine whether the stack is empty.

//Postcondition: Returns true if the stack is empty,

// otherwise returns false.

virtual bool isFullStack() const = 0;

//Function to determine whether the stack is full.

//Postcondition: Returns true if the stack is full,

// otherwise returns false.

virtual void push(const Type& newItem) = 0;

//Function to add newItem to the stack.

//Precondition: The stack exists and is not full.

//Postcondition: The stack is changed and newItem

// is added to the top of the stack.

virtual Type top() const = 0;

//Function to return the top element of the stack.

//Precondition: The stack exists and is not empty.

//Postcondition: If the stack is empty, the program

// terminates; otherwise, the top element

// of the stack is returned.

virtual void pop() = 0;

//Function to remove the top element of the stack.

//Precondition: The stack exists and is not empty.

//Postcondition: The stack is changed and the top

// element is removed from the stack.

};

#endif