6 Replies - 321 Views - Last Post: 20 November 2019 - 08:17 PM Rate Topic: -----

#1 mike10lanurias   User is offline

  • New D.I.C Head

Reputation: 0
  • View blog
  • Posts: 13
  • Joined: 20-November 19

Word Concordance using BST as a data structure

Posted 20 November 2019 - 06:01 PM

The task is to write a program that reads a text file and constructs the concordance that contains the distinct words in the file and, for each word, the line number of the first occurrence, and then allows the user to search the concordance for a particular word, and to print out a list of all the distinct words in the concordance. I was wondering how to read a file for each word to each tree for one letter and insert a word into a tree by the first letter of the word. I was also wondering how can I track on the line number of a word that is occurred first and how can I track on how many times the word appears on the file.

#include <iostream>

#ifndef BINARY_SEARCH_TREE
#define BINARY_SEARCH_TREE

template <typename DataType>
class BST
{
 public:
  /***** Function Members *****/
  BST();
  /*------------------------------------------------------------------------
    Construct a BST object.

    Precondition:  None.
    Postcondition: An empty BST has been constructed.
   -----------------------------------------------------------------------*/

  bool empty() const;
  /*------------------------------------------------------------------------
    Check if BST is empty.

    Precondition:  None.
    Postcondition: Returns true if BST is empty and false otherwise.
   -----------------------------------------------------------------------*/

  bool search(const DataType & item) const; 
  /*------------------------------------------------------------------------
    Search the BST for item.

    Precondition:  None.
    Postcondition: Returns true if item found, and false otherwise.
   -----------------------------------------------------------------------*/
   
  void insert(const DataType & item);
  /*------------------------------------------------------------------------
    Insert item into BST.

    Precondition:  None.
    Postcondition: BST has been modified with item inserted at proper 
        position to maintain BST property. 
  ------------------------------------------------------------------------*/
  
  void remove(const DataType & item);
  /*------------------------------------------------------------------------
    Remove item from BST.

    Precondition:  None.
    Postcondition: BST has been modified with item removed (if present);
        BST property is maintained.
    Note: remove uses auxiliary function search2() to locate the node
          containing item and its parent.
 ------------------------------------------------------------------------*/
 
  void inorder(ostream & out) const;
  /*------------------------------------------------------------------------
    Inorder traversal of BST.

    Precondition:  ostream out is open.
    Postcondition: BST has been inorder traversed and values in nodes 
        have been output to out.
    Note: inorder uses private auxiliary function inorderAux().
 ------------------------------------------------------------------------*/
 
  void graph(ostream & out) const;
  /*------------------------------------------------------------------------
    Graphic output of BST.

    Precondition:  ostream out is open.
    Postcondition: Graphical representation of BST has been output to out.
    Note: graph() uses private auxiliary function graphAux().
 ------------------------------------------------------------------------*/
 
 private:
  /***** Node class *****/
  class BinNode 
  {
   public:
    DataType data;
    BinNode * left;
    BinNode * right;

    // BinNode constructors
    // Default -- data part is default DataType value; both links are null.
    BinNode()
    : left(0), right(0)
    {}

    // Explicit Value -- data part contains item; both links are null.
    BinNode(DataType item)
    : data(item), left(0), right(0)
    {}
 
  };// end of class BinNode declaration

  typedef BinNode * BinNodePointer; 
  
  /***** Private Function Members *****/
  void search2(const DataType & item, bool & found,
               BinNodePointer & locptr, BinNodePointer & parent) const;
 /*------------------------------------------------------------------------
   Locate a node containing item and its parent.
 
   Precondition:  None.
   Postcondition: locptr points to node containing item or is null if 
       not found, and parent points to its parent.#include <iostream>
 ------------------------------------------------------------------------*/
 
  void inorderAux(ostream & out, 
                  BinNodePointer subtreePtr) const;
  /*------------------------------------------------------------------------
    Inorder traversal auxiliary function.

    Precondition:  ostream out is open; subtreePtr points to a subtree 
        of this BST.
    Postcondition: Subtree with root pointed to by subtreePtr has been
        output to out.
 ------------------------------------------------------------------------*/
 
  void graphAux(ostream & out, int indent,
                      BinNodePointer subtreeRoot) const;
  /*------------------------------------------------------------------------
    Graph auxiliary function.

    Precondition:  ostream out is open; subtreePtr points to a subtree 
        of this BST.
    Postcondition: Graphical representation of subtree with root pointed 
        to by subtreePtr has been output to out, indented indent spaces.
 ------------------------------------------------------------------------*/
 
 /***** Data Members *****/
  BinNodePointer myRoot; 

}; // end of class template declaration

//--- Definition of constructor
template <typename DataType>
inline BST<DataType>::BST()
: myRoot(0)
{}

