Just need to see if in the right direction.

[skinnygod]

Hello I was wondering if anyone could help me with my program. I am tasked with writing a spell check class that will take a string and check a set of strings to see if it is spelled correctly using hash tables. I have written what I could however, I confused on how I will actually pass the string to be compared with the misspelled word to let the program know if it is misspelled. If someone could help me and just explain to me how it is that I can do that I would appreciate it!! Thank you!!!!

Main file:

#include <iostream>
#include <string>
#include "spellCheck.h"

int main()
{
    std::string s;
    
    std::cout << "Please enter a sentence: ";
    
    std::cin >> s;
    
    spellCheck hashObject;

    
    hashObject.checkSpelling(s);

	return 0;
}

spellCheck.cpp

#include <iostream>
#include "spellCheck.h"
#include <fstream>
#include <string>

spellCheck::spellCheck()
{
    for (int i = 0; i < tableSize; i++)
    {
        hashtbl[i] = new item;
        hashtbl[i]->word = "empty";
        hashtbl[i]->next = NULL;
    }
}


spellCheck::~spellCheck(void)
{
}

void spellCheck::additem(std::string word)
{
    int index = hash(word);
    
    if(hashtbl[index]->word == "empty")
    {
        hashtbl[index]->word = word;
    }
    else
    {
        item* Ptr = hashtbl[index];
        item* n = new item;
        n->word = word;
        n->next = NULL;
        while(Ptr->next != NULL)
        {
            Ptr = Ptr->next;
        }
        Ptr->next = n;
        
    }
}

int spellCheck::numberOfItems(std::string mispells)
{
    int index = hash(mispells);
    int count = 0;
    
    if (hashtbl[index]->word == "empty")
    {
        return count;
    }
    else
    {
        count++;
        item* Ptr = hashtbl[index];
        while(Ptr->next != NULL)
        {
            count++;
            Ptr = Ptr->next;
        }
    }
    
    return count;
    
}

/*void spellCheck::printTbl()
{
    int number;
    for (int i = 0; i < tableSize; i++)
    {
        number = numberOfItems(i);
        std::cout << "----------------------\n";
        std::cout << "index = " << i << std::endl;
        std::cout << hashtbl[i]->word << std::endl;
        std::cout << "# of items = " << number << std::endl;
        std::cout << "----------------------\n";
    }
    
}*/

void spellCheck::printItems(int index)
{
    item* Ptr = hashtbl[index];
    
    if(Ptr->word == "empty")
    {
        std::cout << "index = " << index << " is empty\n";
    }
    else
    {
        std::cout << "index = " << index << " contains the following items\n";
        while (Ptr != NULL)
        {
            std::cout << "------------------\n";
            std::cout << Ptr->word << std::endl;
            std::cout << "------------------\n";
            Ptr = Ptr->next;
        }
    }
}

int spellCheck::hash(std::string key)
{
	int hashvar = 0;
	int index;

	for(int i = 0; i < key.length(); i++)
	{
		hashvar = hashvar + (int)key[i];
	}

	index = hashvar % tableSize;


	return index;

}

void spellCheck::dictionary()
{
    std::ifstream infile;
    
    std::string mispells;
    
    infile.open("Dictionary.txt");
    
    if (infile.fail())
    {
        std::cout << "File could not be opened.";
        exit(1);
    }
    while (infile >> mispells)
    {
        if (!numberOfItems(mispells))
            {
                additem(mispells);
            }
    }
    infile.close();
    
}

void spellCheck::checkSpelling(std::string s)
{
    
}

spellCheck.h

#include <string>
#pragma once

#ifndef SPELLCHECK_H
#define SPELLCHECK_H
class spellCheck
{
private:
	static const int tableSize = 19000;
    
    struct item
    {
        std::string word;
        item* next;
    };
    
    item* hashtbl[tableSize];

public:
	spellCheck();
	~spellCheck(void);
	int hash (std::string key);
    void additem(std::string word);
    int numberOfItems(std::string mispells);
    //void printTbl();
    void printItems(int index);
    void dictionary();
    void checkSpelling(std::string s);
};

#endif /*SPELLCHECK_H*/ 

[dhayden]

Why do you have the "empty" entries? They aren't necessary and just take up space.

