UVa 551 Nesting a Bunch of Brackets

题目描述题目要求检查表达式中的括号是否正确嵌套。括号类型包括()、[]、{}、以及复合括号(*和*)各视为一个字符。表达式中的非括号字符包括字母、数字、运算符等也占一个位置。若表达式正确输出YES否则输出NO及第一个导致错误的位置即最短不能扩展为正确表达式的前缀长度。输入格式输入包含多行每行一个表达式长度不超过300030003000。输入以文件结束符EOF\texttt{EOF}EOF终止。输出格式对于每行输入输出一行若正确输出YES否则输出NO和一个空格然后输出错误位置。样例输入(*a(*) (*a{}*)输出NO 6 YES题目分析本题的核心是使用栈进行括号匹配。括号识别普通括号()、[]、{}、。复合括号(*和*)各视为一个符号两个字符。非括号字符视为普通字符只占位置不影响括号匹配。算法遍历字符串的每个字符维护当前位置计数器从111开始。遇到左括号(、[、{、或(*时将对应符号压栈。遇到右括号)、]、}、或*)时检查栈顶是否为对应的左括号。若是则弹出否则记录错误位置并退出。遍历结束后若栈非空则存在未匹配的左括号错误位置为最后一个字符的位置加111即超出表达式长度。注意点(*和*)是两个字符需要一起处理。非括号字符只增加位置计数不改变栈。复杂度分析每个字符处理一次时间复杂度O(L)O(L)O(L)。代码实现// Nesting a Bunch of Brackets// UVa ID: 551// Verdict: Accepted// Submission Date: 2016-08-18// UVa Run Time: 0.000s//// 版权所有C2016邱秋。metaphysis # yeah dot net#includebits/stdc.husingnamespacestd;intmain(intargc,char*argv[]){cin.tie(0);cout.tie(0);ios::sync_with_stdio(false);charleft_brackets[4]{(,[,{,},right_brackets[4]{),],},};string line;while(getline(cin,line)){stackcharbrackets;inti0,lengthline.length(),counter0;boolerrorfalse;while(ilength){counter;if(line[i](){if(i1lengthline[i1]*){brackets.push($);i;}elsebrackets.push(();}elseif(line[i]*){if(i1lengthline[i1])){if(brackets.empty()||brackets.top()!$){errortrue;break;}else{brackets.pop();i;}}}else{boolupdatedfalse;for(intj0;j4;j)if(left_brackets[j]line[i]){brackets.push(line[i]);updatedtrue;break;}if(!updated){for(intj0;j4;j)if(right_brackets[j]line[i]){if(brackets.empty()||brackets.top()!left_brackets[j])errortrue;elsebrackets.pop();break;}}if(error)break;}i;}if(brackets.size()0)errortrue;if(errorilength)counter;if(error)coutNO counter\n;elsecoutYES\n;}return0;}