lex+yacc 构造语法树（三）

lex.l 和yacc.y文件都准备好之后，接下来就是打印的工作了。

构建的语法树实际上是兄弟父子树，每个节点的左节点为自己的大儿子，右节点为与自己相近的兄弟节点。兄弟父子树是通过insert函数来构建的：

void insert(struct Node *parent,struct Node *child)
{   
	struct Node *p;
	if (child==NULL)
		return;
	if(parent->No_Child==0)
	{
		parent->child=child;
		child->IsBegin=1;
		parent->No_Child=1;
	}
	else
	{
		p=parent->child;
		while(p->brother!=NULL)
			p=p->brother;
		p->brother=child;
		child->IsBegin=0;
		parent->No_Child++;
	}
}

由于是通过缩进的形式来打印树，并且在本章中是采用前序遍历的方式，所以需要记录下当前节点所在树的层数，来决定空格的个数。

void printTree(struct Node* root,FILE *stream)
{   
	Node* tmp;
	Node* Child;
	Node* Brother;
	int i = 0;
EnQueue(que, root);
	root->IsBegin=1;
while(!IsEmpty(que))
	{
		DeQueue(que, &tmp);
		fprintf(stream,"\n");
		for(i = 0; i < tmp->col ;i++)
			fprintf(stream,"%-10s", " ");
		fprintf(stream,"%-1s",tmp->name);
		fprintf(stream," ");
		Child=tmp->child;
		Brother=tmp->brother;
		if(Brother!=NULL)
		{
			Brother->col=tmp->col;
			EnQueue(que,Brother);
		}
		if(Child!=NULL)
		{
			Child->col=tmp->col+1;
			EnQueue(que,Child);
		}
	}
}

前序遍历的方式有很多种，最简单的可以递归实现，这里是采用了利用栈的非递归实现。

栈的构造和进出栈（这里的名字还是用的队列但实际是栈）：

#include <malloc.h>
#include <stdio.h>
#include "node.h"
typedef Node* Item;
typedef struct node* Qnode;
typedef struct node
{
   Item data;
   Qnode next;
}Pnode;
typedef struct
{
	Qnode front;
	int  length;
}queue;

//新建队列
queue *NewQueue()
{
	queue *p=(queue *)malloc(sizeof(queue));
	if (p==NULL)
	{
		printf("Error:out of memory.\n");
		return p;
	}
	else
		{p->front=NULL;
		 p->length=0;
		 return p;
		}
}
//查看队列是否为空
int IsEmpty(queue *p)
{
	if(p->length==0)
		return 1;
	else
		return 0;
}
//进栈
void EnQueue(queue *list,Item item)
{  
   Qnode p=(Qnode)malloc(sizeof(Pnode));
   if(p==NULL)
   {
   	printf("Error:empty node.\n");
   	return;
   }
   else
   { 
   	 p->data=item;
   	 if(IsEmpty(list))
     	p->next=NULL;
     else
        p->next=list->front;
    list->length++;
    list->front=p;
    }
 }
 //出栈
 void DeQueue(queue *list,Item *pitem)
 {  
 	Qnode tmp=list->front;
 	if(IsEmpty(list))
 	{
 		printf("Error:empty list.\n");
    return;
 	}
 	else
 	{
 		if(pitem!=NULL)
 			*pitem=tmp->data;
 		list->front=tmp->next;
 		list->length--;
 		free(tmp);
 		if(list->length==0)
 			list->front=NULL;
 	}

 }

至此，准备的程序都已经完成，编译好l和y文件，再gcc一下，便可以打印语法树了~