字符串匹配问题(strs)

题目描述

给出 $n$ 个只由 () [] <> {} 四种括号组成的字符串（每行一个，长度不超过 $255$ ），判断每个串是否匹配：每个左括号都要有同类的右括号与之配对且不交叉错位，且括号互相包含时从内到外的类型顺序必须是 <>、()、[]、{}。输入第一行为整数 $n$ ，接下来 $n$ 行每行一个括号串；输出 $n$ 行，每行 YES 或 NO。样例：输入 2 行 [()]、([])，输出依次为 YES、NO。

思路

用一个栈做括号匹配：四类左括号按「越靠内优先级越高」编码为 {=0、[=1、(=2、<=3，右括号编码取同类加 4，栈从底到顶正好是从外到内的嵌套顺序。左括号入栈前若编号小于栈顶就违反优先级规则，右括号则要求栈非空且与栈顶编码差为 4（同种），扫完栈空即输出 YES。

参考代码

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
37
38
39
40
41
42#!/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-30 06:51
# update_at: 2026-09-30 06:58

import sys

# 左括号按“允许的嵌套层级”编码：编号越大越靠内层。
# 题面要求从内到外依次是 <>, (), [], {}，所以 < 必须在最内层（编号 3），{ 在最外层（编号 0）。
# 右括号编码 = 同类左括号 + 4，于是“左右是否同一种括号”退化成“编码差是否为 4”。
LEVEL = {'{': 0, '[': 1, '(': 2, '<': 3, '}': 4, ']': 5, ')': 6, '>': 7}
CLOSE = 4  # 互相匹配的一对括号，其左、右编码的固定差值


def is_matched(s: str) -> bool:
    """判断一行括号串是否合法：必须两两配对，且从内到外依次是 <>,(),[],{}。"""
    stack: list[int] = []  # 自底向上只存左括号编号，恰好对应“由外到内”的嵌套顺序
    for code in map(LEVEL.get, s):
        if code < CLOSE:  # 左括号
            if stack and code < stack[-1]:  # 编号比当前最内层还小，也就是还想更靠外
                return False
            stack.append(code)
        elif not stack:  # 右括号，但没有可配对的左括号
            return False
        else:
            top = stack.pop()
            if code - top != CLOSE:  # 与刚弹出的左括号不同种
                return False
    return not stack  # 还留着没闭合的左括号时栈非空


def solve() -> None:
    lines = sys.stdin.read().splitlines()
    n = int(lines[0])  # 第一行是串数
    answers = ('YES' if is_matched(line.strip()) else 'NO' for line in lines[1:1 + n])
    print('\n'.join(answers))


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
58
59
60
61
62
63
64
65/**
 * 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 11:53
 * update_at: 2026-10-05 11:53
 */

#include <cstdio>
#include <cstring>

typedef long long ll;

const int MAXL = 260; // 每行字符串长度不超过 255，多留一点余量

char s[MAXL]; // 当前读入的括号串
int stk[MAXL]; // 栈：从底到顶存未闭合左括号的编号，正好是从外到内的嵌套顺序
int top; // 栈顶指针（栈内元素个数）

// 把括号字符映射成编码；返回 -1 表示不是括号（本题不会出现）。
int get_level(char c) {
    if (c == '{') return 0;
    if (c == '[') return 1;
    if (c == '(') return 2;
    if (c == '<') return 3;
    if (c == '}') return 4;
    if (c == ']') return 5;
    if (c == ')') return 6;
    return 7; // '>'
}

// 判断一个括号串是否合法：既要两两配对，又要内层优先级不低于外层
bool check() {
    top = 0; // 每个串开始前清空栈
    ll len = strlen(s);
    for (ll i = 0; i < len; ++i) {
        int code = get_level(s[i]);
        if (code < 4) { // 左括号
            // 新左括号只能插在最内层：编号小于栈顶说明它比当前最内层还靠外，非法
            if (top > 0 && code < stk[top - 1])
                return false;
            stk[top++] = code;
        } else { // 右括号
            if (top == 0) // 没有可配对的左括号
                return false;
            --top;
            if (code - stk[top] != 4) // 与弹出的左括号不同种
                return false;
        }
    }
    return top == 0; // 还留着没闭合的左括号时栈非空
}

int main() {
    int n;
    scanf("%d", &n);
    for (int i = 1; i <= n; ++i) {
        scanf("%s", s); // 括号串不含空白，用 %s 读即可
        if (check())
            printf("YES\n");
        else
            printf("NO\n");
    }
    return 0;
}

字符串匹配问题(strs)

目录

题目描述

思路

参考代码