[net.sources] Parse tree program

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