平衡的判定

题目描述

给定一个由括号组成的字符序列，该序列只会出现六种字符，分别是 ( 、)、[ 、]、{、} 。

请判断输入的括号序列是否是平衡的。

平衡的定义如下：

• 空序列是平衡的；
• 如果某个括号序列 s 是平衡的，那么 [s]、 (s)、{s} 也是平衡的；
• 如果某两个括号序列 s 与 t 是平衡的，那么 s 拼接 t 后也是平衡的。

不能由上述规则得到的括号序列都是不平衡的。

输入格式

• 一个字符序列：表示输入的括号序列。

输出格式

• 如果是平衡的，输出 B，否则，输出 U。

数据范围

设 |S| 表示输入序列的长度，

• 对于 50% 的数据，1 ≤ |S| ≤ 1000，保证输入的括号序列只含有 ( 及 )；
• 对于 100% 的数据，1 ≤ n ≤ 1000000；

样例输入 #1

({})[]

样例输出 #1

B

样例输入 #2

{)(}

样例输出 #2

U

本题涉及的知识点从属于 GESP 六级，难度等级：⭐⭐

测试点分布