cf1214C C. Bad Sequence

C. Bad Sequence
time limit per test1 second
memory limit per test512 megabytes
inputstandard input
outputstandard output
Petya’s friends made him a birthday present — a bracket sequence. Petya was quite disappointed with his gift, because he dreamed of correct bracket sequence, yet he told his friends nothing about his dreams and decided to fix present himself.

To make everything right, Petya is going to move at most one bracket from its original place in the sequence to any other position. Reversing the bracket (e.g. turning “(” into “)” or vice versa) isn’t allowed.

We remind that bracket sequence s is called correct if:

s is empty;
s is equal to “(t)”, where t is correct bracket sequence;
s is equal to t1t2, i.e. concatenation of t1 and t2, where t1 and t2 are correct bracket sequences.
For example, “(()())”, “()” are correct, while “)(” and “())” are not. Help Petya to fix his birthday present and understand whether he can move one bracket so that the sequence becomes correct.

Input
First of line of input contains a single number n (1≤n≤200000) — length of the sequence which Petya received for his birthday.

Second line of the input contains bracket sequence of length n, containing symbols “(” and “)”.

Output
Print “Yes” if Petya can make his sequence correct moving at most one bracket. Otherwise print “No”.

Examples
input
2
)(
output
Yes
input
3
(()
output
No
input
2
()
output
Yes
input
10
)))))(((((
output
No
Note
In the first example, Petya can move first bracket to the end, thus turning the sequence into “()”, which is correct bracket sequence.

In the second example, there is no way to move at most one bracket so that the sequence becomes correct.

In the third example, the sequence is already correct and there’s no need to move brackets.
题意： 给出字符串长度，和一段只含左右括号的字符，并定义该字符序列是好的条件为括号匹配或者只通过移一个括号，能使其完全匹配，如果满足上述条件，则输出Yes，否则输出No。
思路： 首先对n进行奇偶判断，奇数直接输出No，因为左括号数不等于右括号数，如果为偶数则用栈去模拟括号是否匹配（遇到左括号入栈，遇到右括号且栈不为空出栈），同时记录左括号数目和右括号数目，如果左括号数目不等于右括号数目，直接输出No，如果相等，再判断栈里的剩余左括号数目，如果其数目小于等于1，则输出Yes，否则输出No。详情看代码和注释。

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N = 2e5 + 10;
char s[N];
int main() {
	int n;
	scanf("%d", &n);
	scanf("%s", s);
	if (n % 2 == 1) printf("No\n");
	else {
		stack<char> st;
		int num = 0, num1 = 0;
		for (int i = 0; i < n; i++) {
			if (s[i] == '(') st.push(s[i]); // 遇到左括号，直接入栈 
			else if (s[i] == ')' && !st.empty()) st.pop(); // 遇到右括号且当前栈不为空，出栈 
			if (s[i] == '(') num++; // 记录左括号数目 
			else num1++; // 记录右括号数目
		}
		if (st.empty() && num == num1) printf("Yes\n"); // 栈为空且左右括号数目相等说明括号匹配 
		else {
			if (st.size() > 1 || num != num1) printf("No\n"); // 如果栈中剩余左括号数目大于1或左右括号数目不相等，输出No 
			else printf("Yes\n"); // 否则输出Yes 
		}
	}
	return 0; 
}