问题 4803 --2. 括号匹配 (pair)

4803: 2. 括号匹配 (pair)

题目描述

  在由{a,b,..., z,A,B ,... ,Z} 组成的字符串中,我们约定:大写字母 {A,B ,... ,Z} 相当于括号作用 , 这 26 个字母形成 13 对括号,(A,Z) 、(B,Y) , ..., (M,N),每对中的第一个字母表示左括号“ (”, 第二个字母表示右括号“ )”。
和我们的习惯思维一样,一个正确的表达式是指左括号和右括号要一一对应,也就是说所有的左括号都应有一个右括号和它配对, 而且如果一个左括号在某一个配对的括号的中间,那么跟它配对的右括号也必须在该配对的括号中间。
例如 AabcZBBefYeY是一个匹配的表达式。而 AabcBZY不是,因为 (B,Y) 中 B 在(A,Z) 的中间,而 Y不在。同样AabcZZA也不是,因为第二个 Z 没有配对的 A。
小写字母 {a,b, ..., z} 不表示括号,可以出现在任何地方。你的任务是判断给定的字符串中括号是否是匹配的?

输入

包括多组测试数据,
每组测试数据第一行是一个整数 N,表示字母的个数,
接下来第二行是 N个字母。

输出

对于每组测试数据,输出 1 或 0,1 表示匹配, 0 表示不匹配。

样例输入输出

输入#1 复制
12
AabcZBBefYeY
输出#1 复制
1

提示

【数据范围】
50%的数据 N<=1000 
100%的数据 N<=1000000

序号 标题 作者 发表时间 费用 订购数 操作