星星博客 »  > 

数据结构--括号配对问题

栈的基本应用–括号配对问题

代码如下:

#include<stdio.h>
#include<stdlib.h>
#include<math.h>
#define ERROR 0
#define OK 1
#define N 100
//字符栈
typedef struct
{
	char *elem;
	int top;
}character;
//初始化字符栈
int InitChStack(character *S)
{
	S->elem=(char *)malloc(sizeof(char)*N);
	if(!(S->elem))
		return ERROR;
	S->top=-1;
	return OK;
}
//字符栈入栈
int PushCh(character *S,char e)
{
	S->top++;
	S->elem[S->top]=e;
	
	return OK;
}
//字符栈出栈
int PopCh(character *S,char *e)
{
	if (S->top==-1)
	{
		printf("字符栈空!\n");
		return ERROR;
	}
	*e=S->elem[S->top];
	S->top--;
	return OK;
}
//字符栈取栈顶元素
int GetChTop(character *S)
{
	if (S->top==-1)
	{
		printf("字符栈空!\n");
		return ERROR;
	}
	return S->elem[S->top];
}
//判断输入字符的合法性以及类型
int judgeaAType(char a)
{
	if(a=='{'||a=='['||a=='(')
		return 1;
	else if(a==')'||a==']'||a=='}'||a=='#')
	    return 2;
	else
		return ERROR;
}
//判断字符优先级
int Compera(char ch1,char ch2)
{
	if(ch1=='{'&&ch2=='}'||ch1=='['&&ch2==']'||ch1=='('&&ch2==')')
		return 1;
	else
		return 2;
}
int main()
{
	int i=0;
	char ch1;
	char A[N];
	character ch;
	InitChStack(&ch);
	PushCh(&ch,'#');
	printf("请输入括号(以#结束):\n");
	gets(A);
	ch1=A[0];
	while(ch1!='#'||GetChTop(&ch)!='#')
	{
		if(judgeaAType(ch1)==1)
		{
			PushCh(&ch,ch1);
			i++;
			ch1=A[i];
		}
		else if(judgeaAType(ch1)==2)
		{
			switch(Compera(GetChTop(&ch),ch1))
			{
			case 1:
				PopCh(&ch,&ch1);
				i++;
				ch1=A[i];
				break;
			case 2:
				printf("括号不配对!\n");
				exit(0);
			}
		}
		else
		{
			printf("输入有误!\n");
			exit(0);
		}
	}
	printf("括号配对!\n");
	return 0;
}

相关文章