首页 > 代码库 > 括号序列
括号序列
题目描述
定义如下规则序列(字符串)：
1．空序列是规则序列；
2．如果S是规则序列，那么(S)和[S]也是规则序列；
3．如果A和B都是规则序列，那么AB也是规则序列。
例如，下面的字符串都是规则序列：
()，[]，(())，([])，()[]，()[()]
而以下几个则不是：
(，[，]，)(，())，([()
现在，给你一些由‘(’，‘)’，‘[’，‘]’构成的序列，你要做的，是找出一个最短规则序列，使得给你的那个序列是你给出的规则序列的子列。(对于序列a1，a2，…，an和序列bl，b2，…，bm，如果存在一组下标1≤i1<i2<…<in≤m，使得aj＝b(i,j)对一切1≤j≤n成立，那么a1，a2…，an就叫做b1，b2，…，bm的子列。
输入输出格式
输入格式：
输入文件仅一行，全部由‘(’，‘)’，‘]’，‘]’组成，没有其他字符，长度不超过100。
输出格式：
输出文件也仅有一行，全部由‘(’，‘)’，‘]’，‘]’组成，没有其他字符，把你找到的规则序列输出即可。因为规则序列可能不止一个，因此要求输出的规则序列中嵌套的层数尽可能地少。
输入输出样例
输入样例#1：
([()
输出样例#1：
()[]()
说明
输出解释：
{最多的嵌套层数为1，如层数为2时的一种为()[()]}
jsoi2011
【题目分析】
说一下大体思路，dp[i][j]表示从i到j需要插入的括号的个数，path[i][j]记录i到j中划分位置k，递归输出
非满分算法
#include<cstdio>#include<cstring>#include<iostream>using namespace std;const int maxn=1100;char str[maxn];int dp[maxn][maxn],p[maxn][maxn],len;void print(int start,int end){ if(start>end) return ; else if(start==end)//找到没有被匹配的括号 { if(str[start]==‘(‘||str[end]==‘)‘) printf("()"); else printf("[]"); } else if(p[start][end]==-1)//如果这段括号中没有被分割的位置 { printf("%c",str[start]); print(start+1,end-1); printf("%c",str[end]); } else //从p[start][end]处被分开，递归输出 { print(start,p[start][end]); print(p[start][end]+1,end); }}int main(){ memset(dp,0,sizeof dp); scanf("%s",str+1); len=strlen(str+1); for(int i=1;i<=len;i++) dp[i][i]=1; for(int l=2;l<=len;l++) for(int i=1;i<=len-1;i++) { int j=i+l-1; if(str[i]==‘(‘&&str[j]==‘)‘||str[i]==‘[‘&&str[j]==‘]‘) dp[i][j]=dp[i+1][j-1], p[i][j]=-1; else dp[i][j]=0x7fffffff; for(int k=i;k<=j-1;k++) if(dp[i][j]>dp[i][k]+dp[k][j]) dp[i][j]=dp[i][k]+dp[k][j], p[i][j]=k; } print(1,len); return 0;}
括号序列
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。