additem() should just add the item to the start of the list. This faster and easier:

void spellCheck::additem(std::string word)
{
    int index = hash(word);
    
    item* n = new item;
    n->word = word;
    n->next = hashtbl[index];
    hashtbl[index] = n;
}

As for checking a word, just find the bucket where the word would be located if it were in the hash table. Then search the words in that bucket for the word you're looking for. If you don't find it, then the word appears to be misspelled.

[skinnygod]

Thank you!!! that really cleared up the idea of the spell check I was looking for something in simpler terms since everything I found was using more flash terms and english. However, one more question for the checking of a sentence would I have to make a function to split the sentence in to separate strings or can I do it without splitting the sentence???

As for the empty, I've been looking around and I noticed people using empty so I was under the impression it was good practice thank you though!!!

[dhayden]

You can read words one at a time like this:

string str;
while (cin >> str) {
    // so something with str
}

This will read white-space-separated strings. Whitespace is spaces, tabs, new lines, etc.

You might need to process the strings some more before checking them in the spell checker:
- If they can be in upper and lower case then you should convert then to one or the other. AND you will need to convert the dictionary words to the same case before putting them in the dictionary.

In other words, if the dictionary contains "Hello" and you're checking the word "heLLO" then you might need to convert the dictionary word to "hello" and the word you're checking to "hello" so they will match.

If the input can contain punctuation then you'll need to remove it before checking the word. In other words, if the input contains "This is a test." then the last word you read will be "test." and that won't match "test" in the dictionary because of the period at the end.

[skinnygod]

Ok so for the checkSpelling function this is what I have so far for the basic checking of it. I am not entirely confident that it is working correctly as it is not putting out either cout statements. The function is all the way at the bottom.


main

#include <iostream>
#include <fstream>
#include <string>
#include "spellCheck.h"

int main()
{
    spellCheck hashObject;
    
    std::ifstream infile;
    
    std::string words;
    
    infile.open("Dictionary.txt");
    
    if (infile.fail())
    {
        std::cout << "File could not be opened.";
        exit(1);
    }
    while (infile >> words)
    {
        if (!hashObject.numberOfItems(words))
        {
            hashObject.additem(words);
        }
    }
    infile.close();
    
    std::string s;
    
    std::cin >> s;
    
    hashObject.checkSpelling(s);

	return 0;
}

#include <iostream>
#include "spellCheck.h"
#include <fstream>
#include <string>

spellCheck::spellCheck()
{
    for (int i = 0; i < tableSize; i++)
    {
        hashtbl[i] = new item;
        hashtbl[i]->word = "empty";
        hashtbl[i]->next = NULL;
    }
}

void spellCheck::additem(std::string word)
{
    int index = hash(word);
    
    item* n = new item;
    n->word = word;
    n->next = hashtbl[index];
    hashtbl[index] = n;
}

int spellCheck::numberOfItems(std::string words)
{
    int index = hash(words);
    int count = 0;
    
        count++;
        item* Ptr = hashtbl[index];
        while(Ptr->next != NULL)
        {
            count++;
            Ptr = Ptr->next;
        }
    
    return count;
    
}

int spellCheck::hash(std::string key)
{
	int hashvar = 0;
	int index;

	for(int i = 0; i < key.length(); i++)
	{
		hashvar = hashvar + (int)key[i];
	}

	index = hashvar % tableSize;


	return index;

}

void spellCheck::checkSpelling(std::string s)
{
    int itemsearch = hash(s);
    
    bool correct = false;
    std::string word;
    
    item* Ptr = hashtbl[itemsearch];
    
    while(Ptr != NULL)
    {
        if(Ptr->word == s)
        {
            correct = true;
            word = Ptr->word;
        }
        Ptr = Ptr->next;
    }
    if (correct == true)
    {
        std::cout << "Spelled Correctly.";
    }
    else
    {
        std::cout << "Spelled incorrectly:";
    }
    
}

#include <string>
#pragma once

#ifndef SPELLCHECK_H
#define SPELLCHECK_H
class spellCheck
{
private:
	static const int tableSize = 19000;
    
    struct item
    {
        std::string word;
        item* next;
    };
    
    item* hashtbl[tableSize];

public:
	spellCheck();
	int hash (std::string key);
    void additem(std::string word);
    int numberOfItems(std::string words);
    void printItems(int index);
    void checkSpelling(std::string s);
};

