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

用栈实现括号匹配

实现思路

• 1.创立一个判断括号是否匹配的函数BracketsCheck

• 2.传参（栈，输入的字符串）
• 3.对字符串中的（、[、{、这三种括号进行匹配
• 4.顺序从左往右进行，依次将符合条件的括号放入栈中，满足FILO原则
• 5.但拿到右括号时进行匹配，如果匹配成功，那么就出栈，如果失败就返回false

栈的基本功能实现

• 定义一个顺序栈

typedef struct {
	char data[MAXSIZE];
	int top;
}Sqstack;
1
2
3
4

• 定义一个初始化函数

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

• 定义一个判断栈是否为空的函数

bool StackEmpty(Sqstack& s)
{
	if (s.top == -1)
		return true;
	else
		return false;
}
1
2
3
4
5
6
7

• 定义一个入栈的函数

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

• 定义一个出栈的函数

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

判断括号是否匹配的函数（重点）

定义成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);
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20

源代码

#define _CRT_SECURE_NO_WARNINGS
#include
#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;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81

运行结果展示

总结

如果这篇文章对你有帮助的话，可以给我点个关注，我们一起进步！