handout #26
CSE143—Computer Programming II
Programming Assignment #7
due: Friday,
This assignment will give you practice with binary trees. You are to implement a yes/no guessing game. The idea is that you construct a binary tree where each leaf has the name of an object and each branch node has a yes/no question that distinguishes between the objects. It’s like a big game of 20 questions where each question is a yes/no question.
Initially you start out with a tree that has a single leaf with “computer” in it. This is, after all, a computer science class, so we should include computer as a possible answer. Then your program learns new objects by interacting with the user. You ask the user to think of an object and then you ask a series of questions. Starting at the root of your tree, you ask the questions in the branch nodes and go to either the left or right subtree depending upon whether the user answers yes or no. We will adopt the convention that yes is left and no is right. Once you hit a leaf node, you ask the user if that is the object they were thinking of. If the user says yes, you announce that they got it right. Otherwise you ask the user for the name of their object and a yes/no question that would distinguish their object from the one you guessed. You then ask what the answer is for their object (yes or no) and you replace the old leaf with a branch node containing the question from the user and containing the old object and the new object as children.
You also have to be able to write the tree to an output file and read it back in. That way your object tree can grow each time a user runs the program. In writing it out, you should write each node’s data on two lines of output (described below) using a preorder traversal. The first line of each such pair should either have the text “A:” to indicate that it is an “answer” (a leaf node) or a “Q:” to indicate that it a question (a branch node). When you read it back in, you’ll be able to read these special codes to know how to reconstruct the tree.
You will be passed a Scanner for reading. It will already be opened to an external output file. You should read entire lines of input using the nextLine method. You may assume the input file is legal, although it’s not a bad idea to throw an IllegalArgumentException if you come across anything unexpected.
You will be writing to a PrintStream object. System.out is of type PrintStream, so you already know how to use such an object.
This program involves interaction with the user. As always, we will use a Scanner linked to System.in to do this. But with interactive programs, you don’t want to have more than one Scanner linked to System.in. For that reason, in this program your class will construct the console Scanner. It turns out that all that the main method needs is the ability to ask a yes/no question of the user. So the interface for your class will include a method yesTo that main will call when it wants to interact with the user. You can construct a single console Scanner that you store in a data field and use throughout your class.
The main program is called QuestionMain.java. You are to write a class called QuestionNode.java (your tree node class) and QuestionTree.java. You can define whatever data fields you want for the QuestionNode class as long as you are using this class to construct a binary tree. Your QuestionTree class should store the binary tree and should have the following public methods:
|
Method |
Description |
|
QuestionTree() |
Constructs a question tree with one leaf node representing the object “computer”. |
|
void read(Scanner input) |
Replaces the current tree by reading the contents of the given Scanner and constructing the corresponding tree (assumes the input is in standard format). |
|
void write(PrintStream output) |
Writes the current tree to the given output stream in standard format. |
|
void askQuestions() |
Using the current tree, ask the user a series of yes/no questions until you either guess their object correctly or until you fail, in which case you expand the tree to include their object and a new question to distinguish their object. |
|
boolean yesTo(String prompt) |
Asks the given question until the user types “y” or “n”; returns true if “y”, false if “n”. |
The details of the yesTo method are fairly uninteresting, so it is being provided for you (this code assumes a data field called “console” has been initialized). You are to include this method without modification in your QuestionTree class.
// post: asks
the user a question, forcing an answer of "y" or "n";
// returns true if the answer was yes,
returns false otherwise
public
boolean yesTo(String
prompt) {
for (;;) {
System.out.print(prompt + " (y/n)? ");
String response = console.nextLine().trim().toLowerCase();
if (response.equals("y"))
return
true;
else if (response.equals("n"))
return
false;
else
System.out.println("Please
answer y or n.");
}
}
You are defining your own tree node class, so you can include as many data fields as you want for solving this particular problem. In other words, you don’t have to use a generic binary tree; you can use one that is highly specific to this program.
A log of execution is provided at the end of
this write-up showing how the program should interact using your QuestionTree class.
You are to exactly reproduce the format of this log. In addition, you are required to produce
output files using the format described above (two lines for each node’s worth
of data, preorder traversal). For
example, it should be possible for your program to read an input file generated
by another student’s program because we are using a standard format for the
files.
In terms of correctness, your class must provide
all of the functionality described above. In terms of style, we will be grading on your
use of comments, good variable names, consistent indentation and good coding
style to implement these operations.
Remember that you will lose points if you declare variables as data
fields that can instead be declared as local variables. You should also avoid extraneous cases (e.g.,
don’t make something into a special case if it doesn’t have to be).
For a more sophisticated version of the program,
go to http://www.sithsense.com/flash.htm.
You should name your files QuestionNode.java and QuestionTree.java and you should turn it in electronically from the “assignments” link on the class web page. A collection of files needed for the assignment is included on the web page as ass7.zip. You will need to have QuestionMain in the same directory as your files in order to run QuestionMain. The folder also contains a version of question.txt, although you should be able to generate such a file from your own program.
Sample execution (short file)
Welcome
to the cse143 question program.
Do
you want to read in the previous tree? (y/n)? n
Please
think of an object for me to guess.
Would
your object happen to be computer? (y/n)? n
What
is the name of your object? dog
Please
give me a yes/no question that
distinguishes between your object
and
mine--> Is it an animal?
And
what is the answer for your object? (y/n)? y
Do
you want to go again? (y/n)? y
Please
think of an object for me to guess.
Is
it an animal? (y/n)? y
Would
your object happen to be dog? (y/n)? n
What
is the name of your object? frog
Please
give me a yes/no question that
distinguishes between your object
and
mine--> Does it hop?
And
what is the answer for your object? (y/n)? y
Do
you want to go again? (y/n)? y
Please
think of an object for me to guess.
Is
it an animal? (y/n)? y
Does
it hop? (y/n)? n
Would
your object happen to be dog? (y/n)? y
Great,
I got it right!
Do
you want to go again? (y/n)? n
Sample data file question.txt (after above log)
Q:
Is it an
animal?
Q:
Does it
hop?
A:
frog
A:
dog
A:
computer