栈的应用----括号匹配

//使用栈进行括号匹配
#include <stdio.h>
#include <malloc.h>

#define MaxSize 10

typedef struct{
	char data[MaxSize];
	int top;
}SqStack;

void InitStack(SqStack *);	//初始化
int StackEmpty(SqStack);	//判断栈是否为空
void Push(SqStack * , char);		//入栈
char Pop(SqStack * , char *);			//出栈 
int BracketCheck(char [] , int);		//括号检查 

int main(void){
	char str[] = "((([{}}])))";
	int length = strlen(str);
	if(BracketCheck(str , length)){
		printf("括号成对！");
	}else{
		printf("括号不成对！");
	} 
	return 0;
} 

//初始化
void InitStack(SqStack *S){
	S->top = -1;
}

//判断栈是否为空
int StackEmpty(SqStack S){
	if(S.top == -1){
		return 1;
	}
	return 0;
}

//入栈
void Push(SqStack *S , char c){
	if(S->top == MaxSize - 1){
		printf("栈满！
");
		return;
	}else{
		S->data[++S->top] = c;
	}
}

//出栈
char Pop(SqStack *S , char *e){
	if(StackEmpty(*S)){
		printf("栈为空！
");
	}else{
		(*e) = S->data[(S->top)--];
	}
	return (*e);
}

//括号检查 
int BracketCheck(char str[] , int len){
	SqStack S;
	InitStack(&S);
	int i;
	for(i = 0 ; i < len ; i ++){
		if(str[i] == '(' || str[i] == '[' || str[i] == '{'){
			Push(&S , str[i]);
		}else{
			if(StackEmpty(S)){
				return 0;
			}else{
				char topElem;
				Pop(&S , &topElem);
				if(str[i] == ')' && topElem != '('){
					return 0;
				}
				if(str[i] == ']' && topElem != '['){
					return 0;
				}
				if(str[i] == '}' && topElem != '{'){
					return 0;
				}
			}
		}
	}
	return StackEmpty(S);
}