扩号匹配问题

题目描述

多组数据读到 EOF，每行只含 (、) 与大小写字母，长度不超过 $100$ 。每个 ( 与它右边距离最近的 ) 配对（从内到外）。对每行输出两行：第一行原串，第二行等长标注——多余的 ( 标 $，多余的 ) 标 ?，其余位置留空格。样例见 problem.md。

思路

从左到右扫一遍，用栈存尚未配对的左括号下标：读到 ( 入栈，读到 ) 时栈非空则弹栈配对、栈空则该 ) 标 ?；扫描结束后栈里剩下的左括号全部标 $。每字符最多入/出栈一次，时间 $O(n)$ 。

参考代码

Python 版：

python

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36#!/usr/bin/env python3
# Author by Rainboy blog: https://rainboylv.com github: https://github.com/rainboylvx
# rbook: -> https://rbook.roj.ac.cn  https://rbook2.roj.ac.cn
# rainboy的学习导航网站: https://idx.roj.ac.cn
# create_at: 2026-09-29 23:28
# update_at: 2026-09-29 23:28

import sys


def marked_line(s: str) -> str:
    """返回标注行：多余的左括号标 $，多余的右括号标 ?，其余位置留空格。"""
    stack: list[int] = []          # 尚未配对的左括号下标，"距离最近"就是栈顶
    unmatched_right: set[int] = set()
    for i, ch in enumerate(s):
        if ch == '(':
            stack.append(i)
        elif ch == ')':
            if stack:
                stack.pop()        # 与左边最近的未配对左括号配对
            else:
                unmatched_right.add(i)
    unmatched_left = set(stack)    # 扫完仍留在栈里的左括号永远找不到搭档
    return ''.join(
        '$' if i in unmatched_left else '?' if i in unmatched_right else ' '
        for i in range(len(s))
    )


def solve() -> None:
    lines = sys.stdin.read().split()   # 一行一组数据，组间空白分隔
    sys.stdout.write(''.join(f'{s}\n{marked_line(s)}\n' for s in lines))


if __name__ == "__main__":
    solve()

C++ 版（同一算法）：

cpp

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57/**
 * Author by Rainboy blog: https://rainboylv.com github: https://github.com/rainboylvx
 * rbook: -> https://rbook.roj.ac.cn  https://rbook2.roj.ac.cn
 * rainboy的学习导航网站: https://idx.roj.ac.cn
 * create_at: 2026-10-05 05:27
 * update_at: 2026-10-05 05:28
 */
// main.cpp：括号匹配。栈存尚未配对的左括号下标，"最近的左括号"就是栈顶。

#include <cstdio>
#include <iostream>
#include <string>
using namespace std;

typedef long long ll;

const int MAXN = 105;       // 单行长度 ≤ 100，留 5 个余量
int st[MAXN];               // 栈：尚未配对的左括号下标
int top_;                   // 栈顶指针（用 top_ 避免和 std 冲突）
bool badL[MAXN];            // badL[i] = 第 i 个 '(' 无法配对
bool badR[MAXN];            // badR[i] = 第 i 个 ')' 无法配对

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    string s;
    // 多组输入，按行读直到 EOF
    while (getline(cin, s)) {
        if ((int)s.size() > MAXN) continue;     // 题目限制外直接跳过
        // 重新初始化当前行的标记
        for (int i = 0; i <= (int)s.size(); ++i) { badL[i] = badR[i] = false; }
        top_ = 0;
        for (int i = 0; i < (int)s.size(); ++i) {
            char ch = s[i];
            if (ch == '(') {
                st[++top_] = i;                 // 入栈：当前 '(' 成为最近的未配对左括号
            } else if (ch == ')') {
                if (top_ > 0) {
                    --top_;                     // 与栈顶配对
                } else {
                    badR[i] = true;             // 栈空：右括号失配
                }
            } // 字母不入栈也不打标记
        }
        // 扫描结束仍留在栈里的左括号永远找不到搭档
        while (top_ > 0) { badL[st[top_--]] = true; }
        // 输出原串与标注串
        cout << s << '\n';
        for (int i = 0; i < (int)s.size(); ++i) {
            if (badL[i]) cout << '$';
            else if (badR[i]) cout << '?';
            else cout << ' ';
        }
        cout << '\n';
    }
    return 0;
}

目录

题目描述

思路

参考代码