Brackets Sequence
Let us define a regular brackets sequence in the following way:
- Empty sequence is a regular sequence.
- If S is a regular sequence, then (S) and [S] are both regular sequences.
- If A and B are regular sequences, then AB is a regular sequence.
For example, all of the following sequences of characters are regular brackets sequences:
(), [], (()), ([]), ()[], ()[()]
And all of the following character sequences are not:
(, [, ), )(, ([)], ([(]
Some sequence of characters '(', ')', '[', and ']' is given. You are to find the shortest possible regular brackets sequence, that contains the given character sequence as a subsequence. Here, a string a1a2...an is called a subsequence of the string b1b2...bm, if there exist such indices 1 ≤ i1 < i2 < ... < in ≤ m, that aj=bij for all 1 ≤ j ≤ n.
Input
The input contains at most 100 brackets (characters '(', ')', '[' and ']') that are situated on a single line without any other characters among them.
Output
Write a single line that contains some regular brackets sequence that has the minimal possible length and contains the given sequence as a subsequence.
Sample
| input | output |
|---|---|
([(] | ()[()] |
Problem Author: Andrew Stankevich
Problem Source: 2001-2002 ACM Northeastern European Regional Programming Contest
Problem Source: 2001-2002 ACM Northeastern European Regional Programming Contest
--------------------------------------------------editorial----------------------------------------------------------
from the given sub sequence we have to find length of minimum valid bracket sequence
there is a observation in this problem ans of will be maximum 2*length of the given sub sequence
since in the worst case we can insert 1 character for each character of the sub sequence ,
also in the best case ans=length of the sub sequence if the given sub sequence is already balanced..
now in rest cases we can pair in some of characters from the given sum sequence and try to find the optimal answer ,
suppose we need to find answer of sub sequence fro l to r
1-> 1 st option will be we cab insert pair for character at index l ans find ans for l+1 to r
2-> for i >l and <l we pair char at position l with ith character and solve( l+1,i-1) ans solve(i+1,r)
for the backtracking part also we will used the computed value for deciding the the characters of the string ,,, see the code of backtracking for clarity
--------------------------------------------------code------------------------------------------------------------------
my code
#include<iostream>
#include<bits/stdc++.h>
using namespace std;
int dp[200][200];
char arr[1000];
int len;
int solve(int l,int r)
{
if(dp[l][r] !=-1) return dp[l][r];
else if(l>r) return 0;
else
{
int ret=501;
for(int i=l;i<=r;i++)
{
if((arr[l]=='(' && arr[i]==')') || (arr[l]=='[' && arr[i]==']'))
{
ret=min(ret,solve(l+1,i-1)+solve(i+1,r));
}
else
{
ret=min(ret,1+solve(l+1,i)+solve(i+1,r));
}
}
dp[l][r]=ret;
return ret;
}
}
int print(int l,int r)
{
// cout<<"print "<<l<<" "<<r<<endl;
if(l>r) return 0;
else
{
int max=solve(l,r);
// cout<<"max in the range of "<<l<<" "<<r<<" "<<max<<endl;
if(max==1+solve(l+1,r))
{
// cout<<"if"<<endl;
if(arr[l]=='(' || arr[l]==')')
cout<<"()";
else if(arr[l]==']' || arr[l]=='[') cout<<"[]";
print(l+1,r);
}
else
{
// cout<<"else"<<endl;
for(int i=l+1;i<=r;i++)
{
// cout<<"matching "<<arr[l]<<" "<<arr[i]<<" "<<solve(l+1,i-1)+solve(i+1,r)<<endl;
if(((arr[l]=='(' && arr[i]==')')|| (arr[l]=='['&&arr[i]==']') )&& max==solve(l+1,i-1)+solve(i+1,r))
{
// cout<<"match index "<<l<<" "<<i<<endl;
if(arr[l]=='(')
{
cout<<"(";
print(l+1,i-1);
cout<<")";
print(i+1,r);
}
else if(arr[l]=='[')
{
cout<<"[";
print(l+1,i-1);
cout<<"]";
print(i+1,r);
}
break;
}
else
{
if(max==1+solve(l+1,i-1)+solve(i+1,r)+solve(i+1,r))
{
if(arr[l]=='(')
{
cout<<"(";
print(l+1,i-1);
cout<<")";
print(i+1,r);
}
else if(arr[l]=='[')
{
cout<<"[";
print(l+1,i-1);
cout<<"]";
print(i+1,r);
}
break;
}
}
}
}
}
}
int main()
{
cin>>arr;
for(int i=0;i<=101;i++)
{
for(int j=0;j<=101;j++) dp[i][j]=-1;
}
for(int i=0;i<=101;i++) dp[i][i]=1;
len=strlen(arr);
for(int i=0;i<len-1;i++)
{
if(arr[i]=='(' && arr[i+1]==')') dp[i][i+1]=0;
else if(arr[i]=='[' && arr[i+1]==']') dp[i][i+1]=0;
}
int ans=solve(0,len-1);
//cout<<ans<<endl;
print(0,len-1);
}
------------------------------------------------------another easy code -----------------------------------
#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std;
int L,memo[100][100];
char S[101];
int solve(int s, int e){
if(s>e) return 0;
int &ret = memo[s][e];
if(ret==-1){
ret = 1+solve(s+1,e);
if(S[s]=='(' || S[s]=='['){
for(int i = s+1;i<=e;++i)
if((S[s]=='(' && S[i]==')') || (S[s]=='[' && S[i]==']'))
ret = min(ret,solve(s+1,i-1)+solve(i+1,e));
}
}
return ret;
}
void print(int s, int e){
if(s>e) return;
int best = solve(s,e);
if(1+solve(s+1,e)==best){
if(S[s]=='(' || S[s]==')'){
putchar('(');
putchar(')');
}else{
putchar('[');
putchar(']');
}
print(s+1,e);
return;
}
for(int i = s+1;i<=e;++i){
if(((S[s]=='(' && S[i]==')') || (S[s]=='[' && S[i]==']')) && best==solve(s+1,i-1)+solve(i+1,e)){
if(S[s]=='('){
putchar('(');
print(s+1,i-1);
putchar(')');
print(i+1,e);
}else{
putchar('[');
print(s+1,i-1);
putchar(']');
print(i+1,e);
}
return;
}
}
}
int main(){
scanf("%s",S);
L = strlen(S);
memset(memo,-1,sizeof(memo));
print(0,L-1);
putchar('\n');
return 0;
}
No comments:
Post a Comment