20.有效的括号-力扣（LeetCode）

题目：

解题思路：

        首先要明确一个问题：配对的左右括号不一定是相邻的，例如： ( [ ] ) 。

        由上述，'（'，'['，'{' 可能不会在遍历整个字符串的过程中，立即找到配对的括号。括号的配对原则是：当遍历到右括号时去看后出现的左括号是否与之配对，那么很容易想到满足后进先出的特点的结构为栈。

        首先定义一个栈的结构体，为栈和栈的存储空间（根据题目中的提示，存储空间定义足够大）以malloc申请空间并进行初始化。遍历整个字符串，当遇到左括号时，进行入栈操作，当遇到右括号时，进行出栈操作（主要出栈前进行判空操作，防止非法访问空间地址）。遍历完成后，栈中如果还有剩余元素，证明左括号多于右括号，返回false。

        不满足有效括号规则的情况：

        1、当传入字符串长度为奇数时，一定不满足有效括号的规则，返回false。

        2、当遍历到右括号，发现栈为空，已经没有左括号与之配对，返回false。

        3、当遍历到右括号，发现栈顶元素不能与之配对，返回false。

        4、遍历完整个字符串以后，栈中如果还有剩余元素，证明左括号多于右括号，返回false。

代码：

typedef struct
{
    char *data;//栈的存储空间
    int count;//栈中元素数量
    int top;//栈顶
}stack;
bool isValid(char *s)
{
    if(strlen(s) == 0)
        return true;
    if(strlen(s) % 2 == 1)
        return false;
    stack *sta = (stack *)malloc(sizeof(stack));//创建栈
    sta->count = 0;
    sta->top = -1;
    sta->data = (char *)malloc(sizeof(char) * 10000);//初始化栈
    while(*s)
    {
        if(*s == '(' || *s == '[' || *s == '{')
        {
            sta->data[sta->top+1] = *s;//入栈
            sta->top++;
            sta->count++;
        }
        if(*s == ')')
        {
            if(sta->top == -1) 
                return false;//判空
            if(sta->data[sta->top] == '(')
            {
                sta->top--;//出栈
                sta->count--;
            }
            else
                return false;
        }
        if(*s == ']')
        {
            if(sta->top == -1) 
                return false;//判空
            if(sta->data[sta->top] == '[')
            {
                sta->top--;//出栈
                sta->count--;
            }
            else
                return false;
        }
        if(*s == '}')
        {
            if(sta->top == -1) 
                return false;//判空
            if(sta->data[sta->top] == '{')
            {
                sta->top--;//出栈
                sta->count--;
            }
            else
                return false;
        }
        s++;
    }
    if(sta->count != 0)
        return false;
    else
        return true;
}