[数据结构与算法]顺序栈的括号匹配问题-----数据结构与算法笔记

1、括号匹配问题

参考书：《数据结构（C语言）》–严蔚敏等编著，清华大学出版社。
顺序栈相关进栈出栈过程：进出栈过程
相关代码：

#include "stdio.h"
#include "stdlib.h"
#define TRUE     1
#define FALSE    0
#define ERROR    0
#define OK		 1
#define STACK_INIT_SIZE 100
#define STACKINCREMENT 10

typedef int Status;
typedef char SElemType;
typedef struct {
	SElemType *base;
	SElemType *top;
	char stacksize; 	//当前已分配的存储空间
} SqStack;

Status InitStack_Sq(SqStack &S);
//构造一个空栈S，栈top初始化
Status InitStack_Sq(SqStack &S) {
	S.base=(SElemType *)malloc(STACK_INIT_SIZE*sizeof(SElemType));
	if(!S.base) return ERROR;
	S.top = S.base;		//表示为空栈
	S.stacksize = STACK_INIT_SIZE;
	return OK;
}

Status Push_Sq(SqStack &S,SElemType e);
//进栈
Status Push_Sq(SqStack &S,SElemType e) {
	if(S.top - S.base >= S.stacksize) {
		S.base=(SElemType *)realloc(S.base,
		    (S.stacksize+STACKINCREMENT)*sizeof(SElemType));
		if(!S.base) return ERROR;
		S.top = S.base + S.stacksize;
		S.stacksize += STACKINCREMENT;
	}
	*S.top++ = e;	//先将新元素赋给top位置，后将top上移 *S.top=e;S.top++;
	return OK;
}

Status Pop_Sq(SqStack &S,SElemType &e);
//出栈
Status Pop_Sq(SqStack &S,SElemType &e) {
	if(S.top==S.base) return ERROR;
	e = *--S.top;	//或--S.top; e=*S.top;
	return OK;
}

Status GetTop_Sq(SqStack S,SElemType &e);
//获取栈顶元素
Status GetTop_Sq(SqStack S,SElemType &e) {
	if (S.base==S.top) return ERROR;//栈顶为空
	e = *S.top;
	return OK;
}

Status StackEmpty_Sq(SqStack S);
//判栈是否为空
Status StackEmpty_Sq(SqStack S) {
	if(S.top==S.base) return TRUE;
	else return FALSE;
}

Status StackMatch(SqStack &S);
//括号匹配
Status StackMatch(SqStack &S) {
	SElemType e,ch;
	int flag=1;	//定义标志 
	while((ch=getchar()) != '#' && flag) {
		switch(ch) {
			case '(':
			case '[':
			case '{': Push_Sq(S,ch); break;
			case ')': if(Pop_Sq(S,e)==ERROR || e!='(')
						flag = 0;
					break;
			case ']': if(Pop_Sq(S,e)==ERROR || e!='[')
						flag = 0;
					break;
			case '}': if(Pop_Sq(S,e)==ERROR || e!='{')
						flag = 0;
					break;
		}
	}
	if(StackEmpty_Sq(S) && flag)
		return OK;
	else
		return ERROR;
}

int main(void) {
	SqStack S;
	InitStack_Sq(S);
	if(StackMatch(S))
		printf("匹配\n");
	else 
		printf("不匹配\n");
	return 0;
}

/*
输入：[([([])])]#
输出：匹配
输入：[([()])](#
输出：不匹配
输入：[(]#
输出：不匹配
*/