COMP225 Assignment 1 — Semester 1, 2008

This Assignment

1. QuestionNode.h This is the file which deals with the building blocks for a tree; it defines a tree node, and implements a constructor. It contains one unimplemented function which you are asked to implement for Task 2 in this assignment.
2. Animal.h This contains some utility routines for implementing the game. You will need to use the function getAnswer defined there. This function takes two strings: the first is a question; the second is a string listing the expected answers. It outputs the question and the list of answers and then waits for the user’s response; it then returns the number in the answer list matching the response.
3. Guess.cpp This is the file where the main game functions and program are implemented. Your Task 1 below asks you to complete the implementation of the function Play which is the main routine for playing the game. Whenever it is necessary to add a new node in the game, this will happen in the function Play. To understand how Play should work, read the specification of Task 1 below, look at the function main in Guess.cpp which uses it, and play the game for yourself, by executing GuessGame. Then complete the starred tutorial and practical exercises.
4. animalData is a file containing the data to build a tree. The data stored in this file is a representation of a previously saved game tree in “serialised form”. When you run GuessGame in the same directory as animalData the first thing that happens is that a game tree is constructed from this data, effectively restoring the old game. This is typically how tree data structures can be saved, for example when the database needs to be “backed up”. Your Task 2 asks you to write the part of the code which allows a game tree to be saved in serialised format.

   To understand how the format relates to a game tree, try playing the game –without adding nodes– while you have the file animalData in front of you, and see whether you can “follow” the the program through the file in the file as you respond to the questions the program asks. Answering the starred tutorial exercises will also help you to understand this format.

Task 1 (10 marks)

Your first task is to complete the function Play in Guess.cpp so that your program plays the game in the same way that the given executable GuessGame does.

To help your understanding of the QuestionNode data structure, complete the starred Tutorial and Practical exercises in Weeks 3 and 4. Then interpret the following pseudocode to complete this task. (UPPER-CASE portions are for you to fill in.)

void Play(QuestionNode *&qN) { // Must be reference to allow a new node possibly to be grafted on in this call.
   if (THE CURRENT NODE qN IS A GUESS NODE) { // OTHERWISE IT'S A QUESTION
      GUESS THE ANSWER;
      if (THE PROGRAM GUESSED CORRECTLY) then PRINT "GREAT! LET'S PLAY AGAIN";
      else { // THE PROGRAM GUESSED INCORRECTLY
         ASK THE USER FOR THE ANSWER, VIA STANDARD OUTPUT/INPUT;
         ASK THE USER FOR A QUESTION THAT WILL DISTINGUISH
            THE ANSWER FROM THE GUESS;
         MAKE A NEW NODE CONTAINING THAT QUESTION, FOR WHICH A "YES"
            LEADS TO THE ACTUAL ANSWER, AND "NO" TO THE GUESS;
         INSERT THAT NEW NODE AT THE CORRECT POINT IN THE TREE;
            // (HINT: DO THE STARRED TUTORIAL EXERCISES FOR HELP WITH THIS)
       } 
   }   
   else { // THE CURRENT NODE IS A QUESTION
     ASK THE QUESTION; GET THE ANSWER; CONTINUE TO PLAY IN THE CORRECT SUB-TREE;
   }
}

Remember to compile your code, have all the files QuestionNode.h, Animal.h and Guess.cpp in the same folder and use g++ Guess.cpp.

Task 2 (5 marks)

We use tags T: to denote a text node, and N: to denote NULL. The depth within the game tree is denoted by the indentation so that a node appears at depth d just when its tag is preceded on the line by d-1 spaces. Thus at depth 1 (no spaces) there are three nodes (one for animal, one for vegetable and one for mineral).

All other nodes either have two children, or no children, or are NULL, and they are all at depth greater than 1. After a T: there is text which is either a question (for a question node) or a guess (for a guess node). Its left branch (for "yes") appears on the next line(s) below, indented by one more space, followed by its representation of the subtree.

To check that your code is producing the correct result, copy the game whose log of interactive responses are saved in the file gameRun. Start from scratch (i.e. without a file animalData), and when you've played that game save it to file. Your program's output should be exactly the same as in the file animalData1.

The files