173 lines · c
1//===-- dictionary.c ---------------------------------------------*- C -*-===//2//3// Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions.4// See https://llvm.org/LICENSE.txt for license information.5// SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception6//7//===---------------------------------------------------------------------===//8#include <ctype.h>9#include <stdio.h>10#include <stdlib.h>11#include <string.h>12 13typedef struct tree_node {14 const char *word;15 struct tree_node *left;16 struct tree_node *right;17} tree_node;18 19/* Given a char*, returns a substring that starts at the first20 alphabet character and ends at the last alphabet character, i.e. it21 strips off beginning or ending quotes, punctuation, etc. */22 23char *strip(char **word) {24 char *start = *word;25 int len = strlen(start);26 char *end = start + len - 1;27 28 while ((start < end) && (!isalpha(start[0])))29 start++;30 31 while ((end > start) && (!isalpha(end[0])))32 end--;33 34 if (start > end)35 return NULL;36 37 end[1] = '\0';38 *word = start;39 40 return start;41}42 43/* Given a binary search tree (sorted alphabetically by the word at44 each node), and a new word, inserts the word at the appropriate45 place in the tree. */46 47void insert(tree_node *root, char *word) {48 if (root == NULL)49 return;50 51 int compare_value = strcmp(word, root->word);52 53 if (compare_value == 0)54 return;55 56 if (compare_value < 0) {57 if (root->left != NULL)58 insert(root->left, word);59 else {60 tree_node *new_node = (tree_node *)malloc(sizeof(tree_node));61 new_node->word = strdup(word);62 new_node->left = NULL;63 new_node->right = NULL;64 root->left = new_node;65 }66 } else {67 if (root->right != NULL)68 insert(root->right, word);69 else {70 tree_node *new_node = (tree_node *)malloc(sizeof(tree_node));71 new_node->word = strdup(word);72 new_node->left = NULL;73 new_node->right = NULL;74 root->right = new_node;75 }76 }77}78 79/* Read in a text file and storea all the words from the file in a80 binary search tree. */81 82void populate_dictionary(tree_node **dictionary, char *filename) {83 FILE *in_file;84 char word[1024];85 86 in_file = fopen(filename, "r");87 if (in_file) {88 while (fscanf(in_file, "%s", word) == 1) {89 char *new_word = (strdup(word));90 new_word = strip(&new_word);91 if (*dictionary == NULL) {92 tree_node *new_node = (tree_node *)malloc(sizeof(tree_node));93 new_node->word = new_word;94 new_node->left = NULL;95 new_node->right = NULL;96 *dictionary = new_node;97 } else98 insert(*dictionary, new_word);99 }100 }101}102 103/* Given a binary search tree and a word, search for the word104 in the binary search tree. */105 106int find_word(tree_node *dictionary, char *word) {107 if (!word || !dictionary)108 return 0;109 110 int compare_value = strcmp(word, dictionary->word);111 112 if (compare_value == 0)113 return 1;114 else if (compare_value < 0)115 return find_word(dictionary->left, word);116 else117 return find_word(dictionary->right, word);118}119 120/* Print out the words in the binary search tree, in sorted order. */121 122void print_tree(tree_node *dictionary) {123 if (!dictionary)124 return;125 126 if (dictionary->left)127 print_tree(dictionary->left);128 129 printf("%s\n", dictionary->word);130 131 if (dictionary->right)132 print_tree(dictionary->right);133}134 135int main(int argc, char **argv) {136 tree_node *dictionary = NULL;137 char buffer[1024];138 char *filename;139 int done = 0;140 141 if (argc == 2)142 filename = argv[1];143 144 if (!filename)145 return -1;146 147 populate_dictionary(&dictionary, filename);148 fprintf(stdout, "Dictionary loaded.\nEnter search word: ");149 while (!done && fgets(buffer, sizeof(buffer), stdin)) {150 char *word = buffer;151 int len = strlen(word);152 int i;153 154 for (i = 0; i < len; ++i)155 word[i] = tolower(word[i]);156 157 if ((len > 0) && (word[len - 1] == '\n')) {158 word[len - 1] = '\0';159 len = len - 1;160 }161 162 if (find_word(dictionary, word))163 fprintf(stdout, "Yes!\n");164 else165 fprintf(stdout, "No!\n");166 167 fprintf(stdout, "Enter search word: ");168 }169 170 fprintf(stdout, "\n");171 return 0;172}173