Leetcode刷题之有效的括号（C语言版）

一、题目描述

20、有效的括号

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

有效字符串需满足：

①、左括号必须用相同类型的右括号闭合。
②、左括号必须以正确的顺序闭合。
③、每个右括号都有一个对应的相同类型的左括号。
1
2
3
4
5
6
7

二、题目测试用例

三、题目分析

本题是要将左括号与右括号相匹配的进行闭合，所以我们想到采用“栈”的先进后出特性来进行数据的存放操作。所以我们先要写一个栈出来，包括栈的创建，栈的销毁等许多的基础操作。如果大家忘记了栈的相关操作如何去写，可以看我之前的文章《数据结构——栈的详细介绍》。写好栈之后，我们对于本道题的解题思路便是：
①、左括号入栈

 if(*s=='('
      ||*s=='{'
      ||*s=='[')
      {
        PushST(&st,*s);
      }
1
2
3
4
5
6

②、右括号出栈顶元素与其进行比较
这里需要注意的是如果当前只有一个任意的右括号，那么就没有可能出栈与其进行匹配操作，所以在此要对栈进行判空，保证当前栈内存在元素。如果当前栈内没有元素，便要对栈进行销毁操作，以防止内存的泄漏。

 else
      {
          //判断栈当前是否为空
          if(STEmpty(&st))
          {
            
            //注意在此需要防止内存泄漏
            //销毁栈
            DestoryST(&st);
              return false;
          }
          //判断匹配问题
          char top=TopST(&st);
          //对栈顶元素进行出栈，更新栈顶元素
          PopST(&st);
          if((*s==']'&&top!='[')
          ||(*s=='}'&&top!='{')
          ||(*s==')'&&top!='('))
          {
            //注意在此需要防止内存泄漏
            //销毁栈
            DestoryST(&st);
              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

③、返回值

 bool ret=STEmpty(&st);
1

查看当前栈内是否还存在其他的元素，如果没有则返回true,否则返回false。

四、完整代码

//定义数据类型
typedef char STDatatype;


typedef struct STack
{
	STDatatype* a;//数组
	int capacity;//容量
	int top;//栈顶元素的下一个
}ST;



//初始化
void InitST(ST* pst);
//销毁
void DestoryST(ST* pst);
//压栈
void PushST(ST* pst, STDatatype x);
//出栈
void PopST(ST* pst);
//判空
bool STEmpty(ST* pst);
//获取栈顶元素
STDatatype TopST(ST* pst);
//获取栈的size
int STSize(ST* pst);
//初始化
void InitST(ST* pst)
{
	assert(pst);
	pst->a = NULL;
	pst->capacity = 0;//栈顶元素的下一个位置
	pst->top = 0;
}
//销毁
void DestoryST(ST* pst)
{
	assert(pst);
	free(pst->a);
	pst->a = NULL;
	pst->capacity = pst->top = 0;
}
//压栈
void PushST(ST* pst, STDatatype x)
{
	if (pst->top == pst->capacity)
	{
		int newcapacity = pst->capacity == 0 ? 4 : pst->capacity * 2;
		STDatatype *tmp = (STDatatype*)realloc(pst->a, sizeof(STDatatype) * newcapacity);
		if (tmp == NULL)
		{
			perror("realloc fail");
			return;
		}
		pst->a = tmp;
		pst->capacity = newcapacity;
	}
	//插入数据
	pst->a[pst->top] = x;
	pst->top++;
}
//出栈
void PopST(ST* pst)
{
	assert(pst);
	assert(!STEmpty(pst));
	pst->top--;
}
//判空
bool STEmpty(ST* pst)
{
	assert(pst);
	return pst->top == 0;
}
//获取栈顶元素
STDatatype TopST(ST* pst)
{
	assert(pst);
	assert(!STEmpty(pst));
	return pst->a[pst->top-1];
}
//获取栈的size
int STSize(ST* pst)
{
	assert(pst);
	return pst->top;
}
bool isValid(char* s) 
{
    ST st;
    //初始化
    InitST(&st);
    //解题思路：①左括号入栈  ②右括号出栈
    while(*s)
    {
      if(*s=='('
      ||*s=='{'
      ||*s=='[')
      {
        PushST(&st,*s);
      }

      else
      {
          //判断栈当前是否为空
          if(STEmpty(&st))
          {
            
            //注意在此需要防止内存泄漏
            //销毁栈
            DestoryST(&st);
              return false;
          }
          //判断匹配问题
          char top=TopST(&st);
          //对栈顶元素进行出栈，更新栈顶元素
          PopST(&st);
          if((*s==']'&&top!='[')
          ||(*s=='}'&&top!='{')
          ||(*s==')'&&top!='('))
          {
            //注意在此需要防止内存泄漏
            //销毁栈
            DestoryST(&st);
              return false;
          }
      }
      ++s;
    }
    bool ret=STEmpty(&st);

    //销毁栈
    DestoryST(&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