CS361 Assignment 3 Introduction to Trees

BACKGROUND: Growing up, many people play the game 20 Questions. In this game, a player thinks of something and the second player asks a series of yes or no questions to determine what the first player is thinking. The game is based upon a binary tree structure with each yes-or-no question directing the second player closer and closer to the answer.

In this assignment, you will take an almost working version of the guessing game. Your task is to implement the input and output functions for the question tree. Both the input and output algorithms will resemble tree traversal algorithms. You will be player 1 (providing the input file and answering the yes-or-no questions) with the computer as player 2 (guessing based on the questions).

REQUIREMENTS:

1. Modify node.cpp to implement the input and output functions for the questions tree.

1. HINT: It is probably easier to get the output working correctly first, because the program will build a tree from scratch if presented with empty input. So, by playing a game with multiple rounds of questions, you can build trees internally to test your output routine.

2. HINT: Make sure your program is able to read its own input. If not, you know that you have a problem! If fact, if you have done your output function first, you can use it as a generator for test data for your input function.

2. The input file consists of several lines. Each line describes a single question or answer.

3. A line begins with a character: Q or A, indicating whether the line describes a question or answer, respectively.

4. The Q or A is followed by 1 or more whitespace characters.

5. The first non-whitespace character after the Q or A indicates the start of the question or answer text, which continues to the end of the line.

6. Each line will contain only 1 question or answer

7. Each Q is immediately followed by lines describing its yes descendants, then lines describing its no descendants.

8. Each non-empty data file will contain at least 1 question and answer.

EXAMPLE:

Q Does it live in the water?

Q Does it have webbed feet?

A Duck

A Fish

A Cat

SUBMISSION Submit the following files: You will submit the node.cpp file.

(I can post/email the code already provided if needed)

game.h

#ifndef __GAME_H__ #define __GAME_H__

#pragma once

#include #include #include #include

#include "node.h"

class Game { private: std::shared_ptr m_Root; private: void LearnNewQuestion(std::shared_ptr current); bool GetAnswer(); public: void Load(std::istream& is); void Play(); void Write(std::ostream& os); };

#endif // __GAME_H__

game.cpp

#include "game.h"

void Game::LearnNewQuestion(std::shared_ptr current) { std::string currentAnswer = current->detailText; std::cout << "What is your answer?: "; std::string newAnswer; std::getline(std::cin, newAnswer); std::string newQuestion; std::cout << "What is a yes/no question that I can use to tell a " << currentAnswer << " from a " << newAnswer << "?" << std::endl; std::getline(std::cin, newQuestion); std::shared_ptr node1 = std::make_shared(newAnswer); std::shared_ptr node2 = std::make_shared(currentAnswer); std::cout << "For a " << newAnswer << ", is the answer yes or no?: "; if (GetAnswer() != false) { current->ifYes = node1; current->ifNo = node2; } else { current->ifYes = node2; current->ifNo = node1; } current->detailText = newQuestion; }

bool Game::GetAnswer() { std::string answer; while (true) { std::getline(std::cin, answer); if (answer[0] == 'y' || answer[0] == 'Y') { return true; } else if (answer[0] == 'n' || answer[0] == 'N') { return false; } std::cout << "Please answer yes or no." << std::endl; } }

void Game::Load(std::istream& is) { if (is) { is >> m_Root; } }

void Game::Play() { if (!m_Root) { // file was empty or nonexistent, so this is a new game m_Root = std::make_shared("Cat"); } std::shared_ptr current = m_Root; while (current) { if (current->ifYes) { // this node has children, so it is a question std::cout << current->detailText << std::endl; if (GetAnswer()) { current = current->ifYes; } else { current = current->ifNo; } } else { // this node has no children, so it is an answer std::cout << "I know. Is it a " << current->detailText << "?" << std::endl; if (GetAnswer()) { std::cout << "I won!" << std::endl; } else { LearnNewQuestion(current); } std::cout << "Try again?" << std::endl; if (GetAnswer()) { current = m_Root; } else { current = std::shared_ptr(); } } } }

void Game::Write(std::ostream& os) { os << m_Root << std::flush; }

main.cpp

#include #include #include

#include "game.h"

int main(int argc, char** argv) { if (argc != 2) { std::cerr << "Usage: " << argv[0] << " [filename] " << "\twhere the filename denotes a file used both " << "\tto read an existing database of questions (may " << "\tbe empty or even nonexistent, in which case a " << "\tdefault initialzation is used instead) and to " << "\treceive the modified database of questions " << "\tafterwards." << std::endl; return -1; }

Game game; std::ifstream fin(argv[1]); game.Load(fin); game.Play(); std::ofstream fout(argv[1]); game.Write(fout); return 0; }

node.h

#ifndef __NODE_H__ #define __NODE_H__

#pragma once

#include #include #include

// // binary tree node for guessing game // // Each node contains a question and and pointers // to the node representing yes and no responses, or // an answer and two null pointers //

struct Node { std::string detailText; std::shared_ptr ifYes; std::shared_ptr ifNo;

Node(std::string q, std::shared_ptr yes = std::shared_ptr(), std::shared_ptr no = std::shared_ptr()) : detailText(q), ifYes(yes), ifNo(no) {}

// read a tree from in storing the tree root in t static void read(std::istream& in, std::shared_ptr& t);

// write the tree whose root is given. // Note: the form written out by this function should be something // that read(...) will accept, recreating the original tree. static void write(std::ostream& out, const std::shared_ptr root); private: friend std::istream& operator>>(std::istream&, std::shared_ptr&); friend std::ostream& operator<<(std::ostream&, const std::shared_ptr); };

inline std::ostream& operator<<(std::ostream& out, const std::shared_ptr n) { Node::write(out, n); return out; }

inline std::istream& operator>>(std::istream& in, std::shared_ptr& n) { Node::read(in, n); return in; }

#endif // __NODE_H__

node.cpp

#include "node.h"

/****************************************************************\ Input/Output format for this program.

A tree of questions and answers is represented by multiple lines of text. There will always be at least one line of text.

Each line represents one node in the tree. Each begins with either a 'Q' or an 'A', indicating whether the node is a Question node or an Answer node, followed by one or more blank spaces, followed by the text of the question or answer. The text of a question or answer begins with the first non-blank character after the Q or A and continues until the end of the line.

Each 'Q' line is followed immediately by two blocks of 'Q' and 'A' lines. The first block describes the collection of questions and answers relevant following a "yes" answer to the first question. The second block describes the collection of questions and answers relevant to a "no" answer to the opening question.

For example,

Q Does it live in the water? Q Does it have webbed feet? A Duck A Fish A Cat

Describes a tree in which the first question to be asked is "Does it live in the water?". If the person playing the game answers "yes", then the block of lines

Q Does it have webbed feet? A Duck A Fish

is relevant (i.e., the program will next ask about webbed feet). If the person answers "no". then the block of lines

A Cat

is relevant (i.e., the program will next ask "Is it a cat?".

The "indentation" shown in the sample above is purely for human readability. It is not required in your output, though your input routine should tolerate it if it is present. \****************************************************************/

// write the tree whose root is given. // Note: the form written out by this function should be something // that read(...) will accept, recreating the original tree. void Node::write(std::ostream& out, const std::shared_ptr root) {

}

// read a tree from in storing the tree root in t void Node::read(std::istream& in, std::shared_ptr& t) {

}