#endif /*SPELLCHECK_H*/

[dhayden]

To get it to print something, try adding \n to the end of the strings at lines 80 & 84 in spellCheck::checkSpelling()

What is spellCheck::numberOfItems() supposed to do? Right now it returns the number of items in the bucket for word. So when you call it inside main(), it's basically saying "if there is already a word in this word's bucket, then don't bother to add this word." If I remove the call to numberOfItems, so that every word in the dictionary gets inserted into the hash table, then the program works for me.

This should be enough to get the program working. Once it's working, you might want to consider these additional changes. Be sure to save the working version before attempting to do any of this.

The constructor is still putting the string "empty" in each bucket. There's no need for that. Just initialize all of the pointers to nullptr.

It may be personal preference, but I prefer a for() loop when going through a linked list. That way all of the "loop" logic is in one place, and all of the "what to do inside the loop" is in another. When you use a while loop, the logic for is all over the place. Compare this:

    item *Ptr = hashtbl[index];
    while (Ptr->next != NULL) {
        count++;
        Ptr = Ptr->next;
    }

to this:

    for (item *Ptr = hashtbl[index]; Ptr->next != nullptr; Ptr = Ptr->next) {
        count++;
    }

In the second case, the for loop makes it clear that you're walking through each item in the list.

Look at checkSpelling(). Right now it takes a word and tells you whether it's spelled correctly. Now suppose you're asked to modify the program so that it reads a file and prints out the number of misspelled words. You can't reuse checkSpelling() without modifying it.

This is why it's always a good idea to separate computation (computing an answer of some sort) from presentation (displaying the results of the answer). In this case, checkSpelling() should just return bool to indicate whether the word is spelled correctly, and the main program should print the appropriate results based on that:

// Return true if the string s is spelled correctly, otherwise false.
bool
spellCheck::checkSpelling(std::string s)
{
    int itemsearch = hash(s);

    bool correct = false;
    std::string word;

    for (item *Ptr = hashtbl[itemsearch]; Ptr != nullptr; Ptr = Ptr->next) {
        if (Ptr->word == s) {
            return true;
        }
    }
    return false;
}
...
int main()
{
...
    std::string s;
    std::cin >> s;
    if (hashObject.checkSpelling(s)) {
        std::cout << "Spelled Correctly.\n"; // dmh
    } else {
        std::cout << "Spelled incorrectly:\n"; // dmh
    }
}

Modifying this program to print the number of misspelled words in a file would be almost trivial.

[skinnygod]

That was helpful, I do prefer using the for as I see what you're saying, so in order to make sure I understand. The for loop everything necessary to make the loop happen is contained there with in the loop in the parenthesis while with a while loop its all over the place in order to just make the loop function correctly, right? As for the splitting of the checkSpelling() I was originally going to do that but I not why it would be a good idea however, with the way you're explaining it, it makes a lot more sense to do that instead.

Also as for printing I ended up figuring out it was the newline characters I never added them in there when I noticed that was the issue I was beating myself up about for a good hour or so something so simple.

Again thank you so much!!

[skinnygod]

Hi again,

Is there a way to stop this loop after each word is spell checked and converted to lower case???

        while(std::cin >> s)
        {
            for(int i = 0; i < s.length(); i++)
            {
                s[i] = tolower(s[i]);
            }
            if (spellObject.checkSpelling(s))
            {
                std::cout << "Spelled Correctly: " << s << std::endl;
                //std::cout << spellObject.hash(s) << std::endl;
            }
            else
            {
                std::cout << "Spelled incorrectly:" << s << std::endl;
            }
        }

Thanks for the help again!!

[dhayden]

You could run it from a terminal window and give the input via the keyboard. That way you could enter the words one per line.

As for the splitting of the checkSpelling() I was originally going to do that but I not why it would be a good idea however, with the way you're explaining it, it makes a lot more sense to do that instead.

I had a real "ah-ha" moment after programming for several years when I realized this: the functions and methods that you right shouldn't "do the work." They should make it easy to do the work. If you think this way, you'll write functions that are a little "lower level" and generic. Then you will use these functions to accomplish your task. As a result, you write much more modular code.