C++ program question:

Write a program that plays with the user the game commonly known as Twenty Questions. However, in this version of the game, the program will not be limited to asking twenty questions. Instead, it may ask any number of questions. Also the program will learn and improve from playing each game.

At the start of each game, the program will ask the user to think of an object for the program to guess. Then, using its database, it will ask the user a number of yes/no questions one at a time. At the end of the question/answer session, it will display its guess for the user object. It will ask the user if its guess is correct. If the guess is correct, it will display a self praising sentence such as I must say I am very smart. If the guess was wrong, for the purpose of improving its performance in the future, it will ask the user for the correct object. It will also ask the user to provide it with a question whose yes answer will be the user correct object and no answer will be the programs wrong guess. It will then update its database with the information received from the user for future use.

Then it will ask the user if he/she will like to play another game. If the user response affirmatively, it will repeat the procedure described above

in the last paragraph. Otherwise, the program will end.

Database

The program will use a flat file database for keeping questions and answers. It will use these questions and answers in interacting with the user. The flat database will be a text file named knowledge.txt. Initially the file will contain the three lines below: (Manually prepare this file using a text editor and save it in a folder accessible from the program).

Is it a non-living object?

Elephant

Stone

In the file, each line will contain either a question or an answer. Each question will be differentiable from the answer in that it will always end with a question mark ?. An answer will never end with a question mark. The above file contains one question component and two answer components.

The question and answer components are stored in the file in such a way that on reading the file, an in memory binary tree can be constructed with each node containing either the question or the answer component. An answer component will always be stored in a leaf node of the tree and a question component will be stored in a non-leaf node of the tree. For example, when the program reads the above file, it will construct the following binary tree:

Is it a non-living object?

| |

| |

Elephant Stone

Algorithm

At the start of the program, the program will read the contents of the file and construct a binary tree containing the question and answer components of the file. It will use this tree to interact with the user.

Once the user has thought of an object, the program will display to the user the contents of the root node as the first question and solicit users yes/no answer.

If the users answer is no, it will traverse the tree using the left link. Otherwise, it will traverse the tree using the right link.

If the new node contains a question, it will present this question to the user and solicits a yes/no answer.

Again if the answer is no, it will traverse the tree using the left link. Otherwise, it will traverse the tree using right link.

It will repeat this process, till it arrives at a leaf node.

It will read the contents of the leaf node and present it to the user as its final guess. (A leaf node will always contain a guess/answer).

If its guess is correct, it will print a self praising message such as I must say I am very smart.

If its guess is wrong, it will first ask the user to provide the correct answer and then it will ask the user to provide a question such that the yes answer to the question is users correct object and no answer is programs wrong guess.

It will update the tree to include the above information received from the user as below:

From the current leaf node that provided the programs guess, it will create two child nodes. It will copy the contents of the current node into its left child node; it will copy users correct answer into its right child node; and it will copy the user supplied question in the current node.

Then it will ask the user if the user would like to play another game.

If the user responds affirmatively, it will repeat the above process.

Otherwise, it will save the updated binary tree in the database file for future use and exit.

Storing/restoring Tree

//For using the method below, make sure that the last

//character in each question is a question mark i.e. ?

//For the methods below to work,

// the last character of every question must be a question mark.

//The methods below for storing a tree to a file is a modified pre-order traversal.

struct NodeType;

typedef NodeType * NodePtr;

struct NodeType

{

string item;

NodePtr llink;

NodePtr rlink;

};

void store()

{

//open a file object for output

ofstream outFile (tree.txt, ios::out);

//assume root is the root of the tree;

rstore(root, outFile);

outFile.close ( );

}

void rstore(NodePtr nodep, ofstream & outFile)

{

//item below is a string being written to the file.

//For a question, the string ends with a question mark (?).

//For an answer,

//it ends with a non question mark, say with a period (.).

//use pre-order traversal to save the tree.

if (nodep!=NULL)

{

OutFile<item <

rstore(nodep->llink,outFile);

rstore(nodep->rlink,outFile);

}

}

//The methods below can be used for restoring tree

//from a file prepared by the above methods. by using pre-order traversal.

void restore( )

{

//open a file object for input

ifstream inFile (tree.txt, ios::in);

//assume root is the root of the tree. It may contain NULL at this time.

rrestore(root, inFile);

inFile.close ( );

}

rrestore(NodePtr &nodep, ofstream & inFile)

