题解 | #有效括号序列#

/**
 * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
 *
 *
 * @param s string字符串
 * @return bool布尔型
 */

#pragma once
#include <assert.h>
#include <stdio.h>
#include <stdlib.h>
typedef char STDataType;
typedef struct Stack {
    STDataType* _a; // 首元素的地址
    int _top; // 栈顶，初始化为0，也就是等同于size，初始化为-1，等同于下标
    int _capacity; // 容量
} Stack;
// 初始化栈
void StackInit(Stack* ps);
// 销毁栈
void StackDestroy(Stack* ps);
// 入栈
void StackPush(Stack* ps, STDataType data);
// 出栈
void StackPop(Stack* ps);
// 获取栈顶元素
STDataType StackTop(Stack* ps);
// 获取栈中有效元素个数
int StackSize(Stack* ps);
// 检测栈是否为空，如果为空返回非零结果，如果不为空返回0
int StackEmpty(Stack* ps);
// 初始化栈
void StackInit(Stack* ps) {
    ps->_a = NULL;

    // 这里栈顶初始化为-1和初始化为0是不一样的
    //    0 0 0 0 0 0 0 0 数组
    // -1 0 0 0 0 0 0 0 0 初始化为-1
    //    0 0 0 0 0 0 0 0 初始化为0
    // 初始化为0，也就是等同于size，初始化为-1，等同于下标
    ps->_capacity = ps->_top = 0;
}
// 销毁栈
void StackDestroy(Stack* ps) {
    // 判断为不为空，判断里面有没有数值
    assert(ps && ps->_top);
    free(ps->_a);
    ps->_capacity = ps->_top = 0;
}
// 入栈
void StackPush(Stack* ps, STDataType data) {
    // 首先判断容量是多少，然后进行扩容
    if (ps->_capacity == ps->_top) {
        // 扩容
        int newapacity = ps->_capacity == 0 ? 4 : 2 * ps->_capacity;
        STDataType* tmp =
            (STDataType*)realloc(ps->_a, newapacity * sizeof(STDataType));
        if (tmp == NULL) {
            perror("StackPush:tmp:error:");
            exit(1);
        }
        // 改变容量大小，指向新空间的头第一个元素位置的地址
        ps->_capacity = newapacity;
        ps->_a = tmp;
    }
    // 插入数值
    ps->_a[ps->_top] = data;
    ps->_top++;
}
// 出栈
void StackPop(Stack* ps) {
    // 判断为不为空，判断里面有没有数值
    assert(ps && ps->_top);
    ps->_top--;
}
// 获取栈顶元素
STDataType StackTop(Stack* ps) {
    assert(ps && ps->_top);
    return ps->_a[ps->_top - 1];
}
// 获取栈中有效元素个数
int StackSize(Stack* ps) {
    assert(ps && ps->_top);
    return ps->_top - 1;
}
// 检测栈是否为空，如果为空返回非零结果(1)，如果不为空返回0
int StackEmpty(Stack* ps) {
    assert(ps);
    return ps->_top == 0;
    // 所以，ps->_top == 0 这个表达式的作用是比较栈顶位置 ps->_top 是否等于 0。
    // 如果相等，说明栈为空，表达式结果为 true（在C语言中用 1 表示）；
    // 如果不相等，说明栈不为空，表达式结果为 false（在C语言中用 0 表示）
}
bool isValid(char* s ) {
    Stack ps;
    StackInit(&ps);
    while (*s) {
        if (*s == '(' || *s == '[' || *s == '{') {
            StackPush(&ps, *s);
        }
        if (*s == ')' || *s == ']' || *s == '}') {
            //栈是空的，但是左括号还有，匹配不上
            if (StackEmpty(&ps)) {
                return false;
            }
            int ret = StackTop(&ps);
            StackPop(&ps);
            if (*s == ')' && ret != '(' || *s == ']' && ret != '[' || *s == '}' &&
                    ret != '{') {
                return false;
            }
        }
        s++;
    }
    //栈不为空，说明左括号没有匹配完毕
    if (!StackEmpty(&ps)) {
        return false;
    }
    return true;
}

解析我放这里，点击链接直接观看

https://blog.csdn.net/Jason_from_China/article/details/138730112