Hey there folks. I am trying to write a program that will take in a paragraph file, and compare it against a "Dictionary" text file, which is being inserted into a Binary Search Tree. Here's what I've got so far:
#include <iostream>
#include <string>
#include <fstream>
#include <iomanip>
#include <cctype>
#include <stack>
using namespace std;
class Node;
stack<string> theStack_;
typedef Node * nodePtr_;
class Node
{
public:
string data_;
nodePtr_ left_;
nodePtr_ right_;
Node() : left_(NULL), right_(NULL), data_("") { }
};
class BST
{
private:
nodePtr_ root_;
public:
BST() : root_(NULL) { }
void insert(string data)
{
insert(data, root_);
}
void insert(string data, nodePtr_ &node)
{
if (node == NULL)
{
node = new Node();
node->data_ = data;
}
else if (data < node->data_)
{
// Traverse left sub tree
insert (data, node->left_);
}
else if ( data > node->data_)
{
// Traverse right sub tree
insert (data, node->right_);
}
else
{
// Node exists
cout << "Node value: " << node->data_ << " already exists!" << endl;
}
}
bool spellCheck(string data)
{
bool broken = spellCheck(data, root_, 0);
return broken;
}
bool spellCheck(string data, nodePtr_ &node, int indent)
{
if (node == NULL)
{
return false; // Empty
}
else if (data == node->data_)
{
return true;
}
else if (data < node->data_)
{
return true;
}
else
{
return spellCheck(data, node->right_, indent+8);
}
}
// Recursive printing
void printTree( ostream &output, nodePtr_ &node, int indent)
{
if (node != NULL)
{
printTree (output, node->right_, indent+8);
output << setw(indent) << node->data_ << endl;
printTree (output, node->left_, indent+8);
}
}
void removeNode (string data)
{
bool found_ = false;
nodePtr_ node = root_;
nodePtr_ parent_ = NULL;
while (!found_ && (node != NULL))
{
if (data < node->data_)
{
// Go left
parent_ = node;
node = node->left_;
}
else if (data > node->data_)
{
// go right
parent_ = node;
node = node->right_;
}
else
{
// found!
found_ = true;
}
}
if (!found_)
{
return;
}
// find the successor
if ((node->left_ != NULL) && (node->right_ != NULL))
{
// Goto left most node
nodePtr_ successor = node->right_;
parent_ = node;
while (successor->left_ != NULL)
{
parent_ = successor;
successor = successor->left_;
}
node->data_ = successor->data_;
node = successor;
}
// now we can delete the node with either one child or no child
nodePtr_ subTree = node->left_;
if (subTree == NULL)
{
subTree = node->right_;
}
if (parent_ == NULL)
{
// delete root node
root_ = subTree;
}
else if (parent_->left_ == node)
{
// delete a node with left subtree
parent_->left_ = subTree;
}
else
{
// Delete a node with a right subtree
parent_->right_ = subTree;
}
delete node;
}
// Trying to sort
bool treeContains( nodePtr_ &node, string item, int indent)
{
if (node == NULL)
{
return false; // tree is empty
}
else if (item == node->data_)
{
return true;
}
else if (item < node->data_)
{
return true;
}
else
{
return treeContains( node->right_, item, indent+8);
}
}
friend ostream& operator<<( ostream &output, BST &bst);
};
ostream& operator<< (ostream &output, BST &bst)
{
bst.printTree(output, bst.root_, 0);
//bst.printTree(bst.root_);
return output;
}
int main()
{
BST bst;
string line;
ifstream dictionaryFile("dictionary.txt");
ifstream paragraphFile("paragraph.txt");
int fileSize = 0; // Size of paragraph
int dictLoaded = 0; // 0 - not loaded, 1 - loaded, 1< - done
bool brokenWord = false;
string search_for = " ";
if (dictLoaded == 0)
{
if (dictionaryFile.is_open())
{
while (!dictionaryFile.eof())
{
getline(dictionaryFile,line);
bst.insert(line);
}
}
dictionaryFile.close();
dictLoaded = 1;
}
if (dictLoaded == 1)
{
if (paragraphFile.is_open())
{
while (dictLoaded >> line)
{
if (line == search_word)
{
}
//getline(paragraphFile,line);
//brokenWord = bst.spellCheck(line);
//if (brokenWord)
//{
// cout << "Bad word! ";
//}
//else
//{
// cout << "No bad words!";
//}
}
}
dictLoaded = 2;
paragraphFile.close();
}
cout << bst << endl;
return 0;
}As you can see, my BST is working just fine, loading the dictionary in and is able to show it. My problem lies here, I planned on searching through the paragraph file word for word, and comparing that word against the dictionary tree. I had the idea of doing this with a stack, putting the words into a stack, checking it, and tossing the word if it's okay. Other wise return the word to the client code, and display the error.
Around line 240 I'm starting to try my search, though I don't know the best way to find the word, right now I was just searching for spaces, and then... blank. =(
Thanks for all your help!
