带你一步实现《栈》（括号匹配问题）

栈的结构及概念

栈是一种特殊的线性表，只允许在固定的一端插入或删除数据，进行插入和删除的一端被称为栈顶，另一端称为栈底。栈中的数据遵循后进先出原则
LIFO（LAST IN FIRST OUT)

• 俗称栈的插入过程叫做压栈，入栈，从栈顶入数据
• 出栈就是栈的删除，出数据也在栈顶哦，不然怎么做到后进先出原则。
  来看一个动态图理解入栈出栈的过程。
  
  接下来首先要进行分析，由于是后进先出，如果用链表来实现的话，相比数组的尾删和尾插，用链表实现更加麻烦一点，如果用数组来实现，尾删只需要size减一，如果需要入栈的话只需要在末尾的位置添加这个数就可以了。

一步一步来实现他

//静态的
//#define N 10
//struct stack
//{
//	int  a[N];
//	int top;
//};

typedef int TYPE;
typedef struct Stack
{
	TYPE* a; 	
	TYPE top;
	int capacity;
}ST;
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15

如果还是用静态的数组就太低端了，而且还会遇到容量不够的问题,因为要储存的值的类型有可能会发生变化，所以可以将变量类型定义一下，需要修改时不至于要修改很多地方。

• 定义一个数组，top是栈内储存的数据的量，capacity是数组的容量，如果存储的数据的量等于容量就要用malloc函数进行扩容，大体思路就是如此了。

进入正题

• 仍然利用分文件的形式来实现，以下栈的功能全部放在STACK.c中
  初始化函数

void STInit(ST* ps)
{
	assert(ps);
	ps->a = NULL;
	ps->capacity = 0;
	ps->top = 0;
}
1
2
3
4
5
6
7

判断创建的结构体指针变量是否为空assert
将ps指向的数组先置空，然后将容量capacity设置为0，数据量设置为0。
判空函数

bool STEmpty(ST* ps)
{
	assert(ps);
	return ps->top == 0;
}
1
2
3
4
5

还是要检查ps是否有问题，返回一个bool变量，判断是false还是true，如果等于0，就返回true，说明栈内为空。
求栈内元素个数

int STSize(ST* ps)
{
	assert(ps);
	return ps->top;
}
1
2
3
4
5

这个很简单，只需要返回top的值即可。
删除元素
这个很很简单相较于用链表实现

void STPop(ST* ps)
{
	assert(ps);
	assert(ps->top > 0);
	ps->top--;
}
1
2
3
4
5
6

即可，当然如果ps指向的top已经是0了就不能再删除了。
添加元素

