栈的应用：括号匹配

括号匹配

在学习数据结构的时候，我们知道，栈有很多的应用，其中比较常见的一个就是括号匹配问题。

在使用栈解决括号匹配问题时，其算法思想是：
（1）初试一个空栈，顺序读入括号；
（2）若是右括号，则与栈顶元素进行匹配，分以下两种情况：
①匹配：弹出栈顶元素并进行下一个元素
②不匹配：该输入序列不合法
（3）若是左括号，则压入栈中；
（4）若是全部元素遍历完毕，栈中非空则序列不合法。

注意：以上标识重点的部分，指出了括号匹配时不合法的两种情况。

注意：
以下代码只能检测 ( ) 和 [ ] 括号

• 代码如下：

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

#define BASE_SIZE 10
#define UP_SIZE 5


typedef struct stack {
	char *base;//栈底指针
	char *top;//栈顶指针
	int s_size;//栈的长度
} Stack;

int InitStack(Stack *S) {//初始化栈
	S->base=(char *)malloc(BASE_SIZE*sizeof(char));
	if(!S->base)
		return 0;//开辟空间失败
	S->top=S->base;
	S->s_size=BASE_SIZE;
	return 1;//开辟空间成功
}

int Push(Stack *S,char e) {
	if(S->top-S->base>=S->s_size) {//栈满，重新分配空间
		S->base=(char *)realloc(S->base,(BASE_SIZE+UP_SIZE)*sizeof(char));
		if(!S->base) exit(0);
		S->top=S->base+S->s_size;
		S->s_size=S->s_size+UP_SIZE;
	}
	*(S->top++)=e;
	return 1;
}

char Pop(Stack *S) {
	char e;
	if(S->top-S->base==0)
		return 0;
	e=*(--S->top);
	return e;
}

int judge(Stack *S) {
	char *p;
	char ch;
	scanf("%c",&ch);
	//当未输入左括号，也没有检测到右括号时，持续进行输入，直到碰到括号为止。
	//当未输入左括号，却检测到右括号时，报错返回。
	if(ch=='#') {
		printf("未输入表达式（按照错误对待）！\n");
		return 0;
	}
	while(ch!='('&& ch!='[') {
		if(ch==')' || ch==']')
			return 0;
		scanf("%c",&ch);
	}
	if(ch=='(' || ch=='[')
		Push(S,ch);
	scanf("%c",&ch);
	while(ch!='#') {
		if(ch=='(' || ch==')' || ch=='[' || ch==']') {
			p=S->top;
			Push(S,ch);
			if(*(p-1)=='(') {
				if(*p==')') {
					// 出栈
					Pop(S);
					Pop(S);
				} else  if(*p==']')
					return 0;
			}
			if(*(p-1)=='[') {
				if(*p==']') {
					//[]出栈
					Pop(S);
					Pop(S);
				} else  if(*p==')')
					return 0;
			}
		}
		scanf("%c",&ch);
	}
	if(S->top-S->base==0)//栈空
		return 1;
	else
		return 0;
}

int main() {
	Stack Sta;
	Stack *S=&Sta;

	if(InitStack(S))
		printf("请输入要匹配的表达式，以#结尾:\n");
	if(judge(S)==1)
		printf("\n括号匹配成功！\n");
	else
		printf("\n括号匹配失败！\n");

	return 0;
}
//3+(4*5+[4+6])#
//3+[5-9]*)4*5(#

 

• 运行结果如下：