题解：AcWing 6030 字符串匹配问题

本文分享的必刷题目是从蓝桥云课、洛谷、AcWing等知名刷题平台精心挑选而来，并结合各平台提供的算法标签和难度等级进行了系统分类。题目涵盖了从基础到进阶的多种算法和数据结构，旨在为不同阶段的编程学习者提供一条清晰、平稳的学习提升路径。

欢迎大家订阅我的专栏：算法题解：C++与Python实现！

附上汇总贴：算法竞赛备考冲刺必刷题（C++） | 汇总

【题目来源】

AcWing：6030. 字符串匹配问题 - AcWing题库

【题目描述】

字符串中只含有括号(),[],<>,{}，判断输入的字符串中括号是否匹配。

如果括号有互相包含的形式，从内到外必须是<>,(),[],{}。

例如，输入:[()]应该输出:YES，而输入([])，([)]都应该输出NO。

【输入】

第一行为一个整数n nn，表示以下有多少个由括号组成的字符串。

接下来的n nn行，每行都是一个由括号组成的长度不超过150 150150的字符串。

【输出】

共n nn行，每行输出YES或NO。

【输入样例】

5 {}{}<><>()()[][] {{}}{{}}<<>><<>>(())(())[[]][[]] {{}}{{}}<<>><<>>(())(())[[]][[]] {<>}{[]}<<<>><<>>>((<>))(())[[(<>)]][[]] ><}{{[]}<<<>><<>>>((<>))(())[[(<>)]][[]]

【输出样例】

YES YES YES YES NO

【算法标签】

#栈#

【代码详解】

#include<bits/stdc++.h>usingnamespacestd;intpri[128];// pri[i]: 字符i的优先级// 初始化括号的优先级voidinitPri(){// 左括号都是正数，右括号都是负数，配对的括号的优先级互为相反数pri['<']=1;pri['(']=2;pri['[']=3;pri['{']=4;pri['>']=-1;pri[')']=-2;pri[']']=-3;pri['}']=-4;}// 求解一组数据voidsolve(){stack<char>stk;// 括号栈string s;// 输入字符串cin>>s;// 输入字符串for(inti=0;i<s.length();++i)// 遍历字符串的每个字符{if(pri[s[i]]>0)// 如果s[i]是左括号{if(stk.empty())// 如果栈为空{stk.push(s[i]);// 直接入栈}else{if(pri[s[i]]<=pri[stk.top()])// 如果当前左括号的优先级 <= 栈顶左括号的优先级{stk.push(s[i]);// 入栈}else{cout<<"NO"<<endl;// 否则不匹配return;}}}else// 如果s[i]是右括号{if(stk.empty())// 如果栈为空{cout<<"NO"<<endl;// 不匹配return;}else{if(pri[s[i]]+pri[stk.top()]==0)// 如果当前右括号和栈顶左括号匹配（优先级和为0）{stk.pop();// 出栈}else{cout<<"NO"<<endl;// 否则不匹配return;}}}}if(stk.empty())// 如果遍历结束后栈为空{cout<<"YES"<<endl;// 所有括号正确匹配}else{cout<<"NO"<<endl;// 栈中还有未匹配的左括号}}intmain(){initPri();// 初始化优先级表intn;// 测试数据组数cin>>n;// 输入测试组数while(n--)// 处理每组测试数据{solve();}return0;// 程序正常结束}

【运行结果】

5 {}{}<><>()()[][] YES {{}}{{}}<<>><<>>(())(())[[]][[]] YES {{}}{{}}<<>><<>>(())(())[[]][[]] YES {<>}{[]}<<<>><<>>>((<>))(())[[(<>)]][[]] YES ><}{{[]}<<<>><<>>>((<>))(())[[(<>)]][[]] NO