Figure 15.2

#include <iostream> // cin, cout, cerr, ...
#include <stack> // stack<T>
using namespace std;

string convertDecimal(int number, int base);

int main()
{
   cout << "To convert a decimal integer to a different base,\n"
	<< " enter a positive integer: ";
   int number;
   cin >> number;
   cout << " then enter the base to which it is to be converted: ";
   int base;
   cin >> base;
   cout << '\n' << convertDecimal(number, base)
	<< " is the base-" << base
	<< " representation of " << number << endl;
}

char baseDigit(int value);
/* convertDecimal() converts a decimal value to its base representation
* Receive: number, an int; and
* base, an int
* Precondition: number is positive &&
* 2 <= base && base <= 35
* Return: a string giving the base-base representation of number
*/

string convertDecimal(int number, int base)
{
   stack<int> intStack;
   int remainder;
   do
   {
	remainder = number % base;
	intStack.push(remainder);
	number /= base;
   }
   while (number != 0);
   string resultString = "";
   char digitChar;
   while ( !intStack.empty() )
   {
	remainder = intStack.top();
	intStack.pop();
	digitChar = baseDigit(remainder);
	resultString += digitChar;
   }
   return resultString;
}

/* Table look-up routine for mapping 0-35 to 0-z
* Receive: value, an int.
* Precondition: 0 <= value && value <= 35
* Return: the 0-z representation of value
*/

char baseDigit (int value)
{
   const int VALUES_SUPPORTED = 36;
   const char resultArray[VALUES_SUPPORTED] =
   { '0', '1', '2', '3', '4', '5', '6', '7', '8', '9',
   'a', 'b', 'c', 'd', 'e', 'f', 'g', 'h', 'i', 'j',
   'k', 'l', 'm', 'n', 'o', 'p', 'q', 'r', 's', 't',
   'u', 'v', 'w', 'x', 'y', 'z'};
   char result = '*';
   if (0 <= value && value < VALUES_SUPPORTED)
	result = resultArray[value];
   else
 	cerr << "\n** baseDigit(value): "
	     << value << " outside of range 0.."
	     << VALUES_SUPPORTED-1 << endl;
   return result;
}
-------------------------
Sample runs:

To convert a decimal integer to a different base,
enter a positive integer: 32

then enter the base to which it is to be converted: 2

100000 is the base-2 representation of 32

To convert a decimal integer to a different base,
enter a positive integer: 32

then enter the base to which it is to be converted: 8

40 is the base-8 representation of 32

To convert a decimal integer to a different base,
enter a positive integer: 32

then enter the base to which it is to be converted: 16

20 is the base-16 representation of 32

To convert a decimal integer to a different base,
enter a positive integer: 255

then enter the base to which it is to be converted: 16

ff is the base-16 representation of 255

Figure 15.3

#include <iostream> // cin, cout, cerr, ...
#include <queue> // queue<T>, priority_queue<T>
using namespace std;

int main()
{
   string name = "JoeSmith";
   priority_queue<char> pQ;
   queue<char> q;
   for (int i = 0; i < 5; i++)
   {
	q.push(name[i]); // insert into normal queue
	pQ.push(name[i]); // insert into priority queue
   }
   while ( !q.empty() ) // output normal queue values
   {
	cout << q.front();
	q.pop();
   }
   cout << endl;
   while ( !pQ.empty() ) // output priority queue values
   {
	cout << pQ.top();
	pQ.pop();
   }
   cout << endl;
}

-----------------
Sample run:

JoeSmith

tomiheSJ

Figure 15.5

template <typename DataType>
bool BST<DataType>::search(const DataType& item) const
{
   Node* currentNode = root; 				// search pointer
   bool found = false; 					// indicates if item already in BST
   while (currentNode != 0 && !found)
   {
	if (item < currentNode->myValue) 		// descend left
	    currentNode = currentNode->myLeft;
	else if (item > currentNode->myValue) 		// descend right
	    currentNode = currentNode->myRight;
	else 						// item found
	    found = true;
   }	
   return found;
}

Figure 15.6

template <typename DataType>
void BST<DataType>::print(ostream& out) const
{
   if (myRoot != 0) 				// if I am not empty
	myRoot->print(out); 			// invoke recursive Node print()
}

template <typename DataType>
void BST<DataType>::Node::print(ostream& out) const
{
   if (myLeft != 0) 				// if my left subtree is not empty
	myLeft->print(out); 			// display its values first
   out << myData << ' '; 			// display my value
   if (myRight != 0) 				// if my right subtree is not empty
	myRight->print(out); 			// display its values last
}

Figure 15.7

template <typename DataType>
void BST<DataType>::Insert(const DataType & item)
{
   Node* currentNode = root,  				// search pointer
   parentNode = 0; 					// pointer to parent of current node
   bool found = false; 					// indicates if item already in BST
   while (currentNode != 0 && !found)
   {
	parentNode = currentNode;
	if (item < currentNode->myValue) 		// descend left
	   currentNode = currentNode->myLeft;
	else if (item > currentNode->myValue) 		// descend right
	   currentNode = currentNode->myRight;
	else 						// item found
	   found = true;
   }
   if (found)
	cerr << "Item already in the tree\n";
   else
   {
	currentNode = new Node(item); 			// construct node ctg item
	if (parentNode == 0) 				// empty tree
	   root = currentNode;
	else if (item < parentNode->data) 		// insert to parent’s left
	   parentNode->myLeft = currentNode;
	else 						// insert to parent’s right
	   parentNode->myRight = currentNode;
   }
}

Figure 15.8

#include <iostream>
using namespace std;
#include "DecisionTree.h"

bool playMore();

int main()
{
   cout << "\nWelcome to the game of Animal!\n";
   DecisionTree dTree("animal.data"); // load knowledge base
   do
   {
	cout << "\nThink of an animal, and I will try to guess it...\n\n";
	int winner = dTree.descend(); // 0 == the person,
	if (winner)
	   cout << "\nHa! Even a computer program can beat you...\n";
	else
	   cout << "\nYou were just lucky...\n";
   }   
   while ( playMore() );
} // knowledge base is auto-saved to file by DecisionTree destructor

bool playMore()
{
   char answer;
   cout << "\nDo you want to play again (y or n)? ";
   cin >> answer;
   return ((answer == 'y') || (answer == 'Y'));
}