UVa 673 Parentheses Balance

题目描述给定一个由圆括号()和方括号[]组成的字符串判断其是否“正确”。正确性的递归定义如下空字符串是正确的若A和B正确则AB正确若A正确则(A)和[A]正确。给定若干字符串长度不超过128128128判断每个字符串是否合法。输入格式第一行为一个正整数nnn表示字符串个数。接下来nnn行每行一个由()和[]组成的字符串可能为空行。输出格式对于每个字符串输出一行Yes或No。样例输入3 ([]) ((()))) ()()()()输出Yes No Yes题目分析本题是经典的括号匹配问题。使用栈进行匹配遇到左括号(或[入栈遇到右括号)或]时检查栈顶是否为对应的左括号若不匹配或栈空则非法。最后若栈非空也非法。注意空字符串是合法的。解题思路读入整数nnn。对每个字符串遍历每个字符。若为左括号入栈。若为右括号检查栈是否为空或栈顶是否匹配若匹配则弹出否则标记错误并跳出循环。遍历结束后若栈非空则错误。输出Yes或No。注意字符串可能为空使用getline读取整行不要用cin 否则无法读取空行。复杂度分析每个字符处理一次时间复杂度O(L)O(L)O(L)L≤128L \le 128L≤128。空间复杂度O(L)O(L)O(L)。代码实现// Parentheses Balance// UVa ID: 673// Verdict: Accepted// Submission Date: 2016-08-15// UVa Run Time: 0.010s//// 版权所有C2016邱秋。metaphysis # yeah dot net#includebits/stdc.husingnamespacestd;intmain(intargc,char*argv[]){cin.tie(0);cout.tie(0);ios::sync_with_stdio(false);string line;getline(cin,line);intnstoi(line);for(inti1;in;i){getline(cin,line);boolerrorfalse;stackcharbank;for(intj0;jline.length();j)if(line[j](||line[j][)bank.push(line[j]);elseif(line[j])){if(bank.empty()||bank.top()!(){errortrue;break;}elsebank.pop();}elseif(line[j]]){if(bank.empty()||bank.top()![){errortrue;break;}elsebank.pop();}if(bank.size()0)errortrue;cout(error?No\n:Yes\n);}return0;}总结本题通过栈实现括号匹配关键在于正确处理空行输入以及栈的匹配逻辑。该解法简单高效适用于所有括号匹配问题。