Visual Studio: C++ Coding

Extend our spell checking program(1) along with trie.h(2) and trie.cpp(3) as well as dictionary (Case Study) to suggest the proper spelling of a misspelled word. Consider these types of misspellings: changing the order of letters (copmuter), omitting a letter (computr), adding a letter (compueter), dittography, i.e., repeating a letter (computter), and changing a letter (compurer). For example, if the letter i is exchanged with the letter i + 1 , then the level i of the trie should be processed before level i + 1 .

Note, the code in the case study has been linked to the words \"spell checking program\".

/////////////////////////////////////////////////////////////////////////////////////////////

1.)

#include

#include

#include

#include

#include

using namespace std;

#include \"trie.h\"

char* strupr(char *s) {

char *ss;

for (ss = s; *s = toupper(*s); s++);

return ss;

}

int main(int argc, char* argv[]) {

char fileName[25], s[80], ch;

int i, lineNum = 1;

ifstream dictionary(\"dictionary\");

if (dictionary.fail()) {

cerr

exit(-1);

}

dictionary >> s;

Trie trie(strupr(s)); // initialize root;

while (dictionary >> s) // initialize trie;

trie.insert(strupr(s));

trie.printTrie();

if (argc != 2) {

cout

cin >> fileName;

}

else strcpy(fileName,argv[1]);

ifstream textFile(fileName);

if (textFile.fail()) {

cout

exit(-1);

}

cout

textFile.get(ch);

while (!textFile.eof()) {

while (true)

if (!textFile.eof() && !isalpha(ch)) { // skip non-letters

if (ch == ' ')

lineNum++;

textFile.get(ch);

}

else break;

if (textFile.eof()) // spaces at the end of textFile;

break;

for (i = 0; !textFile.eof() && isalpha(ch); i++) {

s[i] = toupper(ch);

textFile.get(ch);

}

s[i] = '\\0';

if (!trie.wordFound(s))

cout

}

dictionary.close();

textFile.close();

return 0;

}

//////////////////////////////////////////////////////////////////////////////////////////////////

2.)

//************************ trie.h *********************************

class Trie;

class TrieNonLeafNode {

public:

TrieNonLeafNode() {

}

TrieNonLeafNode(char);

private:

bool leaf, endOfWord;

char *letters;

TrieNonLeafNode **ptrs;

friend class Trie;

};

class TrieLeafNode {

public:

TrieLeafNode() {

}

TrieLeafNode(char*);

private:

bool leaf;

char *word;

friend class Trie;

};

class Trie {

public:

Trie() : notFound(-1) {

}

Trie(char*);

void printTrie() {

* prefix = '\\0';

printTrie(0,root,prefix);

}

void insert(char*);

bool wordFound(char*);

private:

TrieNonLeafNode *root;

const int notFound;

char prefix[80];

int position(TrieNonLeafNode*,char);

void addCell(char,TrieNonLeafNode*,int);

void createLeaf(char,char*,TrieNonLeafNode*);

void printTrie(int,TrieNonLeafNode*,char*);

};

/////////////////////////////////////////////////////////////////////////////////////////

3.)

//************************ trie.cpp *********************************

#include

#include

#include

#include \"trie.h\"

using namespace std;

TrieLeafNode::TrieLeafNode(char *suffix) {

leaf = true;

word = new char[strlen(suffix)+1];

if (word == 0) {

cerr

exit(-1);

}

strcpy(word,suffix);

}

TrieNonLeafNode::TrieNonLeafNode(char ch) {

ptrs = new TrieNonLeafNode*;

letters = new char[2];

if (ptrs == 0 || letters == 0) {

cerr

exit(1);

}

leaf = false;

endOfWord = false;

* ptrs = 0;

* letters = ch;

*(letters+1) = '\\0';

}

Trie::Trie(char* word) : notFound(-1) {

root = new TrieNonLeafNode(*word); // initialize the root

createLeaf(*word,word+1,root); // to avoid later tests;

}

void Trie::printTrie(int depth, TrieNonLeafNode *p, char *prefix) {

register int i; // assumption: the root is not a leaf

if (p->leaf) { // and it is not null;

TrieLeafNode *lf = (TrieLeafNode*) p;

for (i = 1; i =>

cout

cout >\" word

}

else {

for (i = strlen(p->letters)-1; i >= 0; i--)

if (p->ptrs[i] != 0) { // add the letter

prefix[depth] = p->letters[i]; // corresponding to

prefix[depth+1] = '\\0'; // position i to prefix;

printTrie(depth+1,p->ptrs[i],prefix);

}

if (p->endOfWord) {

prefix[depth] = '\\0';

for (i = 1; i =>

cout

cout >>\"

}

}

}

int Trie::position(TrieNonLeafNode *p, char ch) {

int i;

for (i = 0; i letters) && p->letters[i] != ch; i++);

if (i letters))

return i;

else return notFound;

}

