请编写程序判断一个包含“(”和“)”的括号序列是否匹配。如匹配则输出Match;如不匹配,计算出使该序列变为匹配序列所需添加的最少括号数目(只允许在该序列开始和结尾处添加括号),并输出经添加最少括号后得到的合法匹配序列。
输入格式:
输入为若干行,每行一个字符串,包含不超过105个括号。输入行数不超过10行。
输出格式:
对于输入的每个括号序列输出1行或2行信息。若输入的括号序列匹配,则输出Match。若不匹配,则输出分为2行,第1行为一个整数,表示将该序列变为匹配序列所需添加的最少括号数目,第2行为一个字符串,表示经添加最少括号后得到的合法匹配序列。
输入样例:
(())()
)(
()))((
输出样例:
Match
2
()()
4
((()))(())
AC代码:
思路:设置两个计数变量统计前面缺失的左括号数量和后面缺失的右括号数量。
此处应用到c++中string函数:string s(num,c) //生成一个字符串,包含num个c字符C++常用函数总结
#include<bits/stdc++.h>
using namespace std;
int main(){
string str;
while(cin>>str){
int left=0;//多余的左括号数
int right=0;//多余的右括号数
for(char c:str){
if(c=='('){
left++;
}else {
if(left>0)
left--;
else
right++;
}
}
if(left==0&&right==0){
cout<<"Match"<<endl;
}else{
cout<<left+right<<endl;
cout<<string(right,'(')<<str<<string(left,')')<<endl;
}
}
return 0;
}