给定一个长度为 n 的字符串 s，字符串由 (, ), [, ]组成，问 s 是不是一个合法的括号序列。

合法的括号序列的定义是：

• 空串是一个合法的括号序列。

• 若 A 是一个合法的括号序列，则 (A), [A] 也是合法的括号序列。

• 若 A, B 都是合法的括号序列，则 AB 也是合法的括号序列。

输入格式

第一行一个整数 n。

接下来一行一个长度为 n的字符串 s。

输出格式

如果 s 是合法的括号序列，输出 Yes，否则输出 No。

样例输入1

10
[]([(())])

样例输出1

Yes

样例输入2

4
[(])

样例输出2

No

数据规模

对于所有数据，保证 n≤100000。

答案

#include <iostream>
#include <cstdio>
using namespace std;

const int N = 1e5+5;
char Stack[N];
int top=0;
char tmp;

int main(){
	
	int n;
	scanf("%d", &n);
	
	getchar();
	
	while(n--){
		scanf("%c", &tmp);
		if(tmp == '(' || tmp == '[')    //左括号就入栈
			Stack[++top] = tmp;
		else if(tmp == ')'){            //发现右括号就判断栈顶的左括号能否与之匹配
			if(Stack[top] == '(')
				--top;                  //匹配就把栈顶左括号出栈
			else{
				printf("No");           //不匹配就直接结束程序
				return 0;
			}
		}
		else{
			if(Stack[top] == '[')
				--top;
			else{
				printf("No");
				return 0;
			}
		}
		
	}
	if(top == 0)                  //最后这里还可能会出现一种情况：就是栈内只剩下左括号
		printf("Yes");            //当然，这肯定是非法的，所以我们还需要判断栈是否为空
	else                          //此时只有栈为空的情况下，输入的括号字符串序列才为合法的
		printf("No");
	
	return 0;
}