Read and Write to input file using trees in C++?

  • (3 Pages)
  • +
  • 1
  • 2
  • 3

41 Replies - 3036 Views - Last Post: 09 July 2013 - 07:08 PM Rate Topic: -----

#1 lamentofking  Icon User is offline

  • D.I.C Head

Reputation: 0
  • View blog
  • Posts: 167
  • Joined: 03-July 13

Read and Write to input file using trees in C++?

Posted 03 July 2013 - 12:30 PM

So the task I am trying to complete is to implement read and write functions to a data file. I am using trees to complete this. The program itself is the animal guessing game (which I'm sure many people here have heard about).

Here are the files I am working with:

//node.h header specification file


#ifndef NODE_H
#define NODE_H

#include <iostream>
#include <string>


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


struct node {
  std::string question;
  node* ifYes;
  node* ifNo;

  node (std::string q, node* yes = NULL, node* no = NULL)
    : question(q), ifYes(yes), ifNo(no)
    {}

private:

  // read a tree from in storing the tree root in t
  static void read (std::istream& in, node*& 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 node* root);
  
    
  friend std::istream& operator>> (std::istream&, node*&);
  friend std::ostream& operator<< (std::ostream&, const node*);

};

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

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

#endif



// animal.cpp client code 

#include <cassert>
#include <fstream>
#include <string>

#include "node.h"


using namespace std;

bool getYesNoAnswer()
{
  // get yes no answer
  while (true)
    {
      string ans;
      getline(cin, ans);
      if ((ans[0] == 'y') || (ans[0] == 'Y'))
	return true;
      else if ((ans[0] == 'n') || (ans[0] == 'N'))
	return false;
      cout << "please answer yes or no.\n";
    }
}

void learnNewAnimal(node* current)
{
  // learn about a new animal type

  string currentAnimal = current->question;
  cout << "what is your animal?\n";
  string newAnimal;
  getline(cin, newAnimal);
  cout << "What is a yes/no question that I can use to tell a "
       << current->question << " from a " << newAnimal << " ?\n";
  string newQuestion;

  node * node1 = new node(newAnimal, 0, 0);
  node * node2 = new node(currentAnimal, 0, 0);
  // make sure allocation worked
  assert ((node1 != 0) && (node2 != 0));

  getline(cin, newQuestion);
  cout << "For a " << newAnimal << " is the answer yes or no?\n";
  if (getYesNoAnswer() != 0)
    {
      current->ifYes = node1;
      current->ifNo = node2;
    }
  else
    {
      current->ifYes = node2;
      current->ifNo = node1;
    }
  current->question = newQuestion;
}



void animalGame(const char* fileName)
{
  // initialize the database
  node* root = 0;
  {
    ifstream in (fileName);
    if (in.good())
      in >> root;
  }


  if (root == 0) // file was empty or nonexistent
    root = new node ("cat", 0, 0);


  // play the game
  node * current = root;
  // now start the game
  cout << "Let's play \"Guess the Animal\".\n";
  while (current != 0)
    {
      // if current node has children it is a question
      if (current->ifYes != 0)
	{
	  cout << current->question << '\n';
	  if (getYesNoAnswer())
	    current = current->ifYes;
	  else
	    current = current->ifNo;
	}
      // if no children it is an answer
      else
	{
	  cout << "I know.  Is it a " << current->question << " ?\n";
	  if (getYesNoAnswer())
	    cout << "I won.\n";
	  else
	    {
	      // we didn't get it.
	      // time to learn something
	      learnNewAnimal(current);
	    }
	  cout << "Try again?\n";
	  if (getYesNoAnswer())
	    current = root;
	  else
	    current = 0;
	}
    }

  // Save the modified question set
  ofstream out (fileName);
  out << root << flush;
}

int main (int nargs, char** argv)
{
  if (nargs != 2)
    {
      cerr << "Usage: animal filename\n"
	   << "  where the filename denotes a file used both\n"
	   << "  to read an existing database of questions (may\n"
	   << "  be empty or even nonexistent, in which case a\n"
	   << "  default initialzation is used instead) and to\n"
	   << "  receive the modified database of questions\n"
	   << "afterwards." << endl;
      return -1;
    }

  animalGame(argv[1]);
  return 0;

}



 //node.cpp specification file

#include "node.h"
#include <cassert>
#include <iomanip>

/*
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.

 */



using namespace std;

// 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 node* root)
{
  // definition goes here
}


// read a tree from in storing the tree root in t
void node::read (istream& in, node*& t)
{
  // definition goes here
 /* node* parent;
  parent = 0;
  string q;
  t->question = q;
  node* yes = NULL;
  node* no = NULL;


  node *CurrentRecord;
  CurrentRecord = t;
  while (in)
  if (!in)
  {
      cout <<"No datafile exists. Program exiting."<<endl;
  }

  string line;
  in.ignore ( );
  getline (in, line, '?');
  while (in !=0)
  {
    parent = CurrentRecord;
  }
 node::read (in, t);*/
//  return in;
  t = NULL;
}




I am working with node.cpp . I tried to tackle the read function (can't write to anything without reading first I assume) . I commented out what I wrote for compilation purposes. But if anyone tries to run it, you'll see that the questions won't save but just overwrite any new questions you put in.

So how do I go about defining the read and write functions and which one is recommended to start with first?

Is This A Good Question/Topic? 0
  • +

Replies To: Read and Write to input file using trees in C++?

#2 jimblumberg  Icon User is online

  • member icon


Reputation: 4133
  • View blog
  • Posts: 12,865
  • Joined: 25-December 09

Re: Read and Write to input file using trees in C++?

Posted 03 July 2013 - 01:36 PM

My suggestion would be to use paper and pencil and determine what your data actually consists of. Once you know exactly what each "record" contains you can figure out how to read and write the information. If I don't have a predefined file I normally start by writing a file then creating the functions to read the file that I wrote.

Jim
Was This Post Helpful? 1
  • +
  • -

#3 lamentofking  Icon User is offline

  • D.I.C Head

Reputation: 0
  • View blog
  • Posts: 167
  • Joined: 03-July 13

Re: Read and Write to input file using trees in C++?

Posted 03 July 2013 - 01:56 PM

View Postjimblumberg, on 03 July 2013 - 01:36 PM, said:

My suggestion would be to use paper and pencil and determine what your data actually consists of. Once you know exactly what each "record" contains you can figure out how to read and write the information. If I don't have a predefined file I normally start by writing a file then creating the functions to read the file that I wrote.

Jim

This is the input:
Q Does it live in the water?
Q Does it have webbed feet?
A Duck
A Fish
A Cat


So I would say I need to use a string (one of the struct data members is a string so it's probably the way to go). I want to do the pointer loop

while (current!=NULL)
{
  "cout<< current question<<endl;
   "current = new question"
}


I tried something similar to that but it won't compile. Invalid use of "question" is what the compiler says.
Was This Post Helpful? 0
  • +
  • -

#4 lamentofking  Icon User is offline

  • D.I.C Head

Reputation: 0
  • View blog
  • Posts: 167
  • Joined: 03-July 13

Re: Read and Write to input file using trees in C++?

Posted 05 July 2013 - 06:34 AM

bump
Was This Post Helpful? 0
  • +
  • -

#5 Skydiver  Icon User is offline

  • Code herder
  • member icon

Reputation: 3616
  • View blog
  • Posts: 11,263
  • Joined: 05-May 12

Re: Read and Write to input file using trees in C++?

Posted 05 July 2013 - 07:06 AM

I am very confused... If you wrote that code in your opening post, how could you have lost all the skill and be unable to even write a loop to print out values? For you to have advanced to the point of having multiple files, use structures and classes, and use operator overloading, you must have gotten past using variables, I/O, and basic flow control.

If you are that significantly behind in your class, I highly recommend taking time to talk to your teacher and let him know about the situation so that the two of you can come up with a plan to help you get back up to speed.
Was This Post Helpful? 2
  • +
  • -

#6 lamentofking  Icon User is offline

  • D.I.C Head

Reputation: 0
  • View blog
  • Posts: 167
  • Joined: 03-July 13

Re: Read and Write to input file using trees in C++?

Posted 05 July 2013 - 11:33 AM

View PostSkydiver, on 05 July 2013 - 07:06 AM, said:

I am very confused... If you wrote that code in your opening post, how could you have lost all the skill and be unable to even write a loop to print out values? For you to have advanced to the point of having multiple files, use structures and classes, and use operator overloading, you must have gotten past using variables, I/O, and basic flow control.

If you are that significantly behind in your class, I highly recommend taking time to talk to your teacher and let him know about the situation so that the two of you can come up with a plan to help you get back up to speed.
Sorry. I meant I commented out what I wrote in node.cpp . All the other code was given.

And apparently it's uncommon to read and write to input files using trees because there aren't any examples on the internet that I found. It can't be that simple if it isn't on the internet yet.
Was This Post Helpful? 0
  • +
  • -

#7 Skydiver  Icon User is offline

  • Code herder
  • member icon

Reputation: 3616
  • View blog
  • Posts: 11,263
  • Joined: 05-May 12

Re: Read and Write to input file using trees in C++?

Posted 05 July 2013 - 11:48 AM

It's actually pretty common... Most students tackling Huffman encoding and decoding need to write out and read in their Huffman trees for the data compression and decompression to work.

I think what is frustrating your search is that you were hoping to find somebody else's code that exactly matches your assignment.

Anyway, if you've covered walking a tree in class, then saving out a tree to a file is exactly the same process. Reading a tree back in can be achieved by merely reading in the data that was written out and rebuilding the tree again.

This post has been edited by Skydiver: 05 July 2013 - 11:51 AM

Was This Post Helpful? 2
  • +
  • -

#8 lamentofking  Icon User is offline

  • D.I.C Head

Reputation: 0
  • View blog
  • Posts: 167
  • Joined: 03-July 13

Re: Read and Write to input file using trees in C++?

Posted 05 July 2013 - 04:43 PM

View PostSkydiver, on 05 July 2013 - 11:48 AM, said:

It's actually pretty common... Most students tackling Huffman encoding and decoding need to write out and read in their Huffman trees for the data compression and decompression to work.

I think what is frustrating your search is that you were hoping to find somebody else's code that exactly matches your assignment.

Anyway, if you've covered walking a tree in class, then saving out a tree to a file is exactly the same process. Reading a tree back in can be achieved by merely reading in the data that was written out and rebuilding the tree again.
Finding code that matches the assignment would be ideal but i can apply an example to my assignment. I'm going to look over my notes again but I don't remember tree walking . In the mean time if someone could provide an example of tree walking that would be helpful. I believe seeing visual examples helps aid in programming along with practicing examples.
Was This Post Helpful? 0
  • +
  • -

#9 #define  Icon User is offline

  • Duke of Err
  • member icon

Reputation: 1368
  • View blog
  • Posts: 4,735
  • Joined: 19-February 09

Re: Read and Write to input file using trees in C++?

Posted 05 July 2013 - 05:33 PM

Instead of using the node as a tree and a node it might be simpler to have a tree class as well as a node class.

The usual method of accessing trees is with recursive functions.

Binary search tree
Was This Post Helpful? 0
  • +
  • -

#10 lamentofking  Icon User is offline

  • D.I.C Head

Reputation: 0
  • View blog
  • Posts: 167
  • Joined: 03-July 13

Re: Read and Write to input file using trees in C++?

Posted 05 July 2013 - 05:51 PM

View Post#define, on 05 July 2013 - 05:33 PM, said:

Instead of using the node as a tree and a node it might be simpler to have a tree class as well as a node class.

The usual method of accessing trees is with recursive functions.

Binary search tree
That wiki could provide some insight. Thanks. Yeah I can only add code in the node.cpp for the read and write definitions. Is reading the same thing as inserting in c++ ?
Was This Post Helpful? 0
  • +
  • -

#11 #define  Icon User is offline

  • Duke of Err
  • member icon

Reputation: 1368
  • View blog
  • Posts: 4,735
  • Joined: 19-February 09

Re: Read and Write to input file using trees in C++?

Posted 05 July 2013 - 06:38 PM

It is very similar I would say.
Was This Post Helpful? 0
  • +
  • -

#12 David W  Icon User is offline

  • DIC supporter
  • member icon

Reputation: 281
  • View blog
  • Posts: 1,788
  • Joined: 20-September 08

Re: Read and Write to input file using trees in C++?

Posted 06 July 2013 - 07:02 PM

Besides all the hints and helps given above, you may like to see this thread that seems to be about the same (or almost the same) student problem ...

binary tree info ...


similar problem
Was This Post Helpful? 1
  • +
  • -

#13 R2B Boondocks  Icon User is offline

  • D.I.C Head
  • member icon

Reputation: 12
  • View blog
  • Posts: 199
  • Joined: 19-September 12

Re: Read and Write to input file using trees in C++?

Posted 08 July 2013 - 08:35 AM

I have a hunch we may be classmates. May I suggest looking at the lesson "Traversing Trees with Iterators" and the lesson "Trees" will extra focus on section 2.2.1 where it talks about pre-order traversals. Keep in mind that the section gives only a template of a pre-order and will have to be manipulated to make it useful. Looking at David's link above I think you will find it more helpful than the lessons (in my opinion).

Also please view node.h...particularly these lines
inline
std::ostream& operator<< (std::ostream& out, const node* n)
{
  node::write (out, n);
  return out;
}

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



Notice how similar the parameters are to our void functions in node.cpp? Does that give you a hint for a least part of them? (think of node n as something that can be replaced by another parameter).

I hope I didn't confuse you in any way.
Was This Post Helpful? 1
  • +
  • -

#14 lamentofking  Icon User is offline

  • D.I.C Head

Reputation: 0
  • View blog
  • Posts: 167
  • Joined: 03-July 13

Re: Read and Write to input file using trees in C++?

Posted 08 July 2013 - 04:30 PM

Alright. I'm trying to figure out if my read function is correct. Here is the psuedo-code form.

while (inside the file)
{
if (t is not NULL)
{
read (in, t->ifYes);
read (in, t->ifNo);
}
}

t = NULL; //to finish the reading of the file


Is that correct? I can't tell how to check if the function works properly.

And thanks for helping Boondocks and David. It is getting me on my feet but I think my adaptations of the code are off somewhere.
Was This Post Helpful? 0
  • +
  • -

#15 R2B Boondocks  Icon User is offline

  • D.I.C Head
  • member icon

Reputation: 12
  • View blog
  • Posts: 199
  • Joined: 19-September 12

Re: Read and Write to input file using trees in C++?

Posted 08 July 2013 - 06:20 PM

animal.cpp
node* root = 0; //sets the node to 0 or NULL

node * current = root; //sets the root to current node



Set t equal to something but comment out t = NULL.

I will tell you that the below is correct (does NOT finish read function still more to do)
read (in, t->ifYes);
read (in, t->ifNo);


Was This Post Helpful? 0
  • +
  • -

  • (3 Pages)
  • +
  • 1
  • 2
  • 3