0

I have tried to programme a trie for pset5, but every time I run the spellcheck it isn't finding any misspellings and I can't work out why. Any help would be appreciated.

typedef struct node
        {
            bool is_word;
            struct node*children[ABSIZE+1];
        }
        node;
        unsigned int dicsize=0;
        node* root=NULL;





bool check(const char* word)
{node* nextNode= root;
    unsigned int i=0;
    unsigned int m;  
    do
    {
          m=word[i];
       if (m>=65 && m<=90)
       {
            m|=32;
       }

         if (( m>=97 && m<=122) || (m='\''))
         {
                if (m=='\'')
                    {
                        m = ABSIZE +AOFF;    
                    }
                if (nextNode->children[m-AOFF] == NULL)
                {
                    return false;
                }
                else 
                {
                   nextNode = nextNode->children[m-AOFF];
                }
         }
    i++;
    } while(m !='\0');
    return nextNode->is_word;
}

bool load(const char* dictionary)
{
    FILE* fp= fopen(dictionary,"r");
        if (fp==NULL)
        {
            printf("cannot open file");
            return false;
        }

           root = malloc(sizeof(node));
           unsigned int m = 0;
           node* nextNode = root;

        do
       {
        m=fgetc(fp);

               if (m !='\n' && m!=EOF)
               {
                    if (m=='\'')
                    {
                        m = ABSIZE +AOFF;    
                    }

                    if ( nextNode->children[m-AOFF] == NULL)
                    {
                        nextNode->children[m-AOFF] = malloc(sizeof(node));
                    } 

                 nextNode= nextNode-> children[m-AOFF];

               }

             else if (m=='\n')
               {
                nextNode->is_word = true;
                dicsize++;
                nextNode=root;
               }

        } while ( m!=EOF) ;
         fclose(fp);

    return true;
}
2
  • Since I did mine the same way that you did, I tried to replicate your result by replacing my load and check with yours, making necessary changes to get it to work. When I ran it using the small dictionary as both the dictionary and the input file, I got 100% misspelled words, not 100% correctly spelled, as would be expected. Clearly this is because of changes I made. So, can you answer a few questions? 1. Are you sure that you were getting no misspelled words? 2. What are AOFF and ABSIZE? Can you post the code for them? If I can duplicate your result, then I can look for a cause.
    – Cliff B
    May 10, 2015 at 23:43
  • Hi cliff, sorry I meant to say that it was returning 100% misspelled words and I can't work out why. ABSIZE is 26, AOFF=97 May 11, 2015 at 6:12

1 Answer 1

1

Good news. Your dictionary is loading correctly and you are mostly checking words against it correctly. The problem is related to how you deal with checking the end of each word and how C processes test code. It was well hidden in plain sight!

Here is the culprit:

if (( m>=97 && m<=122) || (m='\''))

For every letter processed, the test condition would hit the ( m>=97 && m<=122) test. Since any letter would satisfy this half of the test condition, the rest of the test was ignored because it is an OR condition. The code would go on it's merry way and would work correctly.

Now, what happens when you get to the end of the word? The value of m is set to 0. The code progresses to the if statement and what happens? First, since m=0, the first half of the test, ( m>=97 && m<=122) is false. This causes the second half of the OR test to finally be evaluated.

Here's the problem (m='\'') isn't a test, it is an assignment. At this point, m will be set to 39. An assignment is always considered true. That causes the program to continue as if you haven't reached the end of the word. It will either return false immediately or continue one more step down the trie via the apostrophe branch. Since no words end with an apostrophe, the next pass generates a false.

Simple fix: (m == '\'')

Note that there are two equals signs, not one. That's what makes it a test and not an assignment. This is a very common bug, and so, so easy to not see! Like I said, it was hiding in plain sight!

If this answers your question, please accept this answer. This takes your question out of the unanswered question pool. Let's keep up on forum maintenance. ;-)

You must log in to answer this question.

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