括号序列

GitHub跳转原题关系图返回列表

按题意用栈匹配最近未匹配左括号，记录成功位置并为其余括号补出对应一对。

OJ: luogu

题目 ID: P1241

难度:普及-

标签:栈字符串模拟python

日期: 2026-07-16 18:10

目录

  1. 题意
  2. 思路
  3. Python 知识
  4. 代码
  5. 复杂度
  6. 总结

题意

按指定规则从左到右给括号配对：右括号只检查左侧最近的未匹配左括号，类型相同才匹配。最后为每个未匹配括号在旁边补一个对应括号。

思路

栈保存尚未匹配的左括号下标。遇到右括号时，只看栈顶：类型相同则弹栈并标记两个位置；类型不同则当前右括号匹配失败，栈顶左括号仍保持未匹配，不能越过它去找更早括号。

扫描结束后按原顺序输出。已匹配字符原样保留；未匹配的 ( 或 ) 输出 ()，未匹配的 [ 或 ] 输出 []。

Python 知识

  • 列表保存下标栈，stack[-1] 取得最近未匹配左括号。
  • 字典 opening_for 表示右括号所需的左括号，completion 表示每种未匹配字符的补全结果。
  • matched[index] = matched[stack.pop()] = True 同时标记一对位置。
  • 最终用生成器和 "".join 构造字符串，避免循环中反复拼接。
  • /home/rainboy/mycode/hugo-blog/content/program_language/python/input_output_and_strings.md：字符串不可变与 join。
  • /home/rainboy/mycode/hugo-blog/content/program_language/python/generator_expression.md：按条件生成输出片段。

代码

python
brackets = input().strip()
stack = []
matched = [False] * len(brackets)
opening_for = {")": "(", "]": "["}
completion = {"(": "()", ")": "()", "[": "[]", "]": "[]"}

for index, bracket in enumerate(brackets):
    if bracket in "([":
        stack.append(index)
    elif stack and brackets[stack[-1]] == opening_for[bracket]:
        matched[index] = matched[stack.pop()] = True

print("".join(
    bracket if matched[index] else completion[bracket]
    for index, bracket in enumerate(brackets)
))
cpp
/**
 * P1241 括号序列
 * Author by Rainboy blog: https://rainboylv.com github: https://github.com/rainboylvx
 * rbook: -> https://rbook.roj.ac.cn
 * rainboy的学习导航网站: https://idx.roj.ac.cn
 * create_at: 2026-07-27 00:00
 * update_at: 2026-07-27 00:00
 */

#include <bits/stdc++.h>
using namespace std;

const int MAXN = 105;

char s[MAXN];       // 原括号字符串
bool match[MAXN];   // match[i] = true 表示位置 i 已配对
int st[MAXN];       // 数组模拟栈，存左括号的下标
int top = 0;        // 栈顶指针

int main() {
    scanf("%s", s);
    int len = strlen(s);
    // 扫描一遍：右括号只看栈顶（最近未匹配左括号）
    for (int i = 0; i < len; ++i) {
        if (s[i] == '(' || s[i] == '[') {
            st[++top] = i; // 左括号入栈
        } else {
            // 栈非空 且 栈顶左括号与当前右括号类型匹配
            if (top && (
                (s[i] == ')' && s[st[top]] == '(') ||
                (s[i] == ']' && s[st[top]] == '[')
            )) {
                match[i] = match[st[top]] = true;
                --top; // 匹配成功，弹栈
            }
            // 类型不匹配 => 当前右括号作废，栈顶左括号继续保留
        }
    }
    // 按原顺序输出
    for (int i = 0; i < len; ++i) {
        if (match[i]) {
            putchar(s[i]);
        } else {
            // 未匹配的括号输出补全的一对
            if (s[i] == '(' || s[i] == ')') printf("()");
            else printf("[]");
        }
    }
    putchar('\n');
    return 0;
}

复杂度

每个字符最多入栈、出栈一次，时间和空间复杂度均为 O(∣s∣)O(|s|)。

总结

本题规则与普通“遇到不匹配就弹栈”不同：右括号只能检查最近未匹配左括号，类型不符时两者都保留为未匹配。