括号配对.cpp

数据结构学习中常用的程序．用c语言编写．vc＋＋６．０运行通过

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

#define StackSize 100	/*假定预分配的栈空间最多为100个元素 */

typedef char DataType;	/*假定栈元素的数据类型为字符 */
typedef struct
{	DataType data[StackSize];
	int top;
}SeqStack;


void InitStack(SeqStack *S)
{ /*将顺序栈置空 */
	(*S).top=-1;
}

int StackEmpty(SeqStack *S)
{
	return (*S).top==-1;
}

int StackFull(SeqStack *S)
{
	return (*S).top==StackSize-1;
}

void Push(SeqStack *S,DataType x)
{	if (StackFull(S))
	{	printf("Stack overflow");
		exit(0);					/*上溢，退出运行 */
	}
	(*S).data[++(*S).top]=x;		/*栈顶指针加1后将x进栈 */
}

DataType Pop(SeqStack *S)
{	if (StackEmpty(S))
	{	printf("Stack underflow");
		exit(0);					/*下溢，退出运行 */
	}
	return (*S).data[(*S).top--];	/*栈顶元素返回后将栈顶指针减1 */
}

DataType StackTop(SeqStack *S)
{	if (StackEmpty(S))
	{	printf("Stack is empty");
		exit(0);
	}
	return (*S).data[(*S).top];
}

int correct(char exp[])
{
	int tag=1,i=0;
	SeqStack st;
	InitStack(&st);
	while(exp[i]!='\0'&&tag)
	{
		if(exp[i]=='('||exp[i]=='['||exp[i]=='{')
			Push(&st,exp[i]);
		if(exp[i]==')')
			if(StackEmpty(&st)||Pop(&st)!='(')
				tag=0;
		if(exp[i]==']')
			if(StackEmpty(&st)||Pop(&st)!='[')
				tag=0;
		if(exp[i]=='}')
			if(StackEmpty(&st)||Pop(&st)!='{')
				tag=0;
		i++;
	}
	if(!StackEmpty(&st)) tag=0;
	return(tag);
}
main()
{
	char exp[100];
	printf("请输入算术表达式：");
	scanf("%s",exp);
	if(correct(exp))
		printf("“%s”中的括号配对\n",exp);
	else
		printf("“%s”中的括号不配对\n",exp);
}