Seinfeld
Time Limit: 2000/1000 MS (Java/Others) Memory Limit: 32768/32768 K (Java/Others)
Total Submission(s): 1388 Accepted Submission(s): 685
Problem Description
I’m out of stories. For years I’ve been writing stories, some rather silly, just to make simple problems look difficult and complex problems look easy. But, alas, not for this one.
You’re given a non empty string made in its entirety from opening and closing braces. Your task is to find the minimum number of “operations” needed to make the string stable. The definition for being stable is as follows:
1. An empty string is stable.
2. If S is stable, then {S} is also stable.
3. If S and T are both stable, then ST (the concatenation of the two) is also stable.
All of these strings are stable: {}, {}{}, and {{}{}}; But none of these: }{, {{}{, nor {}{.
The only operation allowed on the string is to replace an opening brace with a closing brace, or visa-versa.
You’re given a non empty string made in its entirety from opening and closing braces. Your task is to find the minimum number of “operations” needed to make the string stable. The definition for being stable is as follows:
1. An empty string is stable.
2. If S is stable, then {S} is also stable.
3. If S and T are both stable, then ST (the concatenation of the two) is also stable.
All of these strings are stable: {}, {}{}, and {{}{}}; But none of these: }{, {{}{, nor {}{.
The only operation allowed on the string is to replace an opening brace with a closing brace, or visa-versa.
Input
Your program will be tested on one or more data sets. Each data set is described on a single line. The line is a non-empty string of opening and closing braces and nothing else. No string has more than 2000 braces. All sequences are
of even length.
The last line of the input is made of one or more ’-’ (minus signs.)
of even length.
The last line of the input is made of one or more ’-’ (minus signs.)
Output
For each test case, print the following line:
k. N
Where k is the test case number (starting at one,) and N is the minimum number of operations needed to convert the given string into a balanced one.
Note: There is a blank space before N.
k. N
Where k is the test case number (starting at one,) and N is the minimum number of operations needed to convert the given string into a balanced one.
Note: There is a blank space before N.
Sample Input
}{ {}{}{} {{{} ---
Sample Output
1. 2 2. 0 3. 1
/*题解：
上周考试题，离成功仅差一步之遥。
我用的是栈的写法，结果是Wrong，后来学习了别人的，发现思路也基本一样。
于是，我又仔细读读题，发现原因是数组开小了。改大后，果然AC.
明明是数组开小，却提示Wrong，难道不是应该RunTime吗？不过总的来说还是自己不细心啊。
*/
学习的代码：
( 基本思路：将配对的括号剔除，仅仅在栈中留下不配对的，可能是}}}}或{{{{或}}{{这几种类型，
求出'{'的个数t1,'}'的个数t2，最后需要替换的次数满足公式(t1+1)/2+(t2+1)/2 )
#include<cstdio>
#include<cstring>
int main()
{
int top,i,j,t1,t2,t=0,len;
char a[10010],s[10010];
while(scanf("%s",a))
{
if(a[0]=='-') break;
s[0]='#';
for(i=0,len=strlen(a),top=1; i<len; i++)
{
if(s[top-1]=='}'||s[top-1]=='#')
{
s[top++]=a[i];
}
else if(s[top-1]=='{')
{
if(a[i]=='{')
s[top++]=a[i];
else if(a[i]=='}')
top--;
}
}
printf("%d. ",++t);
if(top==1)
{
printf("0\n");
}
else
{
for(i=1,t1=t2=0; i<top; i++)
{
if(s[i]=='{') t1++;
if(s[i]=='}') t2++;
}
printf("%d\n",(t1+1)/2+(t2+1)/2);
}
}
return 0;
}
考试时自己写的AC代码：
（利用剩余的括号替换所满足的一个规律）
#include<cstdio>
#include<cstring>
int main()
{
int top,i,j,t=0,len;
char a[10010],s[10010];
while(scanf("%s",a))
{
if(a[0]=='-') break;
s[0]='#';
for(i=0,len=strlen(a),top=1; i<len; i++)
{
if(s[top-1]=='}'||s[top-1]=='#')
{
s[top++]=a[i];
}
else if(s[top-1]=='{')
{
if(a[i]=='{')
s[top++]=a[i];
else if(a[i]=='}')
top--;
}
}
printf("%d. ",++t);
if(top==1)
{
printf("0\n");
}
else
{
if(top%2==1) j++;
for(i=1,j=0; i<top; i+=2)
{
if(s[i]=='}'&&s[i+1]=='{')
j+=2;
else if(s[i]=='{'&&s[i+1]=='{')
j++;
else if(s[i]=='}'&&s[i+1]=='}')
j++;
}
printf("%d\n",j);
}
}
return 0;
}