【力扣】括号匹配

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

题目：

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

有效字符串需满足：

左括号必须用相同类型的右括号闭合。
左括号必须以正确的顺序闭合。

思路：

利用栈后进先出的特性

代码：

typedef struct Stack
{
    char* c;
    int top;
    int capacity;
}Stack;
void StackInit(Stack* ps)
{
    ps->top = 0;
    ps->c = NULL;
    ps->capacity = 0;
}
void StackPush(Stack* ps, char c)
{
    if (ps->capacity == ps->top)
    {
        int newCapacity = ps->capacity == 0 ? 4 : ps->capacity * 2;
        char* temp = (char*)realloc(ps->c,sizeof(char) * newCapacity);
        if (!temp)
        {
            exit(-1);
        }
        ps->c = temp;
        ps->capacity = newCapacity;
    }

    ps->c[ps->top++] = c;
}
void StackPop(Stack* ps)
{
    ps->top--;
}
char StackTop(Stack* ps)
{
    return ps->c[ps->top - 1];
}
bool isValid(char* s)
{
    char c = 0;
    Stack stack;
    StackInit(&stack);
    while (*s)
    {
        if (*s == '(' || *s == '{' || *s == '[')
        {
            StackPush(&stack, *s);
        }
        else
        {
            if (stack.top == 0)
            {
                return false;
            }
            if (*s == ')')
            {
                c = StackTop(&stack);
                if (c != '(')
                {
                    return false;
                }
                StackPop(&stack);
            }
            else if (*s == ']')
            {
                c = StackTop(&stack);
                if (c != '[')
                {
                    return false;
                }
                StackPop(&stack);
            }
            else if (*s == '}')
            {
                c = StackTop(&stack);
                if (c != '{')
                {
                    return false;
                }
                StackPop(&stack);
            }
        }


        s++;
    }
    if (stack.top == 0)
    {
        return true;
    }
    return false;
}