You are to write a C++ program to implement a spelling checker. The program will first build a dictionary of correctly spelled words by reading the words from the files dict.txt in the current directory. It will then ask the user for the name of a text file to spell check. The program must print to standard output a list of misspelled words and the line numbers on which they occur. Also, for each misspelled word, list any words in the dictionary that are obtainable by applying any of the following rules:

Add one letter to the word (at any position)

Remove one letter from the word

Exchange adjacent characters

Note that line numbers must begin with 1 for the first line in the file.

You are determining what the interface of this program looks like, but you will be evaluated partially on the quality of the interface. Make sure that your output is clear and clean. Overly wordy output is just as bad as cryptic output. Do make sure you spell well this is a spelling checker, after all.

Remember that good design is also important to the evaluation of your program.

You will use a dictionary class that is implemented using an AVL tree. That class is provided for you, and can be found in below Make sure you read the comments carefully. In Part 1, you will submit your working spell checker that uses the given AVL tree. Below is a small test file for using the dictionary. The Following two files can't be changed, you must work with the .h and .cpp file and create the AVL tree from it:

(Dictionary.h) File

// file to implement a binary search tree of Entry objects

#ifndef DICTIONARY_H #define DICTIONARY_H

#include #include

using namespace std;

struct AVLTreeNode { string data; int height; AVLTreeNode* left; AVLTreeNode* right; };

class Dictionary { private: AVLTreeNode* root; int size;

public:

Dictionary(); // Creates an empty dictionary;

Dictionary(const Dictionary& orig); // Copy constructor

virtual ~Dictionary(); // Destructor

Dictionary& operator=(const Dictionary& orig); // assignment operator

void AddEntry(string anEntry); // Preconditions: anEntry has a key not already in the dictionary // Postconditions: anEntry has been added to the dictionary

bool FindEntry(string key); // Postconditions: if key is found in the dictionary, returns true; // otherwise returns false

void PrintSorted(ostream& outStream); // Postconditions: has printed contents of the dictionary in order

private:

void copyDict(const Dictionary& orig); // copies the contents of orig to this dictionary

void deleteDict(); // properly frees all memory occupied by this Dictionary

};

#endif

(Dictionary.cpp) file

// Implementation file for AVL search tree #include #include #include #include #include #include "Dictionary.h"

int max(int x, int y) { if (x > y) return x; else return y; }

Dictionary::Dictionary() { root = NULL; size = 0; }

Dictionary::Dictionary(const Dictionary& orig) { this->copyDict(orig); }

Dictionary::~Dictionary() { this->deleteDict(); }

Dictionary& Dictionary::operator=(const Dictionary& orig) { if (this->root != orig.root) { this->deleteDict(); this->copyDict(orig); } return *this; }

int GetNodeHeight(AVLTreeNode* t) { return t == NULL ? -1 : t->height; }

void RotateWithLeftChild(AVLTreeNode*& k2) { AVLTreeNode* k1 = k2->left; k2->left = k1->right; k1->right = k2; k2->height = max(GetNodeHeight(k2->left), GetNodeHeight(k2->right)) + 1; k1->height = max(GetNodeHeight(k1->left), k2->height) + 1; k2 = k1; }

void RotateWithRightChild(AVLTreeNode*& k2) { AVLTreeNode* k1 = k2->right; k2->right = k1->left; k1->left = k2; k2->height = max(GetNodeHeight(k2->left), GetNodeHeight(k2->right)) + 1; k1->height = max(k2->height, GetNodeHeight(k1->left)) + 1; k2 = k1; }

void DoubleWithLeftChild(AVLTreeNode*& k3) { RotateWithRightChild(k3->left); RotateWithLeftChild(k3); }

void DoubleWithRightChild(AVLTreeNode*& k3) { RotateWithLeftChild(k3->right); RotateWithRightChild(k3); }

void Insert(AVLTreeNode* p, AVLTreeNode*& t) {

if (t == NULL) t = p; else { if (p->data < t->data) // headed left { Insert(p, t->left); if ( GetNodeHeight(t->left) - GetNodeHeight(t->right) == 2) if (p->data < t->left->data) RotateWithLeftChild(t); else DoubleWithLeftChild(t); } else { Insert(p, t->right); if (GetNodeHeight(t->right) - GetNodeHeight(t->left) == 2) if (p->data > t->right->data) RotateWithRightChild(t); else DoubleWithRightChild(t); } } t->height =max(GetNodeHeight(t->left), GetNodeHeight(t->right)) + 1; }

void Dictionary::AddEntry(string anEntry) { // create the node AVLTreeNode* p = new AVLTreeNode; p->data = anEntry; p->height = 0; p->left = NULL; p->right = NULL; Insert(p, root); }

bool Dictionary::FindEntry(string key) { AVLTreeNode* q = root; bool found = false;

while (!found && q) { if (q->data == key) { found = true; } else if (q->data < key) { q = q->right; } else { q = q->left; } } return found; }

void PrintInOrder(AVLTreeNode* p, ostream& outStream) { if (p) { PrintInOrder(p->left, outStream); outStream << p->data << endl; PrintInOrder(p->right, outStream); } }

void Dictionary::PrintSorted(ostream& outStream) { PrintInOrder(root,outStream); }

AVLTreeNode* copyTree(const AVLTreeNode* node) { if (!node) return NULL; else { AVLTreeNode* newNode = new AVLTreeNode; newNode->data = node->data; newNode->height = node->height; newNode->left = copyTree(node->left); newNode->right = copyTree(node->right); return newNode; } }

void Dictionary::copyDict(const Dictionary& orig) { this->size = orig.size; this->root = copyTree(orig.root); }

void deleteTree(AVLTreeNode* node) { if (node) { deleteTree(node->left); deleteTree(node->right); delete node; } }

void Dictionary:: deleteDict() { deleteTree(this->root); this->root = NULL; }

(input file) a accent an as away believe brain but cannot child clouds come decided doubt doubtful eager encouraging encouragingly expect fact first from girl gravely he hers him his i imaginative impulse is it know lady merely must next not of over overly own reprimand roll rolled said sane sanity she shot speaking that the then to truth us was with you