{

//use pre-order traversal for restoring the tree.

//After reading a line, and creating a node for it, ask if this is a question?

//If it is a question, make a recursive call to create and fill the next node.

//If it is not a question (i.e. it is an answer), do not make the recursive call

//because there is no node below it.

//read a line from the file.

char buf[120];

inFile.getline(buf,120);

//create a node.

//link this node to the node/root above it.

// The root or left/right link of the node above is passed to this method.

nodep = new NodeType;

//fill the node.

nodep->item = buf;

nodep->llink = NULL;

nodep->rlink = NULL:

//if this is a question, make the recursive call

//because there is still a node below it.

if (nodep->item[nodep->item.length( )-1]=='?')

{

rrestore(nodep->llink, inFile);

rrestore(nodep->rlink, inFile);

}

}

Testing

Make your own data for testing.

Keep testing till tree becomes at least 7 levels deep.

Submit

Submit console input/output dialog for at least one correct and one incorrect answer.

After the tree is at least 7 levels deep, submit a copy of the output file.

SAMPLE RUNS

A number of sample runs are presented below. For each run, the binary tree before the run and the input/output dialog are shown.

Sample Run 1

Database text file contents before the run

Is it a non-living object?

Elephant

Stone

Tree constructed from the above file content.

Is it a non-living object?

| |

| |

Elephant Stone

Input/Output Dialog

Think of an object for me to guess.

Is it a non-living object? (yes/no)

no

My guess: elephant

Is it correct? (yes/no)

yes

I must say I am smart.

Will you like to play another game? (yes/no)

no

Good Bye!

Tree at the end of the run:

Database file contents at the end of the run:

The database file contents at the end of the run will be same as at the start of the next run (See Run 2 below).

The tree at the end of the run will look the same as at the start of the next run. (See Run 2 below).

Sample Run 2

Database text file contents before the run:

Is it a non-living object?

Elephant

Stone

Tree constructed from the above file contents:

Is it a non-living object?

| |

| |

Elephant Stone

Input/Output Dialog

Think of an object for me to guess.

Is it a non-living object? (yes/no)

no

My guess: elephant

Is it correct? (yes/no)

no

What is the correct answer?

apple

Provide a question whose yes answer is your object and no answer is my guess.

Is it a fruit?

Will you like to play another game? (yes/no)

no

Good Bye!

Tree at the end of the run:

Database file contents at the end of the run:

The database file contents at the end of the run will be same as at the start of the next run (See Run 3 below).

The tree at the end of the run will look the same as at the start of the next run. (See Run 3 below).

Sample Run 3

Database text file contents before the run:

Is it a non-living object?

Is it a fruit?

Elephant

Apple

Stone

Tree constructed from the above file contents:

Is it a non-living object?

| |

| |

Is it a fruit? Stone

| |

| |

Elephant Apple

Input/Output Dialog

Think of an object for me to guess.

Is it a non-living object? (yes/no)

no

Is it a fruit?

no

My guess: elephant

Is it correct? (yes/no)

no

What is the correct answer?

asparagus

Provide a question whose yes answer is your object and no answer is my guess.

Is it a vegetable?

Will you like to play another game? (yes/no)

no

Good Bye!

Tree at the end of the run:

Database file contents at the end of the run:

The database file contents at the end of the run will be same as at the start of the next run (See Run 4 below).

The tree at the end of the run will look the same as at the start of the next run. (See Run 4 below).

Sample Run 4

Database text file contents before the run:

Is it a non-living object?

Is it a fruit?

Is it a vegetable?

Elephant

Asparagus

Apple

Stone

Tree constructed from the above file contents:

Is it a non-living object?

| |

| |

Is it a fruit? Stone

| |

| |

Is it a vegetable? Apple

| |

| |

Elephant Asparagus

Input/Output Dialog

Think of an object for me to guess.

Is it a non-living object? (yes/no)

no

Is it a fruit?

no

Is it a vegetable?

yes

My guess: asparagus

Is it correct? (yes/no)

yes

I must say I am smart.

Will you like to play another game? (yes/no)

Yes

Think of an object for me to guess.

Is it a non-living object? (yes/no)

yes

My guess: stone

Is it correct? (yes/no)

yes

I must say I am smart.

Will you like to play another game? (yes/no)

no

Good Bye!

Tree at the end of the run:

Database file contents at the end of the run:

There will be no change in these during the run because all the guesses made by the program during this run are correct.