本文共 3057 字，大约阅读时间需要 10 分钟。

栈的应用----括号匹配问题(这里借鉴朱战立老师的算法思想)

一、问题引入:

假设一个算数表达式种包含圆括号、方括号和花括号三种类型的括号，编写一个函数，用来判别表达式中的括号是否正确配对。

二、算法思想:

括号匹配共有以下4种情况:

• 左右括号配对次序不正确
• 左括号多于右括号
• 右括号多于左括号
• 左右括号匹配成功
  具体实现方法:顺序扫描算术表达式(表现为一个字符串)，当遇到3种类型的左括号时，让该括号进栈。当扫描到某一种类型的右括号时，比较当前栈顶括号是否与之匹配，若匹配，则退栈继续进行判断:若当前栈顶符号与当前扫描的括号不相同，则左、右括号配对次序不正确。若字符串当前为某种类型的右括号而堆栈已空，则右括号多于左括号；字符串循环扫描结束时，若堆栈非空(即堆栈中还有某种类型左括号)，则说明左括号多于右括号；如果未出现上述3种情况，则说明左右括号匹配正确。

三、代码实现(Visual Studio 2017开发环境)

头文件 stack.h

#pragma once#include
   
    typedef struct Stacknode {
   	Elemtype data;	struct Stacknode *next;}Stacktype;//初始化void InitStack(Stacktype **top) {
   	*top = (Stacktype *)malloc(sizeof(Stacktype));	(*top)->next = NULL;}//入栈操作int pushStack(Stacktype *top, Elemtype x) {
   	Stacktype *p;	p = (Stacktype*)malloc(sizeof(Stacktype));//申请结点	p->data = x;	p->next = top->next;	top->next = p;	return true;}//出栈操作Elemtype popStack(Stacktype *top) {
   	Stacktype *p;	Elemtype x;	if (top->next == NULL) {
   		printf("空栈!!");		return NULL;	}	else {
   		p = top->next;		top->next = p->next;		x = p->data;		free(p);		return x;	}}//取栈顶数据元素Elemtype GetTop(Stacktype *top, Elemtype *x) {
   	if (top->next == NULL) {
   		return NULL;	}	else {
   		*x = top->next->data;		return (top->next->data);	}}//判断栈不空int StackNotEmpty(Stacktype *top) {
   	if (top->next != NULL) {
   		return 1;	}	else {
   		return 0;	}}//括号匹配void bracket(char exp[], int n) {
   	//判断有n个字符的字符串exp的左右括号是否配对正确	Stacktype *myStack;	int i;	char c;	InitStack(&myStack);//初始化堆栈	for (i = 0; i < n; i++) {
   		if ((exp[i] == '(') || (exp[i] == '[') || (exp[i] == '{')) {
   //碰到左括号，入栈			pushStack(myStack, exp[i]);		}		else if ((exp[i] == ')') && StackNotEmpty(myStack) && GetTop(myStack, &c) && c == '(') {
   //判断'()'			popStack(myStack);		}		else if ((exp[i] == ')') && StackNotEmpty(myStack) && GetTop(myStack, &c) && c != '(') {
   			printf("左右括号配对次序不正确!\n");			return;		}		else if ((exp[i] == ']') && StackNotEmpty(myStack) && GetTop(myStack, &c) && c == '[') {
   //判断'[]'			popStack(myStack);		}		else if ((exp[i] == ']') && StackNotEmpty(myStack) && GetTop(myStack, &c) && c != '[') {
   			printf("左右括号配对次序不正确!\n");			return;		}		else if ((exp[i] == '}') && StackNotEmpty(myStack) && GetTop(myStack, &c) && c == '{') {
   //判断'{}'			popStack(myStack);		}		else if ((exp[i] == '}') && StackNotEmpty(myStack) && GetTop(myStack, &c) && c != '{') {
   			printf("左右括号配对次序不正确!\n");			return;		}		else if ((exp[i] == ')') || (exp[i] == ']') || (exp[i] == '}') && !StackNotEmpty(myStack)) {
   			printf("右括号多于左括号!\n");			return;		}		}	if (StackNotEmpty(myStack)) {
   //字符数组遍历完时堆栈不空，则左括号多于右括号		printf("左括号多于右括号!\n");		return;	}	else {
   		printf("**左右括号配对成功**\n");	}}
   

源文件:

#include
   
    #include
    
     #include
     
      typedef char Elemtype;#include"stack.h"int main() {
   	int n;//字符数组大小	printf("请输入字符数组大小\n");	scanf("%d",&n);	char *a;	a = (char *)calloc(n, sizeof(char));//为动态数组申请n个char类型的空间	getchar();	printf("请输入字符数组的内容\n");	for (int i = 0; i < n; i++) {
   		scanf("%c", &a[i]);	}	printf("\n");	bracket(a,n);	system("pause");	return 0;}
     
    
   

四、测试结果

转载地址：http://ynzzi.baihongyu.com/