Help with read/write for queue

  • (2 Pages)
  • +
  • 1
  • 2

15 Replies - 1068 Views - Last Post: 06 July 2013 - 04:54 PM Rate Topic: -----

#1 R2B Boondocks  Icon User is offline

  • D.I.C Head
  • member icon

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

Help with read/write for queue

Posted 06 July 2013 - 07:10 AM

Hey guys,

I need to implement a read / write function for my node.cpp file. I had a friend suggest using (partially) a queue to write / restore tree structure from the input file that will be used to test the program (do not have access to it). Below you will see my three files. The one that needs to be manipulated is node.cpp.

Animal.cpp
#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.h
#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



Node.cpp
#include "node.h"
#include <cassert>

/*
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 )
{
    // insert your code here
    const node* cur = root;

    out << cur->question << std::endl;
    out << cur->ifYes->question << std::endl;

// Originally all that was there was //insert your code here
}


// read a tree from in storing the tree root in t
void node::read( istream& in, node*& t )
{
    // replace the line below by your own code
    //t = NULL;
    std::string line; 

    if( getline( in, line ) )
        t = new node ( line, 0, 0 );
    if( getline( in, line ) )
        t->ifYes = new node ( line, 0, 0 );

//Originally all that was there was t=Null (which needs to be replaced)
}



Do you guys have any suggestions on what method to use to complete this program or a link that clearly describes tress and how to use them?

Thanks

Is This A Good Question/Topic? 0
  • +

Replies To: Help with read/write for queue

#2 jimblumberg  Icon User is online

  • member icon


Reputation: 4013
  • View blog
  • Posts: 12,386
  • Joined: 25-December 09

Re: Help with read/write for queue

Posted 06 July 2013 - 07:51 AM

Quote

or a link that clearly describes tress and how to use them?


This link may help explain binary trees.

Jim
Was This Post Helpful? 2
  • +
  • -

#3 Skydiver  Icon User is offline

  • Code herder
  • member icon

Reputation: 3548
  • View blog
  • Posts: 10,986
  • Joined: 05-May 12

Re: Help with read/write for queue

Posted 06 July 2013 - 08:22 AM

Yet another duplicate thread...

Ah it looks like jimblumberg split this section off.

Okay, I'll play... your friend suggested using a queue. Where is your queue implementation? Or are you allowed to use std::queue<>?

This post has been edited by Skydiver: 06 July 2013 - 08:22 AM

Was This Post Helpful? 0
  • +
  • -

#4 R2B Boondocks  Icon User is offline

  • D.I.C Head
  • member icon

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

Re: Help with read/write for queue

Posted 06 July 2013 - 08:24 AM

Thanks for that link Jim. I am thinking that my *ifYes is my "left" and my *ifNo is my right. I'll then have to print them for my write function:
/* 
 Given a binary tree, print its 
 nodes according to the "bottom-up" 
 postorder traversal. 
*/ 
void printPostorder(struct node* node) { 
  if (node == NULL) return;
  // first recur on both subtrees 
  printTree(node->left); 
  printTree(node->right);

  // then deal with the node 
  printf("%d ", node->data); 
} 


However instead of a post order do a pre order:
- A pre-order traversal is one in which the data of each node is processed before visiting any of its children


and in order to read them I just need to follow this algorithm?
/* 
 Given a binary tree, return true if a node 
 with the target data is found in the tree. Recurs 
 down the tree, chooses the left or right 
 branch by comparing the target to each node. 
*/ 
static int lookup(struct node* node, int target) { 
  // 1. Base case == empty tree 
  // in that case, the target is not found so return false 
  if (node == NULL) { 
    return(false); 
  } 
  else { 
    // 2. see if found here 
    if (target == node->data) return(true); 
    else { 
      // 3. otherwise recur down the correct subtree 
      if (target < node->data) return(lookup(node->left, target)); 
      else return(lookup(node->right, target)); 
    } 
  } 
} 



I found this for a pre order
void preorder(tnode<T> *t)
{
// the recursive scan terminates on a empty subtree
if (t != nullptr)
{
doSomethingWith (t->nodeValue);
preorder(t->left); // descend left
preorder(t->right); // descend right
}
}


Was This Post Helpful? 0
  • +
  • -

#5 Skydiver  Icon User is offline

  • Code herder
  • member icon

Reputation: 3548
  • View blog
  • Posts: 10,986
  • Joined: 05-May 12

Re: Help with read/write for queue

Posted 06 July 2013 - 08:26 AM

Remember that for reading, you are starting with an empty tree. You'll need to build up the tree also using a pre-order traversal if you saved the data in pre-order.
Was This Post Helpful? 2
  • +
  • -

#6 R2B Boondocks  Icon User is offline

  • D.I.C Head
  • member icon

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

Re: Help with read/write for queue

Posted 06 July 2013 - 08:44 AM

How about something like this since we are reading from a file?
void node::read( istream& in, node*& t )
{
    // replace the line below by your own code
    //t = NULL;
if (t != NULL)
{
    (t -> ifYes);
    (t -> ifNo);
}


Was This Post Helpful? 0
  • +
  • -

#7 Skydiver  Icon User is offline

  • Code herder
  • member icon

Reputation: 3548
  • View blog
  • Posts: 10,986
  • Joined: 05-May 12

Re: Help with read/write for queue

Posted 06 July 2013 - 08:51 AM

It will always be null when you are reading in... See these sections of code that your teacher provided and you said that you aren't supposed to touch:

Animal.cpp:
059 void animalGame(const char* fileName)
060 {
061   // initialize the database
062   node* root = 0;
063   {
064     ifstream in (fileName);
065     if (in.good())
066       in >> root;
067   }



Node.h:
49 inline
50 std::istream& operator>> (std::istream& in, node*& n)
51 {
52   node::read (in, n);
53   return in;
54 }



See how line 62 sets the node to null.
Was This Post Helpful? 2
  • +
  • -

#8 R2B Boondocks  Icon User is offline

  • D.I.C Head
  • member icon

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

Re: Help with read/write for queue

Posted 06 July 2013 - 09:13 AM

 node* root; //take the null root from animal.cpp
    if (in.good()) //if in is good....
   in >> root; // in std::istream& operator>> (std::istream& in, node*& n)
      t = root; //storing the tree root in t (whatevers in root is set to t)


Was This Post Helpful? 0
  • +
  • -

#9 Skydiver  Icon User is offline

  • Code herder
  • member icon

Reputation: 3548
  • View blog
  • Posts: 10,986
  • Joined: 05-May 12

Re: Help with read/write for queue

Posted 06 July 2013 - 09:48 AM

In the other thread, you said that you are only allowed to touch node::read() and node::write(). Are you now saying that you are allowed to touch other code?

Anyway, there is no need for t. Notice this from Animal.cpp:
075   node * current = root;



So, I'm still waiting for the queue that you supposedly are using and is what the thread title also alluded to. So far, I'm still seeing a tree.

This post has been edited by Skydiver: 06 July 2013 - 09:51 AM
Reason for edit:: Put in link to the other thread.

Was This Post Helpful? 0
  • +
  • -

#10 R2B Boondocks  Icon User is offline

  • D.I.C Head
  • member icon

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

Re: Help with read/write for queue

Posted 06 July 2013 - 10:11 AM

No sorry if I suggested otherwise we can only manipulate node.cpp read/write. The queue was just an idea. If I was to pursure it...

Std::queue <list <string> > my_queue;
queue.push(node* current)
In order to build the tree? That should take the root and push it onto stack.

Then under write
If (! Queue.empty ())
Print tree nodes
Was This Post Helpful? 0
  • +
  • -

#11 jimblumberg  Icon User is online

  • member icon


Reputation: 4013
  • View blog
  • Posts: 12,386
  • Joined: 25-December 09

Re: Help with read/write for queue

Posted 06 July 2013 - 10:20 AM

@R2B Boondocks
Is that other thread that Skydiver is referring to also yours? Do you have two different login names?

Jim

This post has been edited by jimblumberg: 06 July 2013 - 10:22 AM

Was This Post Helpful? 0
  • +
  • -

#12 Skydiver  Icon User is offline

  • Code herder
  • member icon

Reputation: 3548
  • View blog
  • Posts: 10,986
  • Joined: 05-May 12

Re: Help with read/write for queue

Posted 06 July 2013 - 11:19 AM

View PostR2B Boondocks, on 06 July 2013 - 01:11 PM, said:

No sorry if I suggested otherwise we can only manipulate node.cpp read/write. The queue was just an idea. If I was to pursure it...

Std::queue <list <string> > my_queue;
queue.push(node* current)
In order to build the tree? That should take the root and push it onto stack.

Then under write
If (! Queue.empty ())
Print tree nodes


The queue is only going to be truly useful if you were planning on doing a breadth-first traversal. (See http://en.wikipedia....Breadth-first_2 )

The comments in node.cpp seem to indicate that the data file should be stored depth first, so a queue although useful if you were using a threaded tree, would actually just make things more complicated in my opinion. Perhaps your friend meant a stack, rather than a queue so that you'll have the non-recursive pre-order tree traversal? (See http://en.wikipedia....ersal#Pre-order )

In my opinion, you would be better off exploring the recursive solution first because of its lower complexity.
Was This Post Helpful? 2
  • +
  • -

#13 R2B Boondocks  Icon User is offline

  • D.I.C Head
  • member icon

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

Re: Help with read/write for queue

Posted 06 July 2013 - 01:28 PM

No sir I only one login and its R2B Boondocks.
Was This Post Helpful? 3
  • +
  • -

#14 R2B Boondocks  Icon User is offline

  • D.I.C Head
  • member icon

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

Re: Help with read/write for queue

Posted 06 July 2013 - 02:46 PM

@Skydiver thanks for that link! I will work on that tonight once I get to a computer. I have a cell phone c++ editor but it can't work with multi file programs yet :( waiting on update.
Was This Post Helpful? 0
  • +
  • -

#15 R2B Boondocks  Icon User is offline

  • D.I.C Head
  • member icon

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

Re: Help with read/write for queue

Posted 06 July 2013 - 04:45 PM

My friend David W (you may recognize the name from here Sky...) helped me finish this up. Basically had to use pre order traversal as you were suggesting except stack was not needed. Viewers of this page may find this site of some help.

http://ellard.org/da...oot/node34.html

I like how the author broke down our choices of traversal and explained why certain ones won't work and which one will work/why.
Was This Post Helpful? 1
  • +
  • -

  • (2 Pages)
  • +
  • 1
  • 2