【数据结构】用栈实现括号匹配

用栈实现括号匹配

实现思路

  • 1.创立一个判断括号是否匹配的函数BracketsCheck
  • 2.传参(栈,输入的字符串)
  • 3.对字符串中的(、[、{、这三种括号进行匹配
  • 4.顺序从左往右进行,依次将符合条件的括号放入栈中,满足FILO原则
  • 5.但拿到右括号时进行匹配,如果匹配成功,那么就出栈,如果失败就返回false

栈的基本功能实现

  • 定义一个顺序栈
typedef struct {
	char data[MAXSIZE];
	int top;
}Sqstack;
  • 定义一个初始化函数
void InitSqstack(Sqstack& s)
{
	s.top = -1;
}
  • 定义一个判断栈是否为空的函数
bool StackEmpty(Sqstack& s)
{
	if (s.top == -1)
		return true;
	else
		return false;
}
  • 定义一个入栈的函数
bool PushSqstack(Sqstack& s,char x)
{
	if (s.top == MAXSIZE - 1)
		return false;
	s.data[++s.top] = x;
	return true;
}
  • 定义一个出栈的函数
bool PopSqstack(Sqstack& s,char& x)
{
	if (s.top == -1)
		return false;
	x = s.data[s.top--];
	return true;
}

判断括号是否匹配的函数(重点)

定义成bool类型的函数,通过返回值来判断是否匹配,其中运用for循环来对字符串来遍历,对里面的字符一一进行判断,通过栈的后入先出的特点,来进行左右符号的匹配

bool BracketsCheck(Sqstack& s, char str[])
{
	for(int i=0;str[i] != '\0'; i++)
	{
		if (str[i] == '(' || str[i] == '[' || str[i] == '{')
			PushSqstack(s, str[i]);
		else
		{
			char element;
			PopSqstack(s, element);
			if (str[i] == ')' && element != '(')
				return false;
			if (str[i] == ']' && element != '[')
				return false;
			if (str[i] == '}' && element != '}')
				return false;
		}
	}
	return StackEmpty(s);
}

源代码

#define _CRT_SECURE_NO_WARNINGS
#include<stdio.h>
#define MAXSIZE 50

typedef struct {
	char data[MAXSIZE];
	int top;
}Sqstack;

void InitSqstack(Sqstack& s)
{
	s.top = -1;
}

bool StackEmpty(Sqstack& s)
{
	if (s.top == -1)
		return true;
	else
		return false;
}

bool PushSqstack(Sqstack& s,char x)
{
	if (s.top == MAXSIZE - 1)
		return false;
	s.data[++s.top] = x;
	return true;
}

bool PopSqstack(Sqstack& s,char& x)
{
	if (s.top == -1)
		return false;
	x = s.data[s.top--];
	return true;
}

/*
* 1.创立一个判断括号是否匹配的函数BracketsCheck
* 2.传参(栈,输入的字符串)
* 3.对字符串中的(、[、{、这三种括号进行匹配
* 4.顺序从左往右进行,依次将符合条件的括号放入栈中,满足FILO原则
* 5.但拿到右括号时进行匹配,如果匹配成功,那么就出栈,如果失败就返回false
*/

bool BracketsCheck(Sqstack& s, char str[])
{
	for(int i=0;str[i] != '\0'; i++)
	{
		if (str[i] == '(' || str[i] == '[' || str[i] == '{')
			PushSqstack(s, str[i]);
		else
		{
			char element;
			PopSqstack(s, element);
			if (str[i] == ')' && element != '(')
				return false;
			if (str[i] == ']' && element != '[')
				return false;
			if (str[i] == '}' && element != '}')
				return false;
		}
	}
	return StackEmpty(s);
}


int main()
{
	Sqstack s;
	InitSqstack(s);
	char str[MAXSIZE];
	printf("请输入一串带有括号的字符串:");
	scanf("%s", str);
	bool flag=BracketsCheck(s, str);
	printf("%d", flag);


	return 0;
}

运行结果展示

在这里插入图片描述
在这里插入图片描述

总结

如果这篇文章对你有帮助的话,可以给我点个关注,我们一起进步!文章来源地址https://www.uudwc.com/A/XkDke/

原文地址:https://blog.csdn.net/Gaara01193/article/details/133148628

本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如若转载,请注明出处: 如若内容造成侵权/违法违规/事实不符,请联系站长进行投诉反馈,一经查实,立即删除!

h
上一篇 2023年09月26日 15:13
数据结构 - 链表
下一篇 2023年09月26日 15:14