大家好，我是安然无虞。

每篇前言

博客主页：安然无虞

作者认证：2021年博客新星Top2

咱的口号：🌹小比特，大梦想🌹

作者请求：由于博主水平有限，难免会有错误和不准之处，我也非常渴望知道这些错误，恳请铁汁批评斧正。

火爆专栏：蓝桥杯基础算法剖析

欢迎加入：比特社区

面试题：有效的括号

原题链接：有效的括号
题目描述：
示例：

解题思路

这道题目其实就是考察我们对于栈这个数据结构的认识，属于简单题，不过这里我用C语言来实现，而不是使用C++的STL，看看用C如何该如何解答类似的题目。

代码执行

typedef char STDataType;

typedef struct Stack
{
	STDataType* a;
	int top;//栈顶
	int capacity;//容量
}Stack;

void StackInit(Stack* ps);
// 入栈
void StackPush(Stack* ps, STDataType data);
// 出栈
void StackPop(Stack* ps);
// 获取栈顶元素
STDataType StackTop(Stack* ps);
// 获取栈中有效元素个数
int StackSize(Stack* ps);
// 检测栈是否为空，如果为空返回非零结果，如果不为空返回0 
int StackEmpty(Stack* ps);
// 销毁栈
void StackDestroy(Stack* ps);


//初始化
void StackInit(Stack* ps)
{
	assert(ps);
	ps->a = NULL;
	ps->top = 0;//特别注意：top初始化成0和-1的区别
	ps->capacity = 0;
}

// 销毁栈
void StackDestroy(Stack* ps)
{
	assert(ps);
	free(ps->a);
	ps->a = NULL;
	ps->top = ps->capacity = 0;
}

// 入栈
void StackPush(Stack* ps, STDataType data)
{
	assert(ps);
	//检查是否需要扩容
	if (ps->top == ps->capacity)
	{
		int newCapacity = ps->capacity == 0 ? 4 : 2 * ps->capacity;
		STDataType* tmp = (STDataType*)realloc(ps->a, sizeof(STDataType) * newCapacity);
		if (tmp == NULL)
		{
			printf("realloc fail\n");
			exit(-1);
		}
		else
		{
			ps->a = tmp;
			ps->capacity = newCapacity;
		}
	}
	ps->a[ps->top] = data;
	ps->top++;

}
// 出栈
void StackPop(Stack* ps)
{
	assert(ps);
	assert(ps->top > 0);
	//printf("%d ", ps->a[ps->top - 1]);
	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);
	return ps->top == 0;
}

bool isValid(char * s){
   Stack st;
   StackInit(&st);
   while(*s)
   {
       //左括号，入栈
       if(*s == '[' || *s == '(' || *s == '{')
       {
           StackPush(&st, *s);
           s++;
       }
       //右括号，出栈，进行匹配，不匹配就报错
       else
       {
           if(StackEmpty(&st))
           {
               StackDestroy(&st);
               return false;
           }
           char top = StackTop(&st);
           StackPop(&st);
           if((top == '(' && *s != ')')
           ||(top == '[' && *s != ']')
           ||(top == '{' && *s != '}'))
           {
               StackDestroy(&st);//注意哦，在返回之前，要销毁栈，防止造成内存泄漏
               return false;
           }
           else
           {
               s++;
           }
           
       }
   }
  
   //判断特殊情况,如果栈不空，说明栈里面剩有左括号
   // if(StackEmpty(&st))
   // {
   //     StackDestroy(&st);
   //     return true;
   // }
   // else
   // {
   //     StackDestroy(&st);
   //     return false;
   // }

   //可简化
   bool ret = StackEmpty(&st);
   StackDestroy(&st);
   return ret;
}

   

  

   
  
  

   
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
   
145
   
146
   
147
  

之所以特意加上这道题目，为的就是说明用C语言的一部分缺陷，需要自己造轮子，远远没有面向对象语言用起来舒服，使用C++语言，只需要四五十行代码即可，在实现后面高阶数据结构时，C语言是不行的。不过你可能有疑问，为什么不包含头文件，因为这是接口型题目，可认为系统会自动给我们包含上。
完整代码：

三、遇见安然遇见你，不负代码不负卿。

码字不易，求个三连。

文章来源: bit-runout.blog.csdn.net，作者：安然无虞，版权归原作者所有，如需转载，请联系作者。

原文链接：bit-runout.blog.csdn.net/article/details/123785593