//===-- dictionary.c ---------------------------------------------*- C -*-===// // // The LLVM Compiler Infrastructure // // This file is distributed under the University of Illinois Open Source // License. See LICENSE.TXT for details. // //===---------------------------------------------------------------------===// #include #include #include #include typedef struct tree_node { const char *word; struct tree_node *left; struct tree_node *right; } tree_node; /* Given a char*, returns a substring that starts at the first alphabet character and ends at the last alphabet character, i.e. it strips off beginning or ending quotes, punctuation, etc. */ char * strip (char **word) { char *start = *word; int len = strlen (start); char *end = start + len - 1; while ((start < end) && (!isalpha (start[0]))) start++; while ((end > start) && (!isalpha (end[0]))) end--; if (start > end) return NULL; end[1] = '\0'; *word = start; return start; } /* Given a binary search tree (sorted alphabetically by the word at each node), and a new word, inserts the word at the appropriate place in the tree. */ void insert (tree_node *root, char *word) { if (root == NULL) return; int compare_value = strcmp (word, root->word); if (compare_value == 0) return; if (compare_value < 0) { if (root->left != NULL) insert (root->left, word); else { tree_node *new_node = (tree_node *) malloc (sizeof (tree_node)); new_node->word = strdup (word); new_node->left = NULL; new_node->right = NULL; root->left = new_node; } } else { if (root->right != NULL) insert (root->right, word); else { tree_node *new_node = (tree_node *) malloc (sizeof (tree_node)); new_node->word = strdup (word); new_node->left = NULL; new_node->right = NULL; root->right = new_node; } } } /* Read in a text file and storea all the words from the file in a binary search tree. */ void populate_dictionary (tree_node **dictionary, char *filename) { FILE *in_file; char word[1024]; in_file = fopen (filename, "r"); if (in_file) { while (fscanf (in_file, "%s", word) == 1) { char *new_word = (strdup (word)); new_word = strip (&new_word); if (*dictionary == NULL) { tree_node *new_node = (tree_node *) malloc (sizeof (tree_node)); new_node->word = new_word; new_node->left = NULL; new_node->right = NULL; *dictionary = new_node; } else insert (*dictionary, new_word); } } } /* Given a binary search tree and a word, search for the word in the binary search tree. */ int find_word (tree_node *dictionary, char *word) { if (!word || !dictionary) return 0; int compare_value = strcmp (word, dictionary->word); if (compare_value == 0) return 1; else if (compare_value < 0) return find_word (dictionary->left, word); else return find_word (dictionary->right, word); } /* Print out the words in the binary search tree, in sorted order. */ void print_tree (tree_node *dictionary) { if (!dictionary) return; if (dictionary->left) print_tree (dictionary->left); printf ("%s\n", dictionary->word); if (dictionary->right) print_tree (dictionary->right); } int main (int argc, char **argv) { tree_node *dictionary = NULL; char buffer[1024]; char *filename; int done = 0; if (argc == 2) filename = argv[1]; if (!filename) return -1; populate_dictionary (&dictionary, filename); fprintf (stdout, "Dictionary loaded.\nEnter search word: "); while (!done && fgets (buffer, sizeof(buffer), stdin)) { char *word = buffer; int len = strlen (word); int i; for (i = 0; i < len; ++i) word[i] = tolower (word[i]); if ((len > 0) && (word[len-1] == '\n')) { word[len-1] = '\0'; len = len - 1; } if (find_word (dictionary, word)) fprintf (stdout, "Yes!\n"); else fprintf (stdout, "No!\n"); fprintf (stdout, "Enter search word: "); } fprintf (stdout, "\n"); return 0; }