A39815. 生成括号
填空题
中等
知识点
题目描述
生成括号
题目描述
Paul是一名数学专业的同学，在课余选修了C++编程课，现在他能够自己写程序判断判断一个给定的由’(‘和’)'组成的字符串是否是正确匹配的。可是他不满足于此，想反其道而行之，设计一个程序，能够生成所有合法的括号组合，请你帮助他解决这个问题。
输入
输入只有一行N，代表生成括号的对数（1 ≤ N ≤ 10)。
输出
输出所有可能的并且有效的括号组合，按照字典序进行排列，每个组合占一行。
样例输入
3
样例输出
((()))
(()())
(())()
()(())
()()()
参考答案
#include<bits/stdc++.h>
using namespace std;
struct pos
{
char c;
int index;
};
bool cmp(pos p1,pos p2){
if(p1.index<p2.index)
return true;
else
return false;
}
int main()
{
string s;
pos pos1;
stack<pos> bracket_r;
stack<pos> bracket_l;
vector<pos> help;
bool flag=false;
while(1){
cin>>s;
for(int i=0;i<s.length();i++)
{
pos1.c=s[i];
pos1.index=i;
if(s[i]=='(')
bracket_l.push(pos1);
else if(s[i]==')')
if(bracket_l.empty()==false)
bracket_l.pop();
else
bracket_r.push(pos1);
}
while(bracket_l.empty()==false)
{
help.push_back(bracket_l.top());
bracket_l.pop();
}
while(bracket_r.empty()==false)
{
help.push_back(bracket_r.top());
bracket_r.pop();
}
sort(help.begin(),help.end(),cmp);
cout<<s<<endl;
for(int i=0;i<s.length();i++){
for(int j=0;j<help.size();j++)
if(help[j].index==i){
if(help[j].c=='(')
cout<<"$";
else if(help[j].c==')')
cout<<"?";
flag=true;
break;
}
if(flag==false)
cout<<" ";
flag=false;
}
cout<<endl;
help.clear();
while(bracket_l.empty()==false)
bracket_l.pop();
while(bracket_r.empty()==false)
bracket_r.pop();
}
return 0;
}答案解析
本题的麻烦在于要按字典序进行排列。做法有二:一是先穷举所有组合然后排序二是找规律后用字符移位的方法逐一输出。
穷举再排序的方案要动态创建二维字符数,字符移位则只需要一个一维字符数组即可，相对简单。
原理是先生成指定数量的嵌套括号对，放在数组里然后找到最里层的括号对，接着寻找其后面的左括号，找到则将括号对后面的字符左侧，将括号对插入到所找到的左括号的位置。然后在移动的括号对之前寻找最右侧的第一个括号对，重复上述操作如果未找到左括号，则找右括号，找到后右移，直到移到最后面。关键:最左侧出现新的成对的括号时，从括号后面重新生成数量-1的嵌套括号对放在数组里。然后递归调用，直到数组变成“() () ()”的形式。
上一题
下一题