第 2 题括号值比较 (`compareparenthesesva`)

CSP-S 复赛模拟赛 25 · 时间限制 1.0 s · 空间限制 256 MB · 104 个测试点 · 全文比较（过滤行末空格及文末回车）

本题使用文件输入输出：输入文件 compareparenthesesva.in，输出文件 compareparenthesesva.out。

按照署名—非商业性使用—相同方式共享 4.0 协议国际版进行授权。

题目描述

使用左括号（和右括号）构成的字符串中，所谓"正确括号序列"定义如下：

仅包含一对括号的字符串 () 是一个正确的括号序列。
若 $X$ 是一个正确的括号序列，则用括号将 $X$ 包起来形成的 $(X)$ 也是一个正确的括号序列。
若 $X$ 和 $Y$ 都是正确的括号序列，则将它们连接而成的 $XY$ 也是一个正确的括号序列。
所有正确的括号序列都只能通过以上三条规则构造出来。

例如，((()(()))) 和 (())()() 是正确的括号序列，而 ()() 或 ))((() 都不是正确的括号序列。

对于一个正确的括号序列 $X$ ，我们定义其括号值 $f[X]$ ，具体如下：

$f(()) = 1$ ；
若 $X$ 是一个正确的括号序列，则 $f((X)) = 2 \times f[X]$ ；
若 $X$ 和 $Y$ 是正确的括号序列，则 $f[XY] = f[X] + f[Y]$ 。

我们来看几个例子：

$f(()) = 1$ ；
$f((())) = 2 \times f[()] = 2 \times 1 = 2$ ；
$f(())() = f[()] + f[()] = 1 + 1 = 2$ ；
$f(()()) = f[()] + f[()] = 1 + 2 = 3$ ；
$f((()())) = 2 \times f[()()] = 2 \times 2 = 4$ ；
$f(((()))) = 2 \times f[((()))] = 2 \times 2 = 4$ ；
$f(()(())) = f[()] + f[(() )] = 1 + 2 = 3$ ；
$f((()()))(()) = f[((()()))] + f[(())] = 4 + 3 = 7$ 。

你的任务是读取两个正确的括号序列 $A$ 和 $B$ ，比较它们的括号值 $f[A]$ 与 $f[B]$ 。

也就是说，判断 $f[A] = f[B]$ 、 $f[A] < f[B]$ 还是 $f[A] > f[B]$ 。

一个输入中会包含 $T$ 个测试用例。

输入格式

第一行包含一个整数 $T$ ，表示测试用例的个数。

接下来的 $T$ 个测试用例中，每个测试用例由如下两行组成：

第一行为括号序列 $A$ ；
第二行为括号序列 $B$ 。

输出格式

对于每个测试用例，输出一行结果：

若 $f[A] = f[B]$ ，输出等号 =；
若 $f[A] < f[B]$ ，输出小于号 <；
若 $f[A] > f[B]$ ，输出大于号 >。

样例

样例 1

输入：

1
(())
()()

输出：

样例 2

输入：

1
()()()
(())

输出：

样例 3

输入：

2
((()))
()(()
(((())))
()()()()()

输出：

>
>

提示

样例 1 说明

$f[A] = f((())) = 2$ ， $f[B] = f(()()) = 2$ ，因此 $f[A] = f[B]$ 。

样例 2 说明

$f[A] = f(()()()) = 3$ ， $f[B] = f(((() ))) = 4$ ，因此 $f[A] < f[B]$ 。

样例 3 说明

第一个测试用例中， $f[A] = f[((()))] = 4$ ， $f[B] = f[()(())] = 3$ ，因此 $f[A] > f[B]$ 。
第二个测试用例中， $f[A] = f[(((())))] = 8$ ， $f[B] = f[()()()()()] = 5$ ，因此 $f[A] > f[B]$ 。

约束条件

$1 \le T \le 10$
$A$ 和 $B$ 都是正确的括号序列。
一个输入中所有测试用例中 $A$ 的总长度之和不超过 $3 \times 10^6$ 。
一个输入中所有测试用例中 $B$ 的总长度之和不超过 $3 \times 10^6$ 。

子任务

（3 分） $A$ 和 $B$ 的长度都不超过 6。
（23 分） $A$ 和 $B$ 的长度都不超过 50。
（13 分）
- 括号数量相等，且所有右括号都出现在所有左括号之后的括号序列，称为"简单括号序列"。
  - 例如 ()、(())、((()))、((((())))) 都是简单括号序列。
  - $A$ 和 $B$ 都是由长度各不相同的多个简单括号序列拼接而成的。
  - 比如 ()(())、(((()))()((()))) 是符合的例子。
  - (()())(()) 也是由简单括号序列拼接而成，但因为包含了两段长度相同的简单括号序列 (())，因此在此子任务中不会出现这种情况。
（61 分）无额外约束条件。

第 2 题 括号值比较 (compareparenthesesva)