0

I've been tearing my hair out over this problem for three days now, and just can;t find where I'm going wrong. All seems okay with this program, it loads the dictionary file (using a trie), gets the size correctly and I think unload is almost there. The trouble is, the check function I've written returns all values as false, therefore incorrectly spelled.

I can;'t for the life of me work out where this is going wrong. I think the code makes sense and should do it right. I've rewritten and restructured the code a few times with the same result. Any help at this point would be greatly appreciated.

// for each letter in 'word'
for (int i = 0, n = strlen(word); i < n;i++)
{
    if (word[i] == '\0')
    {
        // null character, break out of loop
        break;
    }

    int l = toupper(word[i]) - 65;
    if(pointer->children[l] == NULL)
    {
        // match not made - mispelled word
        return false;
    }
    else
    {   
        // check for apostrophe
        if (word[i] == '\'')
        {
            pointer = pointer->children[26];
        }
        // check for is_word and end of passed in word
        else if (i == n - 1 && pointer->is_word == true)
        {
            return true;
        }
        pointer = pointer->children[l];
    }
}
return false;

The above code is my first attempt, and as I say it returns all words checked as false. I rewrote the code as follows, but this returns the same results.

    while (word != NULL)
{
    for (int i = 0, n = strlen(word); i < n; i++)
    {
        int l = toupper(word[i]);
        if (word[i] == '\'')
        {
            pointer = pointer->children[26];
        }
        else if (i == n-1 && pointer->is_word == true)
        {
            return pointer->is_word;
        }
        else
        {
            pointer = pointer->children[l];
        }
    }
}
return pointer->is_word;

Thanks in advance,

2
  • 1. why are using the while loop? when the for loop surfice. 2. you should try handling the apostrophy before indexing the alphabets. – brainscientist Aug 13 '15 at 15:42
  • HI & thanks for your comment, the two loops weren't used at the same time, the while loop was a temporary replacement to see if i could work a different solution to the problem, but this gave me the same result :( – noobcake Aug 14 '15 at 10:59
2

The second version looks cleaner so let's go with that. Without seeing the rest of the check function, or the load function, I think I still found your problem. Assuming that pointer->children[] is a 27 element array and is indexed from 0 to 26, then look at how you're trying to traverse down the tree.

    int l = toupper(word[i]);
    pointer = pointer->children[l];

You're using an ASCII value for the index because you forgot to subtract 65.

The code could be simplified further by removing the else-if clause. You simply need to traverse the trie until you get to the end of the word and return the value in is_word for the last letter, whether it's true or false. There's no need to test what that value is. The for loop will stop the traversal at the last character, so again, no need for the test in the if statement.

However, you've overlooked something. What happens if you have a word that isn't in the dictionary, but the first part of the word is there? For example, if your word is 'toad' and isn't in the dictionary, but 'to' is there, then when you traverse to 'a', then you go off the tree. You need to check for

pointer->children[x]==NULL.

Interesting that you did those things in the first version.

Regarding the while loop and/or testing that word isn't null. The calling code validates that you have a word and the spec basically says that you can assume that you are given a valid word, so while it's a good coding lesson and good prectice to check, it isn't necessary. Also, if you do want to make the check, it isn't necessary to put the code to process the word inside the loop. In fact, it makes it less readable and more confusing for later maintenance or enhancement. The better practice would be to simply have an if statement to test for null and return false if the test is true.

No guarantees that this fixes it, but it will get you closer.

If this answers your question, please click the check to accept, and remove your question from the unanswered question pool. Let's keep up on forum maintenance. ;-)

1
  • thanks for the reply. i don't know what to say, forgetting to subtract 65, and forgetting to check for the NULL value when I rewrote in the while loop were pretty stupid mistakes, but sometimes it takes fresh eyes to point them out :) I've tidied up the code and removed the extra checking that you pointed out and, as you say, I'm a lot closer... thanks again – noobcake Aug 14 '15 at 11:22

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .