题解 | #有效括号序列#

// 链式存储实现的栈
#include <cstddef>
#include <cstdlib>
typedef struct LNode {
    char data;
    struct LNode* next;
}* LinkStack, LNode;

// 初始化链栈
bool InitStack(LinkStack& S) {
    // 分配一个头结点
    S = (LNode*)malloc(sizeof(LNode));
    // 内存不够初始化失败
    if (S == NULL) return false;
    // 头结点指向空
    S->next = NULL;
    return true;
}

// 链栈判空
bool StackEmpty(LinkStack S) {
    return S->next == NULL;
}

// 入栈
bool Push(LinkStack& S, char x) {
    // 分配一个结点
    LNode* L = (LNode*)malloc(sizeof(LNode));
    // 内存不够
    if (L == NULL)return false;
    L->data = x;
    // 头结点后没有结点时
    if (S->next == NULL) {
        L->next = NULL;
        S->next = L;
    } else {
        L->next = S->next;
        S->next = L;
    }
    return true;
}

// 出栈
bool Pop(LinkStack& S, char& x) {
    // 判断栈空
    if (StackEmpty(S))return false;
    LNode* n = S->next;
    x = n->data;
    S->next = n->next;
    free(n);
    return true;
}

bool Destroy(LinkStack& S) {
    return true;
}

// 括号匹配
bool bracketCheck(const char* str, int length) {
    // 创建链栈
    LinkStack S;
    InitStack(S);
    // 遍历处理括号
    for (int i = 0; i < length; i++) {
        // 是否是左括号
        if (str[i] == '(' || str[i] == '[' || str[i] == '{') {
            // 是, 入栈
            Push(S, str[i]);
        } else {
            // 是右括号, 检查右括号单身
            if (StackEmpty(S))return false;
            // 检查括号匹配
            char topElem;
            Pop(S, topElem);
            if (str[i] == ')' && topElem != '(')return false;
            if (str[i] == ']' && topElem != '[')return false;
            if (str[i] == '}' && topElem != '{')return false;
        }
    }
    // 如果处理完括号序列, 发现栈非空, 则左括号单身
    return StackEmpty(S);
}
    class Solution {
      public:
        /**
         * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
         *
         *
         * @param s string字符串
         * @return bool布尔型
         */
        bool isValid(string s) {
            // write code here
            if (bracketCheck(s.c_str(), s.length())) {
                return true;
            }
            return false; ;

        }
    };