链栈实现括号匹配

<pre name="code" class="cpp">//括号匹配
//利用栈的操作思想，实现括号匹配的检验。如输入3*{2+[2*5/(2+9)]},则括号匹配
//正确，但如果输入3*(2+6/[2*9)],则括号匹配失败。
//优先级说明:
//()优先级最高，里面不能嵌套任何其他括号(包括小括号);
//[]优先级其次，里面只能嵌套小括号
//{}优先级最低，里面可以嵌套大括号和小括号 
#include <stdio.h>
#include <stdlib.h>
#include <string.h>

//定义栈的结构，采用链栈的形式
typedef struct node
{
	char data;//存储进栈的括号
	struct node *next;//指向后继结点
}linkstack;//linkstack为链栈的名称

int Initlinkstack(linkstack *&head);//对带有头结点的链栈进行初始化
void Pushlinkstack(linkstack *&head,char e,int &r);//进栈，e为进栈的元素
void Poplinkstack(linkstack *&head,int &r);//出栈，出栈元素未返回
int Emptylinkstack(linkstack *head);//判断链栈是否为空，空则返回1，否则返回0
char Getdata(linkstack *head);//取栈顶元素

int Initlinkstack(linkstack *&head)
{
	head=(linkstack *)malloc(sizeof(linkstack));//为head(头结点)分配空间
	head->next=NULL;
	if(head==NULL)//若空间分配失败则返回0，否则返回1
		return 0;
	return 1;
}

void Pushlinkstack(linkstack *&head,char e,int &r)//把e压入栈
{
	linkstack *s,*p=head;
	s=(linkstack *)malloc(sizeof(linkstack));
	if(!s)//为新节点分配空间，失败则返回
	{
		printf("空间分配失败!\n");
		return ;
	}
	while(p->next)//查找链尾
		p=p->next;
	s->data=e;//空间分配成功，将e入栈
	p->next=s;//将s插入到链尾
	s->next=NULL;
	r++;//p记录入栈与出栈的括号总数,若入栈和出栈的括号总数与总括号数相等，则优先级正确 
}

void Poplinkstack(linkstack *&head,int &r)
{
	linkstack *s,*p=head;
	if(head->next==NULL)//若为空栈则返回
	{
		printf("空栈,出栈失败!\n");
		return ;
	}
	else//不为空栈则出栈(删除栈顶元素)
	{
		while(p->next)//查找倒数第二个链栈元素的地址
		{
			s=p;
			p=p->next; 
		}
		s->next=NULL;
		free(p);//释放删除元素的空间
	}
	r++;//同样，括号出栈p也要加一 
}

char Getdata(linkstack *head)
{
	linkstack *s=head;
	while(s->next)//查找最后一个元素的地址
		s=s->next;
	return s->data;//返回最后一个元素
}

int Emptylinkstack(linkstack *head)
{
	return head->next==NULL;
}

int main()
{
	char a[50];//存储表达式 
	int m,i,ch;//m存储表达式的长度,i做循环变量
	int r,q;//检查优先级是否正确
	linkstack *head;//链栈的头结点
	if(Initlinkstack( head ))//对带有头结点的链栈进行初始化
		printf("链栈初始化成功!\n");
	do{
		printf("请输入表达式:\n");
		gets(a);//输入表达式
		r=0;//初始化r为0，即进栈与出栈的括号数为0 
		for(i=0;i<strlen(a);i++)
		{
			if((a[i]=='['&&Getdata(head)=='{')||(a[i]=='['&&Emptylinkstack(head)))//若为左括号且优先级正确就进栈
				Pushlinkstack(head,a[i],r);//进栈操作
			if((a[i]=='('&&(Getdata(head)=='['||Getdata(head)=='{'))||(a[i]=='('&&Emptylinkstack(head)))//优先级检测 
				Pushlinkstack(head,a[i],r);
			if(a[i]=='{'&&Emptylinkstack(head))//优先级检测 
				Pushlinkstack(head,a[i],r);
			if(a[i]==']'&&Getdata(head)=='[')//若为右括号且和栈顶元素配对就出栈
				Poplinkstack(head,r);//出栈操作
			if(a[i]=='}'&&Getdata(head)=='{')
				Poplinkstack(head,r);
			if(a[i]==')'&&Getdata(head)=='(')
				Poplinkstack(head,r);
		}
		for(i=0,q=0;i<strlen(a);i++)
			if(a[i]=='('||a[i]=='['||a[i]=='{'||a[i]==']'||a[i]=='}'||a[i]==')')
				q++;
		if(Emptylinkstack(head)&&r==q)//对栈进行判空，若为空，则(进栈==出栈)且优先级正确,则括号配对成功
			printf("括号配对正确!\n");
		else
			printf("括号配对错误!\n");
		printf("要继续吗(1 or 0)?\n");
		scanf("%d",&ch);
		getchar();
	} while (ch==1);
	return 0;
}</pre>