2013
11-09

# Brackets Sequence

Let us define a regular brackets sequence in the following way:

1. Empty sequence is a regular sequence.

2. If S is a regular sequence, then (S) and [S] are both regular sequences.

3. 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 a1 a2 … an is called a subsequence of the string b1 b2 … bm, if there exist such indices 1 = i1 < i2 < ... < in = m, that aj = bij for all 1 = j = n.

The input file contains at most 100 brackets (characters ‘(‘, ‘)’, ‘[' and ']‘) that are situated on a single line without any other characters among them.

Write to the output file a single line that contains some regular brackets sequence that has the minimal possible length and contains the given sequence as a subsequence.

([(]

()[()]

//* @author:
import java.util.*;
public class Main
{
//f[i][j]从位置i到位置j所需要插入的最小字符数，ans[i][j]表示i到j之间最少括号匹配字符

private char s[];
private int len;

private  int f[][];
private String ans[][];

public Main(char s[]){
this.s=s;
this.len=s.length;
f=new int[len][len];
ans=new String[len][len];
for(int i=0;i< len;i++)
Arrays.fill(ans[i],"");
dp();
}

public String[][] getAns(){
return ans;
}

return ans[0][len-1];
}

private void dp()
{
for (int i = 0; i < len; i++)
for (int j = i; j < len; j++)
{
f[i][j] = Integer.MAX_VALUE;
}
for (int i = len - 1; i >= 0; i--)
for (int j = i; j < len; j++)
if (i == j)
{
f[i][j] = 1;
if (s[i] == '(') ans[i][j] = "()";
if (s[i] == ')') ans[i][j] = "()";
if (s[i] == '[') ans[i][j] = "[]";
if (s[i] == ']') ans[i][j] = "[]";
}
else  if (j > i)
{

if (s[i] == '(' && s[j] == ')')
{
if (f[i + 1][j - 1] < f[i][j])
{
f[i][j] = f[i + 1][j - 1];
ans[i][j] = "(" + ans[i + 1][j - 1] + ")";
}
}
else if (s[i] == '[' && s[j] == ']')
{
if (f[i + 1][j - 1] < f[i][j])
{
f[i][j] = f[i + 1][j - 1];
ans[i][j] = "[" + ans[i + 1][j - 1] + "]";
}
}
for (int k = i; k < j; k++)
{
if (f[i][k] + f[k + 1][j] < f[i][j])
{
f[i][j] = f[i][k] + f[k + 1][j];
ans[i][j] = ans[i][k] + ans[k + 1][j];
}
}
}
}

public static void main(String[] args)
{
Scanner sc = new Scanner(System.in);
String ss=sc.nextLine();
if(ss.length()==0){
System.out.println();
}
ss.replaceAll(" ", "");
char s[]=ss.toCharArray();

Main m=new Main(s);
}