You are to write a C++ program to implement a spelling checker. The program will
ID: 3708177 • Letter: Y
Question
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
Explanation / Answer
// Spell Checker.cpp : Defines the entry point for the console application.
//
#include "stdafx.h"
#include <stdio.h>
#include <string>
#include <stdlib.h>
#include <fstream>
#include <iostream>
using namespace std;
#pragma warning(disable : 4996)
int k;
char output[100][100];
//char **output;
int factorial(int n)
{
if (n<=1){
return 1;
}
else
return n*factorial(n-1);
}
/*
void print(char *v, const int n){
//sprintf(output[k++],"%s",v);
//strcpy(output[k],v);
//k++;
}
*/
void permute(char *v, const int start, const int n)
{
if (start == n-1) {
//print(v,n);
sprintf(output[k++],"%s",v);
}
else {
for (int i = start; i < n; i++) {
int tmp = v[i];
v[i] = v[start];
v[start] = tmp;
permute(v, start+1, n);
v[start] = v[i];
v[i] = tmp;
}
}
}
void dictionary(int m)
{
ifstream infile("dictionary.txt");
string *list= new string[267751];
//char list[267751][5];
//string list[267751];
if (infile.is_open()){
for (int i=0; i <267751; i++)
{
//infile>>list[i];
getline(infile, list[i]);
//cout<<list[i]<<endl;
}
}
infile.close();
for (int i=0; i<267751; i++)
{
for (int j=0; j<m; j++)
{
if(output[j]==list[i])
{
printf("Spelling suggestions: %s ", list[i]);
}
}
}
}
int main()
{
//read in word
char word[100];
printf ("Enter a word: ");
scanf("%s",word);
int n=strlen(word);
int i,m=factorial(n);
for(int j=0; j<n; j++)
{
word[j]=toupper(word[j]);
}
//generate permutations of the word
//char** output=(char**)malloc(m*sizeof(char*));
//for (i=0; i<m; i++){
//output[i]=(char*)malloc((n+2)*sizeof(char));
//}
k=0;
permute(word,0,n);
for (i=0; i<m; i++){
printf("%d %s ",i,output[i]);
}
//for each word in the permutation list, search it in the dictionary. if match, store in an output array
dictionary(m);
//give names for output
system("pause");
}
Related Questions
drjack9650@gmail.com
Navigate
Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.