//--- Definition of empty()
template <typename DataType>
inline bool BST<DataType>::empty() const
{ return myRoot == 0; }

//--- Definition of search()
template <typename DataType>
bool BST<DataType>::search(const DataType & item) const
{
   BST<DataType>::BinNodePointer locptr = myRoot;
   bool found = false;
   while (!found && locptr != 0)
   {
      if (item < locptr->data)       // descend left
        locptr = locptr->left;
      else if (locptr->data < item)  // descend right
        locptr = locptr->right;
      else                           // item found
        found = true;
   }
   return found;
}

//--- Definition of insert()
template <typename DataType>
inline void BST<DataType>::insert(const DataType & item)
{
   BST<DataType>::BinNodePointer 
        locptr = myRoot,   // search pointer
        parent = 0;        // pointer to parent of current node
   bool found = false;     // indicates if item already in BST
   while (!found && locptr != 0)
   {
      parent = locptr;
      if (item < locptr->data)       // descend left
         locptr = locptr->left;
      else if (locptr->data < item)  // descend right
         locptr = locptr->right;
      else                           // item found
         found = true;
   }
   if (!found)
   {                                 // construct node containing item
      locptr = new BST<DataType>::BinNode(item);  
      if (parent == 0)               // empty tree
         myRoot = locptr;
      else if (item < parent->data )  // insert to left of parent
         parent->left = locptr;
      else                           // insert to right of parent
         parent->right = locptr;
   }
   else
      cout << "Item already in the tree\n";
}

//--- Definition of remove()
template <typename DataType>
void BST<DataType>::remove(const DataType & item)
{
   bool found;                      // signals if item is found
   BST<DataType>::BinNodePointer 
      x,                            // points to node to be deleted
      parent;                       //    "    " parent of x and xSucc
   search2(item, found, x, parent);

   if (!found)
   {
      cout << "Item not in the BST\n";
      return;
   }
   //else
   if (x->left != 0 && x->right != 0)
   {                                // node has 2 children
      // Find x's inorder successor and its parent
      BST<DataType>::BinNodePointer xSucc = x->right;
      parent = x;
      while (xSucc->left != 0)       // descend left
      {
         parent = xSucc;
         xSucc = xSucc->left;
      }

     // Move contents of xSucc to x and change x 
     // to point to successor, which will be removed.
     x->data = xSucc->data;
     x = xSucc;
   } // end if node has 2 children

   // Now proceed with case where node has 0 or 1 child
   BST<DataType>::BinNodePointer 
      subtree = x->left;             // pointer to a subtree of x
   if (subtree == 0)
      subtree = x->right;
   if (parent == 0)                  // root being removed
      myRoot = subtree;
   else if (parent->left == x)       // left child of parent
      parent->left = subtree; 
   else                              // right child of parent
      parent->right = subtree;
   delete x;
}

//--- Definition of inorder()
template <typename DataType>
inline void BST<DataType>::inorder(ostream & out) const
{ 
   inorderAux(out, myRoot); 
}

//--- Definition of graph()
template <typename DataType>
inline void BST<DataType>::graph(ostream & out) const
{ graphAux(out, 0, myRoot); }

//--- Definition of search2()
template <typename DataType>
void BST<DataType>::search2(const DataType & item, bool & found,
                            BinNodePointer & locptr, 
                            BinNodePointer & parent) const
{
   locptr = myRoot;
   parent = 0;
   found = false;
   while (!found && locptr != 0)
   {
      if (item < locptr->data)       // descend left
      {
         parent = locptr;
         locptr = locptr->left;
      }
      else if (locptr->data < item)  // descend right
      {
         parent = locptr;
         locptr = locptr->right;
      }
      else                           // item found
         found = true;
   }
}

//--- Definition of inorderAux()
template <typename DataType>
void BST<DataType>::inorderAux(ostream & out, 
                               BinNodePointer subtreeRoot) const
{
   if (subtreeRoot != 0)
   {
      inorderAux(out, subtreeRoot->left);    // L operation
      out << subtreeRoot->data << "  ";      // V operation
      inorderAux(out, subtreeRoot->right);   // R operation
   }
}

//--- Definition of graphAux()
#include <iomanip>

template <typename DataType>
void BST<DataType>::graphAux(ostream & out, int indent, 
                             BinNodePointer subtreeRoot) const
{
  if (subtreeRoot != 0)
    {
      graphAux(out, indent + 8, subtreeRoot->right);
      out << setw(indent) << " " << subtreeRoot->data << endl;
      graphAux(out, indent + 8, subtreeRoot->left);
    }
}
#endif



Here's the program that I made by far:
#include <iostream>
#include <string>
#include <iomanip>
#include <fstream>

using namespace std;

#include "BST.h"

void uppercase(string&);

