题解 | #有效括号序列#

#define MaxSize 10000
typedef struct {
    char data[MaxSize];
    int top;
} SqStack;

// 初始化栈
void InitStack(SqStack& S) {
    S.top = -1;
}

// 判断栈是否为空
bool StackEmpty(SqStack& S) {
    if (S.top == -1)return true;
    return false;
}

// 新元素入栈
bool Push(SqStack& S, char x) {
    if (S.top >= MaxSize) {
        return false;
    }
    S.data[++S.top] = x;
    return true;
}

// 栈顶元素出栈， 用x返回
bool Pop(SqStack& S, char& x) {
    if (StackEmpty(S)) return false;
    x = S.data[S.top--];
    return true;
}

// 括号匹配
bool bracketCheck(const char str[], int length) {
    // 声明一个顺序栈S， 静态分配内存空间
    SqStack S;
    // 初始化栈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; ;

    }
};