diff options
| -rw-r--r-- | ch6/6-02_common-prefix-printer.c | 239 |
1 files changed, 239 insertions, 0 deletions
diff --git a/ch6/6-02_common-prefix-printer.c b/ch6/6-02_common-prefix-printer.c new file mode 100644 index 0000000..fedb389 --- /dev/null +++ b/ch6/6-02_common-prefix-printer.c @@ -0,0 +1,239 @@ +#include <stdio.h> +#include <string.h> +#include <ctype.h> +#include <stdlib.h> + +/* The C Programming Language: 2nd Edition + * + * Exercise 6-2: Write a program that reads a C program and prints in + * alphabetical order each group of variable names that are identical in the + * first 6 characters, but different somewhere thereafter. Don't count words + * within string and comments. Make 6 a parameter that can be set from the + * command line. + * + * Notes: First off, "variable names" should be "words". It doesn't make sense + * otherwise. + * + * The trick to this is we can traverse the tree with no problem, but to do + * comparisons on the words, we need to know the last one we worked with. With + * two additional static variables in treeprint(), we have all we need to + * manipulate what we're outputting. + */ + +#define BUFSIZE 1000 +#define MAXWORD 100 +#define DEF_PRE_LEN 6 + +struct key { + char *word; + int count; +}; +struct tnode { + char *word; + int count; + struct tnode *left; + struct tnode *right; +}; + +enum states { + NORMAL, + INQUOTE, + INCOMMENT +}; +char buf[BUFSIZE]; +int bufp = 0; +int state = NORMAL; +int minlen; + +int getch(void); +void ungetch(int); +int getword(char *, int); +struct key *binsearch(char *, struct key *, int); +struct tnode *addtree(struct tnode *, char *); +void treeprint(struct tnode *, int); +struct tnode *talloc(void); +char *mystrdup(char *); +int check_prefix(char *, char*, int); + +int main(int argc, char *argv[]) { + switch (argc) { + case 1: + minlen = DEF_PRE_LEN; + break; + case 2: + minlen = strtol(argv[1], NULL, 10); + break; + default: + printf("Too many arguments.\n"); + return 1; + } + struct tnode *root; + char word[MAXWORD]; + root = NULL; + while (getword(word, MAXWORD) != EOF) { + /* Only add the words we need to the tree */ + if (isalpha(word[0]) && strlen(word) > minlen) { + root = addtree(root, word); + if (root == NULL) { + printf("No words at that length or greater were found.\n"); + return 1; + } + } + } + treeprint(root, minlen); + return 0; +} + +int getword(char *word, int lim) { + int c; + char *w = word; + while (isspace(c = getch())) { + } + if (c != EOF && c != '#' && c != '"' && c != '/' && c != '*') { + *w++ = c; + } + if (c == '*' && state == INCOMMENT) { + if ((c = getch()) == '/') { + state == NORMAL; + return '/'; + } + } + /* Ignore comments */ + if (c == '/') { + c = getch(); + if (c == '/') { + while ((c = getch()) != EOF && c != '\n') { + } + return '*'; + } + if (c == '*') { + state = INCOMMENT; + return '*'; + } + } + /* Handle quotes */ + if (c == '"') { + state = INQUOTE; + } + if (state == INQUOTE) { + while ((c = getch()) != '"' && c != EOF) { + } + state = NORMAL; + } + /* Ignore preprocessor lines */ + if (c == '#') { + while ((c = getch()) != '\n' && c != EOF) { + } + } + /* Add exceptions for underscores */ + if (!isalpha(c) && c != '_') { + *w = '\0'; + return c; + } + for ( ; --lim > 0; w++) { + if (!isalnum(*w = getch()) && *w != '_') { + ungetch(*w); + break; + } + } + *w = '\0'; + return word[0]; +} + +struct key *binsearch(char *word, struct key *tab, int n) { + int cond; + struct key *low = &tab[0]; + struct key *high = &tab[n]; + struct key *mid; + while (low < high) { + mid = low + (high-low) / 2; + if ((cond = strcmp(word, mid->word)) < 0) { + high = mid; + } else if (cond > 0) { + low = mid + 1; + } else { + return mid; + } + } + return NULL; +} + +int getch(void) { + return (bufp > 0) ? buf[--bufp] : getchar(); +} + +void ungetch(int c) { + if (bufp >= BUFSIZE) { + printf("ungetch: Too many characters.\n"); + } else { + buf[bufp++] = c; + } +} + +struct tnode *addtree(struct tnode *p, char *w) { + int cond; + if (p == NULL) { + p = talloc(); + p->word = mystrdup(w); + p->count = 1; + p->left = p->right = NULL; + } else if ((cond = strcmp(w, p->word)) == 0) { + p->count++; + } else if (cond < 0) { + p->left = addtree(p->left, w); + } else { + p->right = addtree(p->right, w); + } + return p; +} + +int check_prefix(char *s1, char *s2, int len) { + int i; + if (len == 0) { + return 1; + } + for (i == 0; *s1 == *s2 && *s1 != '\0' && i < len; i++, *s1++, *s2++) { + } + if (i == len) { + return 1; + } + return 0; +} + +void treeprint(struct tnode *p, int len) { + static struct tnode *last; /* The last word we saw */ + static int output = 1; /* Controls whether we output 'last' or not */ + if (p != NULL) { + treeprint(p->left, len); + if (len == 0) { + printf("%4d %s\n", p->count, p->word); + } else { + if (last != NULL) { + if (check_prefix(last->word, p->word, len)) { + if (output) { + printf("%4d %s\n", last->count, last->word); + output = 0; + } + printf("%4d %s\n", p->count, p->word); + } else { + output = 1; + } + } + last = p; + } + treeprint(p->right, len); + } +} + +struct tnode *talloc(void) { + return (struct tnode *) malloc(sizeof(struct tnode)); +} + +char *mystrdup(char *s) { + char *p; + p = (char *) malloc(strlen(s)+1); + if (p != NULL) { + strcpy(p , s); + } + return p; +} |