中 · 栈

括号匹配

不需要栈库也能有栈：一个数组，加一个只碰末端的下标，就是栈。这道题是这个技巧存在的经典理由 —— 括号按「最近打开的先闭合」嵌套，而栈存的恰恰就是这个。

一句话答案左括号压入数组；遇到右括号，检查和栈顶配对后弹出。全程不错配、结束时栈空就输出 YES，否则 NO。

题目

输入: 一行，不超过 1000 个字符，只包含 ( ) [ ] { }。

输出: 括号配平且嵌套正确输出 YES，否则 NO。

样例:

输入	输出
`([{}])`	`YES`
`(]`	`NO`
`(((`	`NO`

「配平」同时意味着两件事：每个右括号都有配对的左括号（永远别从空栈弹出），每个左括号最终都被闭合（结束时栈为空）。少哪一半都算错。

你的解答

main.cpp — 你的解答

「运行我的输入」用的自定义输入

判题在浏览器本地运行。死循环会在 3 秒后被自动中断 —— 但还是确保每个循环都有出口。代码随打随存。

卡住了？提示

提示 1 — 下一个能闭合的，只会是最近打开的那个

从左到右扫。看到 (、[ 或 { 就记下来。看到右括号时，它必须和你还欠着的最后一个左括号配对 —— 只要不是（比如 ([)]），无论后面是什么都坏了。「按到来的反序取出」正是栈做的事。

提示 2 — 三种失败，三处检查

来了右括号但栈是空的 → NO。来了右括号但栈顶类型对不上 → NO。走完整行栈里还剩东西（比如 (((）→ NO。三种都没发生才输出 YES。动手前把这三处检查想清楚，这题就做完一半了。

提示 3 — 把配对判断写清楚

一个紧凑写法：右括号与栈顶配对，当 (open == '(' && c == ')') || (open == '[' && c == ']') || (open == '{' && c == '}')。栈里只放左括号（永远不放右括号），一切都很简单 —— 如果你发现自己在压右括号，停下来重新想想这个循环。

题解（先自己试试！）

#include <iostream>
using namespace std;

int main() {
    char s[1005];
    cin.getline(s, 1005);
    char stack[1005];
    int top = 0;

    int i = 0;
    while (s[i] != '\0') {
        char c = s[i];
        if (c == '(' || c == '[' || c == '{') {
            stack[top] = c;
            top++;
        } else if (c == ')' || c == ']' || c == '}') {
            if (top == 0) { cout << "NO" << endl; return 0; }
            char open = stack[top - 1];
            bool match = (open == '(' && c == ')') ||
                         (open == '[' && c == ']') ||
                         (open == '{' && c == '}');
            if (!match) { cout << "NO" << endl; return 0; }
            top--;
        }
        i++;
    }

    cout << (top == 0 ? "YES" : "NO") << endl;
    return 0;
}

你已经用上了「数组当栈」这个惯用法，它的用途远不止括号：撤销历史、DFS、表达式求值都靠它。文本这边的姊妹模式根本不需要栈 —— 两个下标相向而行 —— 回文串正是这么做的。

深度解析

为什么这样做对

括号按「后开先闭」闭合 —— 这正是栈的定义（LIFO）。一个数组加一个整数 top 就是一台完整的栈：压入是 stack[top++] = c，弹出是 top--，看栈顶是 stack[top-1]。

代价

n 个字符的行是 O(n) 时间 —— 每个字符至多被压入或弹出一次 —— 最坏情况（全是左括号）O(n) 空间。

常见错法

从空栈弹出：单独一个 ] 到来时没有任何东西可配。碰 stack[top-1] 之前先查 top == 0，否则你会读到下标之下的一堆垃圾。
忘了检查剩余。((( 如果只对右括号作反应会打出 YES —— 结束时栈必须为空，所以最后一行需要 top == 0。

下一步

测字符串对称性的另一条路根本不用栈：两个下标相向而行，见回文串。

记住这两句

栈 = 数组 + 一个只碰末端的下标。
三种失败：空栈弹出、类型不配、结尾有剩余。

🐞 这段是错的 —— 点开,亲手让它挂一次

只数左右数量、不看类型 —— ([)] 蒙混过关

#include <iostream>
using namespace std;

int main() {
    char s[1005];
    cin.getline(s, 1005);
    int open = 0;
    int i = 0;
    while (s[i] != '\0') {
        if (s[i] == '(' || s[i] == '[' || s[i] == '{') open++;
        else if (s[i] == ')' || s[i] == ']' || s[i] == '}') open--;
        i++;
    }
    cout << (open == 0 ? "YES" : "NO") << endl;
    return 0;
}