上海计算机学会2026年月6月赛C++丙组T2 平衡的判定

平衡的判定

题目描述

给定一个由括号组成的字符序列，该序列只会出现六种字符，分别是 ( 、)、[ 、]、{、} 。

请判断输入的括号序列是否是平衡的。

平衡的定义如下：

• 空序列是平衡的；
• 如果某个括号序列 s 是平衡的，那么 [s]、 (s)、{s} 也是平衡的；
• 如果某两个括号序列 s 与 t 是平衡的，那么 s 拼接 t 后也是平衡的。

不能由上述规则得到的括号序列都是不平衡的。

输入格式

一个字符序列：表示输入的括号序列。

输出格式

如果是平衡的，输出 B，否则，输出 U。

数据范围

设 |S| 表示输入序列的长度，

• 对于 50% 的数据，1≤∣S∣≤10001 \le |S| \le 10001≤∣S∣≤1000，保证输入的括号序列只含有 ( 及 )；
• 对于 100% 的数据，1≤n≤10000001 \le n \le 10000001≤n≤1000000；

样例

样例1

输入：

({})[]

输出：

B

样例2

输入：

{)(}

输出：

U

我的题解

这道题是经典的括号匹配问题，我使用栈这个数据结构来辅助判断。
遍历整个字符串，遇到左括号(、[、{就压入栈中；遇到右括号时，先检查栈是否为空，若为空说明没有左括号可以匹配，直接判定为不平衡；否则检查栈顶的左括号是否与当前右括号匹配，若匹配则弹出栈顶，若不匹配也判定为不平衡。
遍历结束后，如果栈为空，说明所有括号都正确匹配，输出B；若栈非空，则说明有多余的左括号，输出U。
时间复杂度 O(n)，空间复杂度 O(n)，n 为序列长度，本题 n 最大 1000000，栈空间足够。

带注释的源代码

#include<bits/stdc++.h>usingnamespacestd;// 我定义一个字符栈，用来存储等待匹配的左括号stack<char>t;string s;intmain(){cin>>s;// 读入括号序列// 遍历整个字符串for(inti=0;i<s.size();i++){// 如果当前字符是左括号，则将其压入栈中if(s[i]=='('||s[i]=='['||s[i]=='{'){t.push(s[i]);}// 否则当前字符是右括号，先检查栈是否为空elseif(t.empty()){// 栈空说明没有左括号与当前右括号匹配，不平衡，直接输出U并结束cout<<"U";return0;}// 栈非空，则检查栈顶左括号是否与当前右括号匹配else{// 若匹配失败（三种不匹配的情况），则不平衡，输出U并结束if(s[i]==')'&&t.top()!='('||s[i]==']'&&t.top()!='['||s[i]=='}'&&t.top()!='{'){cout<<"U";return0;}else{// 匹配成功，弹出栈顶的左括号t.pop();}}}// 遍历结束后，如果栈为空，说明全部匹配，输出Bif(t.empty()){cout<<"B";}else{// 栈非空，说明有未匹配的左括号，输出Ucout<<"U";}return0;}