void STPush(ST* ps, TYPE x)
{
	assert(ps);
	if (ps->top == ps->capacity)
	{
		//ps->capacity *= 2;//当capacity等于零时不好用
		int newcapacity = ps->capacity == 0 ? 4 : ps->capacity * 2;
		TYPE* tmp = (TYPE*)realloc(ps->a, sizeof(TYPE) * newcapacity);//判断是否扩容成功
		if (tmp == NULL)
		{
			perror("realloc fail");
		}
		ps->a = tmp;
		ps->capacity = newcapacity;
	}
	ps->a[ps->top] = x;
	ps->top++;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18

• 传入一个x，首先来判断容量是否为零，如果容量为零的话，那就申请4个空间的内存，然后先存放数据，存放完数据会使数据量top加一，如果top和数据的容量相等时，那就扩充容量为原来的二倍。将x放进该位置，入栈的过程就结束啦。
  销毁栈

void STDestroy(ST* ps)
{
	assert(ps);
	free(ps->a);
	ps->a = NULL;
	ps->top = ps->capacity = 0;
}
1
2
3
4
5
6
7

判断必不可少，因为内存是malloc过来的，要用free函数将其释放掉，然后恢复到初始化函数时的状态。将容量还有数量全部还原为零。
获取栈顶元素

TYPE STTop(ST* ps) 
{
	assert(ps);
	assert(ps->top > 0);
	return ps->a[ps->top - 1];
}
1
2
3
4
5
6

判断栈内到底有没有元素，这是很重要的，不然会越界访问，然后返回入栈的数量减一下标的元素即可，为什么减一呢，第一个元素，下标为零，懂了吧！
别忘记在STACK.h中声明这几个函数

void STInit(ST* ps);
void STDestroy(ST* ps);
//入栈
void STPush(ST* ps,TYPE x);
//出栈
void STPop(ST* ps);

int STSize(ST* ps);

bool STEmpty(ST* ps);

//获取栈顶元素
TYPE STTop(ST* ps);
1
2
3
4
5
6
7
8
9
10
11
12
13

来测试一波
test.c

#define _CRT_SECURE_NO_WARNINGS
#include "stack.h"
#include 
Test1()
{
	ST st;
	STInit(&st);
	STPush(&st, 1);
	STPush(&st, 2);
	STPush(&st, 3);
	STPush(&st, 4);
	STPush(&st, 5);

	while (!STEmpty(&st))
	{
		printf("%d ", STTop(&st));
		STPop(&st);
	}
	printf("\n");
	STDestroy(&st);
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21

运行后如图

如果有想测验一下的，下边就是代码

Test1()
{
	ST st;
	STInit(&st);
	STPush(&st, 1);
	STPush(&st, 2);
	STPush(&st, 3);
	STPush(&st, 4);
	STPush(&st, 5);

	while (!STEmpty(&st))
	{
		printf("%d ", STTop(&st));
		STPop(&st);
	}
	printf("\n");
	STDestroy(&st);
}

int main()
{
	Test1();
	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

学习完了栈的定义及实现，上一个重头戏
题目：括号的匹配

这道题实现起来很不简单，如果没有学习栈相关的知识，我们在判断时会遇到很多阻力，这道题也可以叫做括号的匹配。例如

• ( { } )这组括号就是可以匹配的。
• ( [ ] ) { } ( )还有像这种。
• ( [ ( ) } ) 然而这组中明显匹配有问题，然而我们怎么来找呢？
  如果用字符数组的话，会有很多情况需要判断，而且很容易出错，现在我们来尝试利用栈的特性来解决这一问题。

---

分析题目要求，仔细分析可以发现，在利用括号开始进行匹配时，如果是右括号（统称）那就入栈，如果是左括号，那就从栈中取出一个元素与其相匹配，如果匹配成功，那就继续向后匹配，如果匹配失败，那就直接返回，并标明匹配错误。
拿出一个测试用例进行解释

接下来解决逻辑问题
首先，因为我们需要用到栈，可以将上边所讲的栈的实现函数全部复制粘贴进去，然后利用栈的特性来实现大体逻辑。
代码如下

bool isValid(char * s){
    ST st;
    STInit(&st);
    char top;
    while(*s)
    {
        if((*s=='[')||(*s=='(')||(*s=='{'))
        {
            STPush(&st,*s);           
        }
        if(*s==')')
        {
            if(STEmpty(&st))
            {
                return false;
            }
            top=STTop(&st);
            STPop(&st);
            if(top!='(')
            {
                return false;
                STDestroy(&st);
            }
        }
        if(*s=='}')
        {
            if(STEmpty(&st))
            {
                return false;
            }
            top=STTop(&st);
            STPop(&st);
            if(top!='{')
            {
                return false;
                STDestroy(&st);
            }
        }
        if(*s==']')
        {
            if(STEmpty(&st))
            {
                return false;
            }
            top=STTop(&st);
            STPop(&st);
            if(top!='[')
            {
                return false;
                STDestroy(&st);
            }
        }        
        s++;
    }
    bool ret=STEmpty(&st);
    STDestroy(&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

创建一个结构体指针变量，这里要注意，上边所写的默认是整型数组，将设置的TYPE改成char类型即可。
在循环体中，我们可以选择使用switch case语句，也可以用if else 语句，代码逻辑十分清晰，在遍历数组的过程中，如果是右括号，则直接入栈，如果是左括号，就出栈顶元素与其相匹配，匹配成功，则走到循环体最后s++的位置，进行下一次判断。

也要注意数组是否为空，可以使用判空函数，如果为空就返回true，如果不为空就返回false，如果是空的话，相当于经历循环体后已经没有左括号了，但是如果不为空的话，那就相当于数组中还剩下一些括号，这些括号是没有被匹配的。

例如

{}()[]{{{

经历过循环后，前边的三组已经匹配完成了，然而后边还有三个右括号入栈，这三个括号没有匹配，所以用判空函数判断一下，如果循环之后栈不为空的话，那就说明匹配不成功，返回false。
需要注意的是取出栈顶元素后将栈顶元素删除。
全部代码如下

typedef char STDataType;
typedef struct Stack
{
	STDataType* a;
	STDataType top;
	int capacity;
}ST;
void STInit(ST* ps)
{
	assert(ps);
	ps->a = NULL;
	ps->capacity = 0;
	ps->top = 0;
}

void STDestroy(ST* ps)
{
	assert(ps);

	free(ps->a);
	ps->a = NULL;
	ps->top = ps->capacity = 0;
}
void STPush(ST* ps, STDataType x)
{
	assert(ps);
	// 11:40
	if (ps->top == ps->capacity)
	{
		int newCapacity = ps->capacity == 0 ? 4 : ps->capacity * 2;
		STDataType* tmp = (STDataType*)realloc(ps->a, sizeof(STDataType) * newCapacity);
		if (tmp == NULL)
		{
			perror("realloc fail");
			exit(-1);
		}

		ps->a = tmp;
		ps->capacity = newCapacity;
	}

	ps->a[ps->top] = x;
	ps->top++;
}
void STPop(ST* ps)
{
	assert(ps);
	assert(ps->top > 0);

	--ps->top;
}
STDataType STTop(ST* ps)
{
	assert(ps);

	// 
	assert(ps->top > 0);

	return ps->a[ps->top - 1];
}
int STSize(ST* ps)
{
	assert(ps);

	return ps->top;
}

bool STEmpty(ST* ps)
{
	assert(ps);

	return ps->top == 0;
}
// bool isValid(char * s)
// {

// }

bool isValid(char * s){
    ST st;
    STInit(&st);
    char top;
    while(*s)
    {
        if((*s=='[')||(*s=='(')||(*s=='{'))
        {
            STPush(&st,*s);           
        }
        if(*s==')')
        {
            if(STEmpty(&st))
            {
                return false;
            }
            top=STTop(&st);
            STPop(&st);
            if(top!='(')
            {
                return false;
                STDestroy(&st);
            }
        }
        if(*s=='}')
        {
            if(STEmpty(&st))
            {
                return false;
            }
            top=STTop(&st);
            STPop(&st);
            if(top!='{')
            {
                return false;
                STDestroy(&st);
            }
        }
        if(*s==']')
        {
            if(STEmpty(&st))
            {
                return false;
            }
            top=STTop(&st);
            STPop(&st);
            if(top!='[')
            {
                return false;
                STDestroy(&st);
            }
        }        
        s++;
    }
    bool ret=STEmpty(&st);
    STDestroy(&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

7777777,加油！