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

本文分享的必刷题目是从蓝桥云课、洛谷、AcWing等知名刷题平台精心挑选而来并结合各平台提供的算法标签和难度等级进行了系统分类。题目涵盖了从基础到进阶的多种算法和数据结构旨在为不同阶段的编程学习者提供一条清晰、平稳的学习提升路径。欢迎大家订阅我的专栏算法题解C与Python实现附上汇总贴算法竞赛备考冲刺必刷题C | 汇总【题目来源】AcWing6030. 字符串匹配问题 - AcWing题库【题目描述】字符串中只含有括号(),[],,{}判断输入的字符串中括号是否匹配。如果括号有互相包含的形式从内到外必须是,(),[],{}。例如输入:[()]应该输出:YES而输入([])([)]都应该输出NO。【输入】第一行为一个整数n nn表示以下有多少个由括号组成的字符串。接下来的n nn行每行都是一个由括号组成的长度不超过150 150150的字符串。【输出】共n nn行每行输出YES或NO。【输入样例】5 {}{}()()[][] {{}}{{}}(())(())[[]][[]] {{}}{{}}(())(())[[]][[]] {}{[]}(())(())[[()]][[]] }{{[]}(())(())[[()]][[]]【输出样例】YES YES YES YES NO【算法标签】#栈#【代码详解】#includebits/stdc.husingnamespacestd;intpri[128];// pri[i]: 字符i的优先级// 初始化括号的优先级voidinitPri(){// 左括号都是正数右括号都是负数配对的括号的优先级互为相反数pri[]1;pri[(]2;pri[[]3;pri[{]4;pri[]-1;pri[)]-2;pri[]]-3;pri[}]-4;}// 求解一组数据voidsolve(){stackcharstk;// 括号栈string s;// 输入字符串cins;// 输入字符串for(inti0;is.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{coutNOendl;// 否则不匹配return;}}}else// 如果s[i]是右括号{if(stk.empty())// 如果栈为空{coutNOendl;// 不匹配return;}else{if(pri[s[i]]pri[stk.top()]0)// 如果当前右括号和栈顶左括号匹配优先级和为0{stk.pop();// 出栈}else{coutNOendl;// 否则不匹配return;}}}}if(stk.empty())// 如果遍历结束后栈为空{coutYESendl;// 所有括号正确匹配}else{coutNOendl;// 栈中还有未匹配的左括号}}intmain(){initPri();// 初始化优先级表intn;// 测试数据组数cinn;// 输入测试组数while(n--)// 处理每组测试数据{solve();}return0;// 程序正常结束}【运行结果】5 {}{}()()[][] YES {{}}{{}}(())(())[[]][[]] YES {{}}{{}}(())(())[[]][[]] YES {}{[]}(())(())[[()]][[]] YES }{{[]}(())(())[[()]][[]] NO