首页 > 专题系列 > Java解POJ > POJ 1141 Brackets Sequence [解题报告] Java
2013
11-09

POJ 1141 Brackets Sequence [解题报告] Java

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;
}

public String Answer(){
   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);
        System.out.println(m.Answer());
   }
}

  1. 我还有个问题想请教一下,就是感觉对于新手来说,递归理解起来有些困难,不知有没有什么好的方法或者什么好的建议?

  2. This write-up presents the gentle in which we can notice the fact. this is extremely wonderful one and gives in depth info.