括号匹配hdu5479

Problem Description
Given a parentheses sequence consist of ‘(‘ and ‘)’, a modify can filp a parentheses, changing ‘(‘ to ‘)’ or ‘)’ to ‘(‘.

If we want every not empty substring of this parentheses sequence not to be “paren-matching”, how many times at least to modify this parentheses sequence?

For example, “()”,”(())”,”()()” are “paren-matching” strings, but “((“, “)(“, “((()” are not.

Input
The first line of the input is a integer T, meaning that there are T test cases.

Every test cases contains a parentheses sequence S only consists of ‘(‘ and ‘)’.

1≤|S|≤1,000

Output
For every test case output the least number of modification.

Sample Input

3
()
((((
(())

Sample Output

1
0
2

题意：给你一组只由’(‘和’)’组成的字符串，你可以改变左右括号，问你需要改几个使左右括号不匹配。

解题思路：其实就是找原来有几组括号匹配，把这几组改了就不匹配了。
熟悉下STL中栈的使用。

AC代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36

#include <cstdio>
#include <cstring>
#include <stack>
using namespace std;
int ()
{
    int T;
    scanf("%d%*c", &T);
    while(T--)
    {
        char s[1010];
        gets(s);
        stack<char>q;
        int cnt=0;
        for(int i=0; i<strlen(s); i++)
        {
            if(q.empty()) q.push(s[i]);
            else
            {
                char a=q.top();
                if(a == '(' && s[i] == ')')
                {
                    cnt++;
                    q.pop();
                }
                else q.push(s[i]);
            }
        }
        printf("%dn",cnt);
    }
    return 0;
}