考研笔记

板子：括号匹配

左括号入栈；遇到右括号就弹出栈顶，看是不是和它配对的左括号。扫描结束时栈必须是空的。

代码

bool bracketCheck(char s[]) {                // s 以 '\0' 结尾，只检查三种括号，其他字符跳过
    char st[MaxSize];                        // 栈里存左括号
    int top = -1;
    for (int i = 0; s[i] != '\0'; i++) {
        char c = s[i];
        if (c == '(' || c == '[' || c == '{') st[++top] = c;       // 左括号：入栈，等右括号来配
        else if (c == ')' || c == ']' || c == '}') {
            if (top == -1) return false;                          // 失败①：来了右括号，栈里却没有左括号
            char l = st[top--];                                   // 弹出最近的一个左括号
            if ((c == ')' && l != '(') || (c == ']' && l != '[') || (c == '}' && l != '{'))
                return false;                                     // 失败②：括号类型对不上
        }
    }
    return top == -1;                                             // 失败③：扫完了栈里还剩左括号
}

复杂度：时间 ，空间 （最坏情况全是左括号）。

例：{[()]} 匹配；([)] 属于失败②；(() 属于失败③；()) 属于失败①。

关键边界：三种失败一个都不能漏

失败什么时候发生对应代码
右括号多了扫描中，栈已经空了，又来一个右括号if (top == -1) return false;
类型不配扫描中，弹出的左括号和当前右括号不是一对三组比较
左括号多了扫描结束，栈里还有东西最后的 return top == -1;

最常见的错误是最后直接写 return true，漏掉了第三种情况。

易错点

  • 必须先判断栈空再弹栈。栈空时还执行 st[top--]，top 会变成 ，下标越界。
  • 选择题常问「扫描到某个位置时栈里有什么」，按上面的规则一步步手动模拟就行。

链接

反向链接