【数据结构】用栈实现括号匹配-Toy模板网

这篇具有很好参考价值的文章主要介绍了【数据结构】用栈实现括号匹配。希望对大家有所帮助。如果存在错误或未考虑完全的地方，请大家不吝赐教，您也可以点击"举报违法"按钮提交疑问。

用栈实现括号匹配

实现思路

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;
}