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

1.题目

括号匹配

给定一个只包括 ‘(’，‘)’，‘{’，‘}’，‘[’，‘]’ 的字符串 s ，判断字符串是否有效。

有效字符串需满足：

左括号必须用相同类型的右括号闭合。
左括号必须以正确的顺序闭合。
每个右括号都有一个对应的相同类型的左括号。

示例 1：

输入：s = "()"
输出：true
1
2

示例 2：

输入：s = "()[]{}"
输出：true
1
2

示例 3：

输入：s = "(]"
输出：false
1
2

2. 思路

有人肯定就想，我记录 ‘（ ’ 的个数与 ‘）’ 的个数，最后将它们比较如果相等就是匹配，不相等就是不匹配。其他两种括号一样的方法。

这种方法是不可以的

举个例子：

“ (({))} ”这种括号便不匹配，但是符合个数相等

有人就觉得这个，好难实现，不会写了。

可以用栈来实现这个是比较好的选择

用栈来实现括号匹配问题

这样就完了吗？

如果第一个是 ‘ ] ’ 或者 ‘ ）’或者 ‘ }’呢？

栈中没有数据怎么办呢？

所以每次要出栈时先要检查是否为NULL,如果为NULL就返回false

3.代码实现

#include
#include
#include
#include

// 支持动态增长的栈
typedef char STDataType;
typedef struct Stack
{
	STDataType* a;
	int top; // 栈顶
	int capacity; // 容量
}Stack;
// 初始化栈
void StackInit(Stack* ps)
{
	//判断指针是否为NULL
	assert(ps);

	//初始化，这里初始化是可以给a分配空间也可以不分配，看自己吧
	//不分配
	ps->a = NULL;
	ps->capacity = ps->top = 0;

	//分配空间
	/*ps->a = (STDataType*)malloc(sizeof(STDataType) * 4);
	ps->capacity = 4;
	ps->top = 0;*/
}
// 入栈
void StackPush(Stack* ps, STDataType data)
{
	assert(ps);

	//先判断栈是否能放下数据
	//不能放下就扩容
	if (ps->capacity == ps->top)
	{
		ps->capacity = ps->capacity == 0 ? 4 : ps->capacity * 2;
		STDataType* tmp = (STDataType*)realloc(ps->a, sizeof(STDataType) * ps->capacity);
		if (tmp == NULL)
		{
			perror("realloc:");
			exit(-1);
		}

		//成功开辟
		ps->a = tmp;
	}

	ps->a[ps->top] = data;
	ps->top++;
}
// 出栈
void StackPop(Stack* ps)
{
	assert(ps);
	//判断栈中是否有数据
	assert(ps->top != 0);

	//有数据
	//出数据，也就是顺序表的尾删
	ps->top--;
}
// 获取栈顶元素
STDataType StackTop(Stack* ps)
{
	assert(ps);
	//要获取栈顶元素，先要保证有元素
	assert(ps->top != 0);

	//有数据
	//栈顶的元素就是数组最后一个元素

	return ps->a[ps->top - 1];
}
// 获取栈中有效元素个数
int StackSize(Stack* ps)
{
	assert(ps);

	return ps->top;
}
// 检测栈是否为空，如果为空返回非零结果，如果不为空返回0
int StackEmpty(Stack* ps)
{
	assert(ps);

	//如果ps->top等于0则返回1代表为空
	//如果不相等返回0代表为假
	return ps->top == 0;
}
// 销毁栈
void StackDestroy(Stack* ps)
{
	assert(ps);

	free(ps->a);
	ps->a = NULL;
	ps->capacity = ps->top = 0;
}

bool isValid(char* s)
{
	Stack st;
	StackInit(&st);
	while (*s)
	{
		if (*s == '(' || *s == '[' || *s == '{')
		{
			StackPush(&st, *s);
		}
		else
		{
			if (StackEmpty(&st))
			{
				return false;
			}
			char ret = StackTop(&st);
			StackPop(&st);
			if ((*s == ')' && ret == '(') || (*s == '}' && ret == '{')
				|| (*s == ']' && ret == '['))
			{

			}
			else
			{
				return false;
			}

		}
		s++;
	}

	if (StackEmpty(&st))
	{
		return true;
	}

	return false;

}

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
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144

4.总结

只不过C语言写这个比较麻烦，写一道题还要先写一个数据结构😄

== ‘[’))
{

		}
		else
		{
			return false;
		}

	}
	s++;
}

if (StackEmpty(&st))
{
	return true;
}

return false;
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16

}

# 4.总结

只不过C语言写这个比较麻烦，写一道题还要先写一个数据结构:smile:

重点是思路。
1
2
3
4
5
6