HDU 3351：Seinfeld

Title source

http://acm.hdu.edu.cn/showproblem.php?pid=3351

Problem description

I have no story . these years , I've been writing stories , Some stories are stupid , Just to make simple problems look difficult and complex problems look easy .
By opening and closing braces , You will get a complete non empty string . Your task is to find the minimum required to stabilize the string “ operation ” Count . The definition of stability is as follows ：

1. Empty strings are stable .
2. If S Stable , be {S} And stable .
3. If S and T All stable , be ST（ The series connection of the two ） And stable .

All these strings are stable ：{},{} {} and { {} {}}; But none of this is ：} {,{ {} { or {} {.
The only allowed operation on a string is to replace an open curly bracket with a closed curly bracket , vice versa .

The input values

Your program will be tested on one or more datasets . Each data set is described in one row . This line is a non empty string consisting of open and closed parentheses , That's it . At most 2000 Two curly brackets . All sequences are equal in length .
The last line of input consists of one or more “-”（ minus sign ） form .

Output

For each test case , Print the following lines ：
k. N
among k Is the test case number （ from 1 Start ）,N Is the minimum operand required to convert a given string to a balanced string .
Be careful ：N There is a space in front .

Sample input

} {
     
{
    } {
    } {
    } 
{
    {
    {
    } 
-

Sample output

1. 2 
2. 0 
3. 1

Code

#include<iostream>
#include<stdio.h>
#include<stdlib.h>
#include<algorithm>
#include<string.h>
#include<math.h>
#include<inttypes.h>
using namespace std;
#include<stack>
int main()
{
    
	string str;int t = 1;
	while(cin>>str && str[0]!='-'){
    
		int i = 0,ans = 0;stack<char>S1,S2;//S1 Push the '{' S2 Push the '}'
		while(str[i]!='\0'){
    
            if(str[i] == '}'){
    
            	if(!S1.empty())S1.pop();  // The match is successful  S1 Pop up a '{'
            	else S2.push('}');// Can't match   take '}' Push the S2 in 
            }
            else{
      
				S1.push('{'); // If the input is '{'  Press it in S1 in 
            }
            i++;// Scan back 
		}
		while(S1.size()>=2){
    ans++;S1.pop();S1.pop();} // If S1 The length of alpha is greater than or equal to alpha 2  Adopt the principle of proximity to match   such as '{
    {' Turn into '{}' ans++
		while(S2.size()>=2){
    ans++;S2.pop();S2.pop();} // If S2 The length of alpha is greater than or equal to alpha 2  Adopt the principle of proximity to match   such as '}}' Turn into '{}' ans++
		// After matching nearby   If S1 S2 Not empty yet   The explanation can only be '}' '{'  This requires two changes  -->'{}'  So add the sum of the lengths of the two stacks 
		ans += S1.size() + S2.size();
		cout<<t<<". "<<ans<<endl;
		t++;
	}
	return 0;
}