上海计算机学会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栈空间足够。带注释的源代码#includebits/stdc.husingnamespacestd;// 我定义一个字符栈用来存储等待匹配的左括号stackchart;string s;intmain(){cins;// 读入括号序列// 遍历整个字符串for(inti0;is.size();i){// 如果当前字符是左括号则将其压入栈中if(s[i](||s[i][||s[i]{){t.push(s[i]);}// 否则当前字符是右括号先检查栈是否为空elseif(t.empty()){// 栈空说明没有左括号与当前右括号匹配不平衡直接输出U并结束coutU;return0;}// 栈非空则检查栈顶左括号是否与当前右括号匹配else{// 若匹配失败三种不匹配的情况则不平衡输出U并结束if(s[i])t.top()!(||s[i]]t.top()![||s[i]}t.top()!{){coutU;return0;}else{// 匹配成功弹出栈顶的左括号t.pop();}}}// 遍历结束后如果栈为空说明全部匹配输出Bif(t.empty()){coutB;}else{// 栈非空说明有未匹配的左括号输出UcoutU;}return0;}