ISourceCode

Make the frequent cases fast and the rare case correct

For some given sequence of characters ‘(‘, ‘)’, ‘[‘, and ‘]’ , Find the shortest possible regular brackets sequence, that contains the given character sequence as a sub sequence.

An example of regular bracket sequence is

(), [], (()), ([]), ()[], ()[()]

and the following are not regular bracket sequence

(, [, ), )(, ([)], ([(]

For some given sequence of characters ‘(‘, ‘)’, ‘[‘, and ‘]’ , Find the shortest possible regular brackets sequence, that contains the given character sequence as a sub sequence.

That means

for a given input

([(]

Find an output sequence like this

()[()]

which is the shortest regular bracket sequence that contains the input.

using System;
using System.Collections.Generic;
using System.Collections;
using System.Text;

namespace BracketSequence
{
    class Bracket
    {
        private String[] input;
        private int len;
        private int[,] flag = new int[100, 100];
        private String[,] output = new String[100, 100];

        public Bracket(String[] value)
        {
            this.input = value;
            this.len = input.Length;
            int[,] flag = new int[len, len];
            String[,] output = new String[len, len];
            for (int i = 0; i < len; i++)
                output.SetValue("", i, 0);

            MinimalBracketSeq();
        }

        public String FindSequence()
        {
            return output[0, len - 1];
        }

        private void MinimalBracketSeq()
        {
            for (int i = 0; i < len; i++)
            {
                for (int j = i; j < len; j++)
                {
                    flag[i, j] = int.MaxValue;
                }
            }
            for (int i = len - 1; i >= 0; i--)
            {
                for (int j = i; j < len; j++)
                {
                    if (i == j)
                    {
                        flag[i, j] = 1;
                        if (input[i].Contains("("))
                            output.SetValue("()", i, j);
                        if (input[i].Contains(")"))
                            output.SetValue("()", i, j);
                        if (input[i].Contains("["))
                            output.SetValue("[]", i, j);
                        if (input[i].Contains("]"))
                            output.SetValue("[]", i, j);
                    }
                    else if (j > i)
                    {

                        if (input[i].Contains("(") && input[j].Contains(")"))
                        {
                            if (flag[i + 1, j - 1] < flag[i, j])
                            {
                                flag[i, j] = flag[i + 1, j - 1];
                                output[i, j] = "(" + output[i + 1, j - 1] + ")";
                            }
                        }
                        else if (input[i].Contains("[") && input[j].Contains("]"))
                        {
                            if (flag[i + 1, j - 1] < flag[i, j])
                            {
                                flag[i, j] = flag[i + 1, j - 1];
                                output[i, j] = "[" + output[i + 1, j - 1] + "]";
                            }
                        }
                        for (int k = i; k < j; k++)
                        {
                            if (flag[i, k] + flag[k + 1, j] < flag[i, j])
                            {
                                flag[i, j] = flag[i, k] + flag[k + 1, j];
                                output[i, j] = output[i, k] + output[k + 1, j];
                            }
                        }
                    }
                }
            }
        }
    }
    class Program
    {
        public static void Main(String[] args)
        {
            String[] input = new String[] { "(", "[", "(", "]" };
            Bracket objBkt = new Bracket(input);
            Console.WriteLine("The input is ([(]");
            Console.WriteLine("The shortest regular bracket sequence is");
            Console.WriteLine(objBkt.FindSequence());
            Console.ReadLine();
        }
    }
}

OUTPUT:

tSequence\BracketSequence\bin\Debug>BracketSequence.exe
The input is ([(]
The shortest regular bracket sequence is
()[()]

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s

%d bloggers like this: