1//===-- dictionary.c ---------------------------------------------*- C -*-===// 2// 3// The LLVM Compiler Infrastructure 4// 5// This file is distributed under the University of Illinois Open Source 6// License. See LICENSE.TXT for details. 7// 8//===---------------------------------------------------------------------===// 9#include <stdlib.h> 10#include <stdio.h> 11#include <ctype.h> 12#include <string.h> 13 14typedef struct tree_node 15{ 16 const char *word; 17 struct tree_node *left; 18 struct tree_node *right; 19} tree_node; 20 21/* Given a char*, returns a substring that starts at the first 22 alphabet character and ends at the last alphabet character, i.e. it 23 strips off beginning or ending quotes, punctuation, etc. */ 24 25char * 26strip (char **word) 27{ 28 char *start = *word; 29 int len = strlen (start); 30 char *end = start + len - 1; 31 32 while ((start < end) && (!isalpha (start[0]))) 33 start++; 34 35 while ((end > start) && (!isalpha (end[0]))) 36 end--; 37 38 if (start > end) 39 return NULL; 40 41 end[1] = '\0'; 42 *word = start; 43 44 return start; 45} 46 47/* Given a binary search tree (sorted alphabetically by the word at 48 each node), and a new word, inserts the word at the appropriate 49 place in the tree. */ 50 51void 52insert (tree_node *root, char *word) 53{ 54 if (root == NULL) 55 return; 56 57 int compare_value = strcmp (word, root->word); 58 59 if (compare_value == 0) 60 return; 61 62 if (compare_value < 0) 63 { 64 if (root->left != NULL) 65 insert (root->left, word); 66 else 67 { 68 tree_node *new_node = (tree_node *) malloc (sizeof (tree_node)); 69 new_node->word = strdup (word); 70 new_node->left = NULL; 71 new_node->right = NULL; 72 root->left = new_node; 73 } 74 } 75 else 76 { 77 if (root->right != NULL) 78 insert (root->right, word); 79 else 80 { 81 tree_node *new_node = (tree_node *) malloc (sizeof (tree_node)); 82 new_node->word = strdup (word); 83 new_node->left = NULL; 84 new_node->right = NULL; 85 root->right = new_node; 86 } 87 } 88} 89 90/* Read in a text file and storea all the words from the file in a 91 binary search tree. */ 92 93void 94populate_dictionary (tree_node **dictionary, char *filename) 95{ 96 FILE *in_file; 97 char word[1024]; 98 99 in_file = fopen (filename, "r"); 100 if (in_file) 101 { 102 while (fscanf (in_file, "%s", word) == 1) 103 { 104 char *new_word = (strdup (word)); 105 new_word = strip (&new_word); 106 if (*dictionary == NULL) 107 { 108 tree_node *new_node = (tree_node *) malloc (sizeof (tree_node)); 109 new_node->word = new_word; 110 new_node->left = NULL; 111 new_node->right = NULL; 112 *dictionary = new_node; 113 } 114 else 115 insert (*dictionary, new_word); 116 } 117 } 118} 119 120/* Given a binary search tree and a word, search for the word 121 in the binary search tree. */ 122 123int 124find_word (tree_node *dictionary, char *word) 125{ 126 if (!word || !dictionary) 127 return 0; 128 129 int compare_value = strcmp (word, dictionary->word); 130 131 if (compare_value == 0) 132 return 1; 133 else if (compare_value < 0) 134 return find_word (dictionary->left, word); 135 else 136 return find_word (dictionary->right, word); 137} 138 139/* Print out the words in the binary search tree, in sorted order. */ 140 141void 142print_tree (tree_node *dictionary) 143{ 144 if (!dictionary) 145 return; 146 147 if (dictionary->left) 148 print_tree (dictionary->left); 149 150 printf ("%s\n", dictionary->word); 151 152 153 if (dictionary->right) 154 print_tree (dictionary->right); 155} 156 157 158int 159main (int argc, char **argv) 160{ 161 tree_node *dictionary = NULL; 162 char buffer[1024]; 163 char *filename; 164 int done = 0; 165 166 if (argc == 2) 167 filename = argv[1]; 168 169 if (!filename) 170 return -1; 171 172 populate_dictionary (&dictionary, filename); 173 fprintf (stdout, "Dictionary loaded.\nEnter search word: "); 174 while (!done && fgets (buffer, sizeof(buffer), stdin)) 175 { 176 char *word = buffer; 177 int len = strlen (word); 178 int i; 179 180 for (i = 0; i < len; ++i) 181 word[i] = tolower (word[i]); 182 183 if ((len > 0) && (word[len-1] == '\n')) 184 { 185 word[len-1] = '\0'; 186 len = len - 1; 187 } 188 189 if (find_word (dictionary, word)) 190 fprintf (stdout, "Yes!\n"); 191 else 192 fprintf (stdout, "No!\n"); 193 194 fprintf (stdout, "Enter search word: "); 195 } 196 197 fprintf (stdout, "\n"); 198 return 0; 199} 200 201