bool Trie::wordFound(char *word) {

TrieNonLeafNode *p = root;

TrieLeafNode *lf;

int pos;

while (true)

if (p->leaf) { // node p is a leaf

lf = (TrieLeafNode*) p; // where the matching

if (strcmp(word,lf->word) == 0) // suffix of word

return true; // should be found;

else return false;

}

else if (*word == '\\0') // the end of word has

if (p->endOfWord) // to correspond with

return true; // the endOfWord marker

else return false; // in node p set to true;

else if ((pos = position(p,*word)) != notFound &&

p->ptrs[pos] != 0) { // continue

p = p->ptrs[pos]; // path, if possible,

word++;

}

else return false; // otherwise failure;

}

void Trie::addCell(char ch, TrieNonLeafNode *p, int stop) {

int i, len = strlen(p->letters);

char *s = p->letters;

TrieNonLeafNode **tmp = p->ptrs;

p->letters = new char[len+2];

p->ptrs = new TrieNonLeafNode*[len+1];

if (p->letters == 0 || p->ptrs == 0) {

cerr

exit(1);

}

for (i = 0; i

p->ptrs[i] = 0;

if (stop

p,

for (i = len; i >= stop+1; i--) { // copy from tmp letters > ch;

p->ptrs[i] = tmp[i-1];

p->letters[i] = s[i-1];

}

p->letters[stop] = ch;

for (i = stop-1; i >= 0; i--) { // and letters

p->ptrs[i] = tmp[i];

p->letters[i] = s[i];

}

p->letters[len+1] = '\\0';

delete [] s;

}

void Trie::createLeaf(char ch, char *suffix, TrieNonLeafNode *p) {

int pos = position(p,ch);

if (pos == notFound) {

for (pos = 0; pos letters) &&

p->letters[pos]

addCell(ch,p,pos);

}

p->ptrs[pos] = (TrieNonLeafNode*) new TrieLeafNode(suffix);

}

void Trie::insert(char *word) {

TrieNonLeafNode *p = root;

TrieLeafNode *lf;

int offset, pos;

char *hold = word;

while (true) {

if (*word == '\\0') { // if the end of word reached,

if (p->endOfWord)

cout

else p->endOfWord = true; // set endOfWord to true;

return;

} // if position in p indicated

pos = position(p,*word);

if (pos == notFound) { // by the first letter of word

createLeaf(*word,word+1,p);// does not exist, create

return; // a leaf and store in it the

} // unprocessed suffix of word;

else if (pos != notFound && // if position *word is

p->ptrs[pos]->leaf) { // occupied by a leaf,

lf = (TrieLeafNode*) p->ptrs[pos]; // hold this leaf;

if (strcmp(lf->word,word+1) == 0) {

cout

return;

}

offset = 0;

// create as many non-leaves as the length of identical

// prefix of word and the string in the leaf (for cell `R',

// leaf `EP', and word `REAR', two such nodes are created);

do {

pos = position(p,word[offset]);

// word == \"ABC\", leaf = \"ABCDEF\" => leaf = \"DEF\";

if (strlen(word) == offset+1) {

p->ptrs[pos] = new TrieNonLeafNode(word[offset]);

p->ptrs[pos]->endOfWord = true;

createLeaf(lf->word[offset],lf->word +

offset+1,p->ptrs[pos]);

return;

}

// word == \"ABCDE\", leaf = \"ABC\" => leaf = \"DEF\";

else if (strlen(lf->word) == offset) {

p->ptrs[pos] = new TrieNonLeafNode(word[offset+1]);

p->ptrs[pos]->endOfWord = true;

createLeaf(word[offset+1],word+offset+2,p->ptrs[pos]

);

return;

}

p->ptrs[pos] = new TrieNonLeafNode(word[offset+1]);

p = p->ptrs[pos];

offset++;

} while (word[offset] == lf->word[offset-1]);

offset--;

// word = \"ABCDEF\", leaf = \"ABCPQR\" =>

// leaf('D') = \"EF\", leaf('P') = \"QR\";

// check whether there is a suffix left:

// word = \"ABCD\", leaf = \"ABCPQR\" =>

// leaf('D') = null, leaf('P') = \"QR\";

char *s = \"\";

if (strlen(word) > offset+2)

s = word+offset+2;

createLeaf(word[offset+1],s,p);

// check whether there is a suffix left:

// word = \"ABCDEF\", leaf = \"ABCP\" =>

// leaf('D') = \"EF\", leaf('P') = null;

if (strlen(lf->word) > offset+1)

s = lf->word+offset+1;

else s = \"\";

createLeaf(lf->word[offset],s,p);

delete [] lf->word;

delete lf;

return;

}

else {

p = p->ptrs[pos];

word++;

}

}

}