首页 > 代码库 > POJ 1141 Brackets Sequence

POJ 1141 Brackets Sequence

2024-07-16 07:40:33   229人阅读

Brackets Sequence
Time Limit: 1000MS Memory Limit: 65536K
Total Submissions: 25132 Accepted: 7083 Special Judge

Description

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.

Input

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

Output

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.

Sample Input

([(]

Sample Output

()[()]

#include <iostream>#include <stack>#include <cstring>#include <cstdio>#include <string>#include <algorithm>using namespace std;#define INF 0x3fffffff#define N 105#define ms(a, val) memset(a, val, sizeof(a))int dp[N][N], p[N][N];string s;/*if(s[i,j] == "[]" || "()")    dp[i][j] = dp[i+1][j-1]dp[i][j] = min(dp[i][j], dp[i][k] + dp[k+1][j]) i<=k<j*/void print(int i, int j){    if (i > j)    {        return;    }    if (i == j)    {        if (s[i] == ‘(‘ || s[j] == ‘)‘)            cout << "()";        else            cout << "[]";        return;    }    if (p[i][j] == -1)    {        cout << s[i];        print(i + 1, j - 1);        cout << s[j];    }    else    {        print(i, p[i][j]);        print(p[i][j] + 1, j);    }}int main(){    int n, t;    while (getline(cin, s))    {        n = s.length();        ms(dp, 0);        for (int i = 0; i < n; i++)        {            dp[i][i] = 1;        }        for (int m = 1; m < n; m++)        {            for (int i = 0, j = m; j < n; i++, j++)            {                dp[i][j] = INF;                p[i][j] = -1;                if ((s[i] == ‘(‘ && s[j] == ‘)‘) || (s[i] == ‘[‘ && s[j] == ‘]‘))                {                    dp[i][j] = dp[i + 1][j - 1];                }                for (int k = i; k < j; k++)                {                    t = dp[i][k] + dp[k + 1][j];                    if (t < dp[i][j])                    {                        dp[i][j] = t;                        p[i][j] = k;                    }                }            }        }        print(0, n - 1);        cout << endl;    }    return 0;}

 


联系
我们