int main()
{
	string line;
	string ans;
	BST<string> alphabetical[26];
	int counter;

	string file;
	cout << "Enter a filename that this program reads in: ";
	cin >> file;

	uppercase(line);

	ifstream inFile(file);
	if (!inFile.is_open())
	{
		cout << "File is not found.\n";
	}
	while (inFile >> line)
	{
		alphabetical[line[0] - 'A'].insert(line);
	}

	do
	{
		cout << "Enter a word that you're looking for: (type 'Exit' or 'exit' to leave): ";
		cin >> line;
		if (alphabetical[line[0] - 'A'].search(line))
			cout << "Found a word.\n";

	} while (ans == "Exit" || ans == "exit");
return 0;
}

void uppercase(string& line)
{
	for (int i = 0; i < line.length(); i++)
	{
		char c = line.at(i);
		c = toupper(c);
		line[i] = c;
	}
}



Is This A Good Question/Topic? 0
  • +

Replies To: Word Concordance using BST as a data structure

#2 Skydiver   User is offline

  • Code herder
  • member icon

Reputation: 7136
  • View blog
  • Posts: 24,244
  • Joined: 05-May 12

Re: Word Concordance using BST as a data structure

Posted 20 November 2019 - 07:33 PM

View Postmike10lanurias, on 20 November 2019 - 08:01 PM, said:

I was wondering how to read a file for each word to each tree for one letter and insert a word into a tree by the first letter of the word.

You seem to be doing pretty well with your current implementation for reading a word at a time. You just need to be careful with blindly assuming that the word starts with an upper case letter. You need to trim away any trailing punctuation. What if you read in a number? What if you read in punctuation?
Was This Post Helpful? 0
  • +
  • -

#3 Skydiver   User is offline

  • Code herder
  • member icon

Reputation: 7136
  • View blog
  • Posts: 24,244
  • Joined: 05-May 12

Re: Word Concordance using BST as a data structure

Posted 20 November 2019 - 07:40 PM

View Postmike10lanurias, on 20 November 2019 - 08:01 PM, said:

I was also wondering how can I track on the line number of a word that is occurred first

To do this, you'll need to change your current code which reads in a word at a time, and instead read in a line at a time. (Hint: getline() maybe helpful.) Keep an increment count of the number of lines read. Then using the std::stringstream use your existing code that reads in a word at a time.

View Postmike10lanurias, on 20 November 2019 - 08:01 PM, said:

how can I track on how many times the word appears on the file.

For that you'll need to change your current BST<string> to BST<WordEntry> where WordEntry is a class that holds the word, the first line number where the word is found, and a frequency count. You'll need to search your tree for the word. If it doesn't exist, obviously add a new entry for it. If it is found, then just bump up the count for that entry.
Was This Post Helpful? 0
  • +
  • -

#4 mike10lanurias   User is offline

  • New D.I.C Head

Reputation: 0
  • View blog
  • Posts: 13
  • Joined: 20-November 19

Re: Word Concordance using BST as a data structure

Posted 20 November 2019 - 07:56 PM

Thanks for the help. But, I need to make WordEntry with something inside the brackets in order to work. So, that any words can go to the tree with the first letter of the word. For WordEntry, that would work but I would need two ints. One for the line number and one for the frequency of words. Should I do 'for' or 'while' loop?
Was This Post Helpful? 0
  • +
  • -

#5 mike10lanurias   User is offline

  • New D.I.C Head

Reputation: 0
  • View blog
  • Posts: 13
  • Joined: 20-November 19

Re: Word Concordance using BST as a data structure

Posted 20 November 2019 - 08:02 PM

Where is WordEntry coming from? It should be the name of BST<dataType> called WordEntry. In the angle brackets, it should be dataType only.

This post has been edited by Skydiver: 20 November 2019 - 08:08 PM
Reason for edit:: Removed unnecessary quote. No need to quote the post above yours.

Was This Post Helpful? 0
  • +
  • -

#6 Skydiver   User is offline

  • Code herder
  • member icon

Reputation: 7136
  • View blog
  • Posts: 24,244
  • Joined: 05-May 12

Re: Word Concordance using BST as a data structure

Posted 20 November 2019 - 08:11 PM

Read carefully what I wrote:

View PostSkydiver, on 20 November 2019 - 09:40 PM, said:

... where WordEntry is a class ...


A class is a data type.

As I said, you'll need to define that class so that it holds the pieces of information that you need to keep track of.
Was This Post Helpful? 0
  • +
  • -

#7 mike10lanurias   User is offline

  • New D.I.C Head

Reputation: 0
  • View blog
  • Posts: 13
  • Joined: 20-November 19

Re: Word Concordance using BST as a data structure

Posted 20 November 2019 - 08:17 PM

Okay, thanks for the help.
Was This Post Helpful? 0
  • +
  • -

Page 1 of 1