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//// 版权所有（C）2016，邱秋。metaphysis # yeah dot net#include<bits/stdc++.h>usingnamespacestd;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)){stack<char>brackets;inti=0,length=line.length(),counter=0;boolerror=false;while(i<length){counter++;if(line[i]=='('){if(i+1<length&&line[i+1]=='*'){brackets.push('$');i++;}elsebrackets.push('(');}elseif(line[i]=='*'){if(i+1<length&&line[i+1]==')'){if(brackets.empty()||brackets.top()!='$'){error=true;break;}else{brackets.pop();i++;}}}else{boolupdated=false;for(intj=0;j<4;j++)if(left_brackets[j]==line[i]){brackets.push(line[i]);updated=true;break;}if(!updated){for(intj=0;j<4;j++)if(right_brackets[j]==line[i]){if(brackets.empty()||brackets.top()!=left_brackets[j])error=true;elsebrackets.pop();break;}}if(error)break;}i++;}if(brackets.size()>0)error=true;if(error&&i==length)counter++;if(error)cout<<"NO "<<counter<<'\n';elsecout<<"YES\n";}return0;}