Brackets sequence
Time Limit: 1.0 second
Memory Limit: 16 MB
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 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 | Ouput |
| ([(] | ()[()] |
Problem Author: Andrew Stankevich
Problem Source: 2001-2002 ACM Northeastern European Regional Programming Contest
Solution
终于过了这题……WA了两次。第一次是判断括号匹配的栈写错了，WA#9；第二次是没有考虑输入文件是空串的情况，WA#13并持续一周 -_-|||
而且这次也写垃圾了，长达80多行。好像原来的ural的内存限制是1000K？这样说我开一个100*100的string数组真是件奢侈的事情呢……
#include <iostream>
#include <fstream>
#include <string>
#include <cassert>
using namespace std;
ifstream fin("bracket.in");
ofstream fout("bracket.out");
string S;
inline bool isregular(int i,int j) //判断原串中的子串S[i...j]是否规则
{
if(j<i) return true;
else if(j==i) return false;
char stack[100]; int p=0;
for(int k=i;k<=j;k++)
{
if(p==0)
{
if(S[k]=='('||S[k]=='[') stack[p++]=S[k];
else return false;
}
else{
if(( stack[p-1]=='('&&S[k]==')' )||( stack[p-1]=='['&&S[k]==']' )) p--;
else if(S[k]==')'||S[k]==']') return false;
else stack[p++]=S[k];
}
}
return (p==0);
}
string s[100][100]; //[i][j]：按照最少原则添加括号规则化S[i...j]后得到的串
string memo(int i, int j) //记忆化搜索
{
if(s[i][j]!="") return s[i][j];
if(isregular(i,j)) //若S[i...j]本身就已经是规则的
{
s[i][j].assign(S,i,j-i+1);
return s[i][j];
}
if(i==j) //若当前串仅由一个字符组成
{
if(S[i]=='('||S[i]==')') s[i][j]="()";
else if(S[i]=='['||S[i]==']') s[i][j]="[]";
else assert(0);
return s[i][j];
}
string ans,tmp,tmp2;
unsigned size=UINT_MAX;
if(( S[i]=='('&&S[j]==')' )||( S[i]=='['&&S[j]==']' )) //若S[i...j]首尾配对，则只需使S[i+1...j-1]规则就得到一个解
{
ans=S[i]+memo(i+1,j-1)+S[j];
size=ans.size();
}
else if(( S[i]=='('&&S[j]!=')' )||( S[i]=='['&&S[j]!=']' )) //S[i...j]首尾不配对，与以上类似
{
ans=S[i]+memo(i+1,j);
if(S[i]=='(') ans=ans+')';
else if(S[i]=='[') ans=ans+']';
else assert(0);
size=ans.size();
}
else if(( S[i]!='('&&S[j]==')' )||( S[i]!='['&&S[j]==']' ))
{
ans=memo(i,j-1)+S[j];
if(S[j]==')') ans='('+ans;
else if(S[j]==']') ans='['+ans;
else assert(0);
size=ans.size();
}
for(int k=i;k<j;k++) //规则化S[i...k]和S[k+1...j]后合并得到的串
if(size>memo(i,k).size()+memo(k+1,j).size())
{
ans=memo(i,k)+memo(k+1,j);
size=memo(i,k).size()+memo(k+1,j).size();
}
return (s[i][j]=ans);
}
int main()
{
fin >> S;
if(S.size()==0)
{
fout << endl;
return 0;
}
fout << memo(0,S.size()-1) << endl;
return 0;
}
可能你对下面的文章也感兴趣：
