UVALive 7454 Parentheses （栈+模拟）

Parentheses

题目链接：

http://acm.hust.edu.cn/vjudge/contest/127401#problem/A

Description

http://7xjob4.com1.z0.glb.clouddn.com/9cf04e507e13a41d77bca3a75bb51e19

Input

The first line contains an integer T ≤ 10 indicating the number of test cases. The first line of each test case contains an even integer n, 2 ≤ n ≤ 100, indicating the length of P. Next, the second line gives the sequence P.

Output

For each test case, output the minimum number of reverse operations that make P well-formed.

Sample Input

3 18 (()())))(((((())(( 2 () 8 (()))()(

Sample Output

4 0 2
##题意：括号匹配问题，求最少的翻转(左右括号转换)操作使得原串合法.
##题解：栈模拟判断当前串是否合法： ①. 如果当前是'('，直接入栈. ②. 如果当前是')'，如果栈非空，则弹出一个'('; 如果栈空就把当前的')'变成'('入栈. 最后的结果栈中肯定全是'('，那么把其中的一半变成')'即可. 与[HDU 5831](http://www.cnblogs.com/Sunshine-tcf/p/5761816.html)类似.
##代码： ``` cpp #include #include #include #include #include #include #include #include #include #include #include #define LL long long #define eps 1e-8 #define maxn 1010 #define mod 100000007 #define inf 0x3f3f3f3f #define mid(a,b) ((a+b)>>1) #define IN freopen("in.txt","r",stdin); using namespace std;

char str[maxn];
stack s;

int main(int argc, char const *argv[])
{
//IN;

int t; cin >> t;
while(t--)
{
    int n; scanf("%d", &n);
    while(!s.empty()) s.pop();
    scanf("%s", str);

    int ans = 0;
    for(int i=0; i<n; i++) {
        if(str[i] == '(') {
            s.push('(');
        } else {
            if(!s.empty()) s.pop();
            else {
                ans++;
                s.push('(');
            }
        }
    }

    ans += s.size() / 2; 

    printf("%d
", ans);
}

return 0;

}