有效的括号

20. 有效的括号 - 力扣（LeetCode） (leetcode-cn.com)

思路：是左括号，就入栈，是右括号，就与栈顶的左括号判断是否匹配，如果匹配，继续，不匹配就终止。

从第79行开始，前面都是实现栈以及其功能接口。

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
typedef char StackDataType;
typedef struct Stack
{
    StackDataType* arry;
    int top;//指向栈顶
    int capacity;//栈的容量——能放几个数据
}Stack;
//初始化
void StackInit(Stack* ps)
{
    assert(ps);
    ps->arry = (StackDataType*)malloc(sizeof(StackDataType)*4);
    if (ps->arry == NULL)
    {
        printf("malloc fail");
        exit(-1);
    }
    ps->capacity = 4;
    ps->top = 0;
}
//销毁
void StackDestory(Stack* ps)
{
    assert(ps);
    free(ps->arry);
    ps->arry = NULL;
    ps->top = ps->capacity =0 ;
}
//入栈
void StackPush(Stack* ps, StackDataType x)
{
    assert(ps);
    //满了
    if (ps->top == ps->capacity)
    {
        StackDataType* tmp = (StackDataType*)realloc(ps->arry, ps->capacity * 2 * sizeof(StackDataType));
        if (tmp == NULL)
        {
            printf("realloc fail");
            exit(-1);
        }
        else
        {
            ps->arry = tmp;
            ps->capacity *= 2;
        }
    }
    ps->arry[ps->top] = x;
    ps->top++;
} 

//出栈
void StackPop(Stack* ps)
{
    assert(ps);
    //如果栈空了调用top，直接终止程序报错
    assert(ps->top > 0);
    ps->top--;
}
//返回栈顶元素
StackDataType StackTop(Stack* ps)
{
    assert(ps);
    assert(ps->top > 0);
    return ps->arry[ps->top - 1];
}
//返回栈中元素个数
int StackSize(Stack* ps)
{
    assert(ps);
    return ps->top;
}
//是否为空
bool StackEmpty(Stack* ps)
{
    assert(ps);
    return ps->top == 0;//真为空，假为非空。
}
///////////////////////////////////////////////////////////////////
bool isValid(char * s){
    Stack  st;
    StackInit(&st);
    while(*s != '\0')
    {
        switch(*s)
        {
            case '{':
            case '[':
            case '(':
            {
                StackPush(&st,*s);
                s++;
                break;
            }
            case '}':
            case ']':
            case ')':
            {
                if(StackEmpty(&st))
                {
                    StackDestory(&st);
                    return false;
                }

                char top = StackTop(&st);
                StackPop(&st);

                //不匹配的三种情况  
                if((*s == '}'&& top != '{')
                || (*s == ']'&& top != '[')
                || (*s == ')'&& top != '('))
                {
                  //不匹配返回fasle，有可能栈里面还有元素，销毁防止内存泄漏
                    StackDestory(&st);
                    return false;
                }
                else
                {
                    //匹配就继续匹配
                    s++;   
                }
                break;
            }
            default:
                break;
        }
    }
    bool ret = StackEmpty(&st);//匹配完成了，栈应该是空的。
    StackDestory(&st);
    return ret;
}