RYIP在线题库
首 页   >   习题练习   >   提交
Problem2014--K13673 合理的栈顺序2

2014: K13673 合理的栈顺序2

[Creator : ]
Time Limit : 1.000 sec  Memory Limit : 128 MB

【 Description 】

题目是这样的:给定n对小括号,问给出的一个括号序列是否为一种合理的括号序列,以及n对小括号能够组成的合理括号序列有多少种?规定合理的括号序列为:
①:空序列是合理的。
②:如果A和B都是合理的括号序列,那么AB也是合理的。
③:如果A是合理的,那么(A)也是合理的。
比如,给定两对小括号,那么:()()与(())都是合理的。
对于给定的序列是否是合理的,小丁一眼就看出来了,但是对于n对小括号,有多少种合理的括号序列,小丁就有点被难到了,你能帮助小丁处理这个问题么?

【 Input 】

输入共两行:
第一行:一个整数n,表示小括号对数。
第二行:由n个小括号组成的括号序列,输入只包含小括号,不存在其他字符。

【 Output 】

输出共两行:
第一行:输出”YES”或”NO”。如果输入的括号序列是合理的,输出”YES”,否则输出”NO”。
第二行:输出n对小括号可以组成的合理括号序列的种数。
输入样例1:
1
()
输出样例1:
YES
1
输入样例2:
2
))((
输出样例2:
NO
2

【 Sample Input 】

1
()

【 Sample Output 】

YES
1

【HINT】

说明
【输入输出样例 1 说明】 
样例1说明:1对小括号。
很明显()是合理的,1对括号只有1种合理的括号序列为:()
样例1说明:2对小括号。
很明显))((是不合理的,按照给定左右括号顺序不能组成合理的()
2对括号只有2种合理的括号序列,分别为:()()与(())。
【数据规模与约定】 
数据范围1 <= N <=20。

【 Source/Category 】

 TX