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

别团等shy哥发育

发布于 2023-02-27 10:27:20

9810

发布于 2023-02-27 10:27:20

文章被收录于专栏：全栈开发那些事

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

一、问题引入:

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

二、算法思想:

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

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

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

头文件 stack.h

#pragma once
#include<windows.h>
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<stdio.h>
#include<malloc.h>
#include<stdlib.h>
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;
}