darrell@sdcsvax.UUCP (04/21/86)
I have used the following program in an undergraduate systems course as a teaching aid. It takes as input infix expressions composed of single letters, {+, -, *, /} and parentheses and produces a parse tree on the screen. Error handling is not spectacular; neither is the input format since it does not accept identifiers of arbitrary length nor does it hand leading blanks. But, perhaps it will be of use to someone teaching a similar course. Flames to your favorite member of net.thought.police. DL Darrell Long Department of Electrical Engineering and Computer Science University of California, San Diego UUCP: sdcsvax!darrell ARPA: darrell@sdcsvax ------------------------------------------------------------------------ # include <stdio.h> # include <curses.h> /* ** PARSE TREE ** ** DDEL ** Sun Apr 13 13:13:11 PST 1986 */ enum selector { operator, operand }; struct node { enum selector tag; char op; struct node *left, *right; }; static char input; /* ** E -> T { + T } | T { - T } */ struct node *E () { char save; struct node *p, *q, *r, *T(); p = T (); q = (struct node *) NULL; r = (struct node *) NULL; while (input == '+' || input == '-') { save = input; input = getchar (); q = T (); r = (struct node *) malloc (sizeof (struct node)); r -> tag = operator; r -> op = save; r -> left = p; r -> right = q; p = r; } if (r == (struct node *) NULL) return p; else return r; } /* ** T -> F { * F } | F { / F } */ struct node *T () { char save; struct node *p, *q, *r, *F(); p = F (); q = (struct node *) NULL; r = (struct node *) NULL; while (input == '*' || input == '/') { save = input; input = getchar (); q = F (); r = (struct node *) malloc (sizeof (struct node)); r -> tag = operator; r -> op = save; r -> left = p; r -> right = q; p = r; } if (r == (struct node *) NULL) return p; else return r; } /* ** F -> letter | ( E ) */ struct node *F () { struct node *p, *E(); if (((input >= 'A') && (input <= 'Z')) || ((input >= 'a') && (input <= 'z'))) { p = (struct node *) malloc (sizeof (struct node)); p -> tag = operand; p -> op = input; input = getchar (); return p; } else if (input == '(') { input = getchar(); p = E (); if (input == ')') input = getchar (); else { move (23, 37); addstr (") expected."); } return p; } else { move (23, 10); addstr ("factor expected."); return (struct node *) NULL; } } void tree (p, position, width, depth) struct node *p; int position, width, depth; { int i; if (p != (struct node *) NULL) switch (p -> tag) { case operator: { move (depth, position); addch (p -> op); tree (p -> left, position - width / 2, width / 2, depth + 3); tree (p -> right, position + width / 2, width / 2, depth + 3); break; } case operand: { move (depth, position); addch (p -> op); break; } } } main () { input = getchar(); initscr(); tree (E (), 39, 40, 0); move (23, 0); refresh(); } -- Darrell Long Department of Electrical Engineering and Computer Science University of California, San Diego UUCP: sdcsvax!darrell ARPA: darrell@sdcsvax