用一个栈存尚未闭合的左括号：右括号只能配栈顶的同类左括号，扫描结束后栈空才输出 OK，否则 Wrong
OJ: roj
题目 ID: 1354
难度:入门
标签:字符串栈
创建: 2026-09-30 06:50
更新: 2026-10-05 11:24
后置题目
roj 3030火车进栈A 教的“栈空弹栈即非法”这一括号合法性失败点，正是 B 第一步把火车进出站归约为合法括号序列时所用的“栈不能空着出”约束（代码用 if stack 保证不空弹），B 在此合法性骨架上再叠加字典序 DFS 枚举与前 20 整树剪枝。roj 1358中缀表达式值(expr)A 教的「中途弹空（右括号多余）与扫完栈非空（左括号多余）两类失败点即配对非法」正是 B 的 tokenize 合法性子过程用的那一步（代码 depth==0 拒右括号、结束后 depth 非 0 拒），B 只把它简化成单类型计数器再叠加记号类别状态机、调度场转后缀与操作数栈求值。luogu P1241括号序列B 的配对规则就是复用 A 教的“右括号只能配栈顶那个同类左括号”，把 A 的判定式匹配（OK/Wrong）改成记录匹配位置，再对未匹配括号补全输出
题目描述
给定一个只含圆括号 ( ) 与方括号 [ ] 的表达式，判断字符串里的括号是否匹配：每个右括号要在左边找到尚未使用且类型相同的左括号配对，配对区间不能交叉。匹配输出 OK，不匹配输出 Wrong。
输入仅一行字符串，字符个数小于 255；输出 OK 或 Wrong。样例输入 ［（］），样例输出 Wrong（样例用的是全角括号，与半角 ()[] 等价）。
思路
用栈保存尚未闭合的左括号，它们从外到内依次入栈。遇左括号入栈；遇右括号时，只有栈非空且栈顶正好是它的同类左括号才能弹出配对，否则立即判 Wrong；扫描结束后栈为空才算 OK。
参考代码
Python 版：
python
#!/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:53
# update_at: 2026-09-30 06:56
import sys
PAIRS = {')': '(', ']': '['} # 右括号 → 它唯一能配的那个左括号
OPEN = frozenset(PAIRS.values()) # 左括号集合
WIDE = str.maketrans('（）［］', '()[]') # 题面样例用的是全角括号，先折算成 ASCII 再判断
def is_matched(brackets: str) -> bool:
"""括号串是否匹配：右括号只允许消耗栈顶那个同类左括号，扫完后栈必须为空。"""
stack: list[str] = [] # 尚未闭合的左括号，栈底在外层、栈顶在最内层
for ch in brackets:
if ch in OPEN:
stack.append(ch) # 左括号入栈，等它对应的右括号
elif not stack or stack[-1] != PAIRS[ch]:
return False # 弹空（右括号多了），或栈顶是与它不同类的左括号
else:
stack.pop() # 配对成功，最内层这一层闭合
return not stack # 栈非空说明还有左括号没被配对
def solve() -> None:
raw = sys.stdin.buffer.read()
# 数据仓里既有 CRLF 的 ASCII 行，也可能有带 BOM 的 UTF-16 行，先按字节识别再整体解码
text = raw.decode('utf-16') if raw.startswith((b'\xff\xfe', b'\xfe\xff')) else raw.decode(errors='ignore')
# 括号以外的字符（空格、换行等）与匹配无关，一次性滤掉
brackets = ''.join(ch for ch in text.translate(WIDE) if ch in OPEN or ch in PAIRS)
print("OK" if is_matched(brackets) else "Wrong")
if __name__ == "__main__":
solve()C++ 版（同一算法）：
cpp
/**
* 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:24
* update_at: 2026-10-05 11:24
*/
// roj 1354 括弧匹配检验：用栈判断圆括号与方括号是否两两配对且不交叉。
#include <iostream>
#include <string>
typedef long long ll;
using namespace std;
char st[4096]; // 栈：存尚未闭合的左括号，栈底是最外层的左括号
char br[4096]; // 折算后的括号串：全角括号换成半角，其它字符全部滤掉
int main() {
string all;
string line;
// 数据行可能是 CRLF 也可能夹杂空行，逐行读入拼接；换行与匹配无关，后面会被滤掉
while (getline(cin, line)) {
all += line;
}
// 第一步：题面样例用的是全角括号（UTF-8 三字节），先折算成半角，同时滤掉非括号字符
ll blen = 0; // 折算后括号串的长度
ll n = all.size();
for (ll i = 0; i < n; ) {
char c = all[i];
if (c == '(' || c == ')' || c == '[' || c == ']') {
br[blen] = c;
blen++;
i++;
} else if (c == '\xef' && i + 2 < n && all[i + 1] == '\xbc') {
// 全角 （ ） ［ ］ 的 UTF-8 编码是 EF BC 88 / 89 / BB / BD
char last = all[i + 2];
if (last == '\x88') {
br[blen] = '(';
blen++;
} else if (last == '\x89') {
br[blen] = ')';
blen++;
} else if (last == '\xbb') {
br[blen] = '[';
blen++;
} else if (last == '\xbd') {
br[blen] = ']';
blen++;
}
i += 3;
} else {
i++; // 空格、换行等字符不影响匹配，直接跳过
}
}
// 第二步：扫一遍括号串，右括号只允许消耗栈顶那个同类左括号
ll top = 0; // 栈内元素个数，栈顶是 st[top-1]
ll ok = 1; // 1 表示目前仍然合法
for (ll i = 0; i < blen; i++) {
char c = br[i];
if (c == '(' || c == '[') {
st[top] = c; // 左括号入栈，等它对应的右括号
top++;
} else if (top == 0) {
ok = 0; // 栈空却来了右括号：右括号多了
break;
} else {
char need; // 这个右括号唯一能配的左括号
if (c == ')') {
need = '(';
} else {
need = '[';
}
if (st[top - 1] != need) {
ok = 0; // 栈顶是另一类左括号：类型错配，或与外层交叉
break;
}
top--; // 配对成功，最内层这一层闭合
}
}
if (ok && top > 0) {
ok = 0; // 扫完栈非空：还有左括号没人配
}
if (ok) {
cout << "OK" << "\n";
} else {
cout << "Wrong" << "\n";
}
return 0;
}