grammar_tree.c

来自「数据结构源码合集」· C语言 代码 · 共 56 行

#include <stdio.h>
#include <stdlib.h>

typedef struct node *link;
struct node
{
	char item;
	link l, r;
};

link NODE(char item)
{
	link t = malloc(sizeof *t);
	t->item = item;
	t->l = t->r = NULL;

	return t;
}

link parse(char *s)
{
	link t;
	if(*s == '\0')
		return NULL;
	if(*s == ' ')
		s++;
	if(*s >= '0' && *s <= '9')
		return NODE(*s++);
	if(*s == '+' || *s == '*')
	{
		t = NODE(*s);
		t->l = parse(++s);
		t->r = parse(++s);

		return t;
	}
}

void pre_order(link t)
{
	if(!t)
		return;
	printf("%c", t->item);
	pre_order(t->l);
	pre_order(t->r);
}

int main(void)
{
	link T = parse("* + 1 2 + 3 4");
	pre_order(T);
	puts("");

	return 0;
}