2016湖南省赛----G - Parenthesis （括号匹配）
Bobo has a balanced parenthesis sequence P=p p …p of length n and q questions.
The i-th question is whether P remains balanced after p and p swapped. Note that questions are individual so that they have no affect on others.
Parenthesis sequence S is balanced if and only if:
1. S is empty;
2. or there exists balanced parenthesis sequence A,B such that S=AB;
3. or there exists balanced parenthesis sequence S' such that S=(S').
Input
The input contains at most 30 sets. For each set:
The first line contains two integers n,q (2≤n≤10 ,1≤q≤10 ).
The second line contains n characters p p …p .
The i-th of the last q lines contains 2 integers a ,b (1≤a ,b ≤n,a ≠b ).
Output
For each question, output " Yes" if P remains balanced, or " No" otherwise.
Sample Input
4 2
(())
1 3
2 3
2 1
()
1 2
Sample Output
No
Yes
No
題意： 给出一个已经匹配的括号序列，任意的交换两个位置的括号，判断是否匹配，如果匹配输出 Yes 不匹配输出 No。
输入一个n一个m，n表示括号序列的长度，m代表下面给出m种交换方式，对每一种方式进行判断。
思路：
可将该问题分为三类：
1. 若交换的两个位置的括号相同 则可直接输出 Yes；
2.若后面的左括号与前面的右括号交换，则可直接输出Yes. 因为一开始是平衡串, 如果左边的字符')'与右边的'('交换,那么此时交换的两个必能匹配为一对。
3.若后面的右括号与前面的左括号交换，则可根据括号匹配问题进行判断.
代码实现：
#include <iostream>
#include <string.h>
#include <string>
#include <stdio.h>
#include <algorithm>
#include <stdio.h>
#include <stack>
using namespace std; char s1[]={}; int main(){
int n,m;
while(~scanf("%d%d",&n,&m)){
getchar();
scanf("%s",s1);
int a,b;
for(int i=;i<=m;i++){
char c;
scanf("%d%d",&a,&b);
if(a>b)
swap(a,b);
if(s1[a-]==s1[b-]||s1[b-]=='('){ //第一种情况与第二种情况
printf("Yes\n");
continue;
}
swap(s1[a-],s1[b-]);
int sum = ;
for(int i = ;i<n;i++){ // 第三种情况的判断
if(s1[i]=='(')
sum++;
if(s1[i]==')')
sum--;
if(sum<)
break;
}
if(sum==)
printf("Yes\n");
else
printf("No\n");
swap(s1[a-],s1[b-]); //将字符串还原
}
}
return ;
}