← 返回题目列表

Codeforces · 1452/C

C. 两个括号

中文机器翻译题面 查看原题

给定一个字符串 $$$s$$$,由两种类型的括号组成:'(', ')', '[' 和 ']'。

如果字符串属于以下类型之一,则称为常规括号序列 (RBS):

- 空字符串;
- '(' + RBS + ')';
- '[' + RBS + ']';
- 苏格兰皇家银行 + 苏格兰皇家银行。

其中 plus 是两个字符串的串联。

在一步操作中,您可以选择字符串 $$$s$$$ 的非空子序列(不一定是连续的),该子序列是 RBS,将其从字符串中删除并连接其余部分而不更改顺序。

您最多可以执行多少步?

输入

第一行包含一个整数 $$$t$$$ ($$$1 \le t \le 1000$$$) — 测试用例的数量。

接下来的 $$$t$$$ 行均包含一个非空字符串,仅由字符“(”、“)”、“[”和“]”组成。所有测试用例的字符串总长度不超过 $$$2 \cdot 10^5$$$。

输出

对于每个测试用例,打印一个整数 - 您可以对给定字符串 $$$s$$$ 执行的最大移动次数。

示例

输入 #1

5
()
[]()
([)]
)]([
)[(]

输出 #1

1
2
2
0
1

注意

在第一个示例中,您可以删除整个字符串。

在第二个示例中,您可以先删除 $$$1$$$ 和 $$$2$$$ 位置上的括号:“[]()”,然后留下“()”。之后您可以将其全部删除。你可以从一开始就擦除整个字符串,但你会得到一步而不是两步。

在第三个示例中,您可以先擦除 $$$1$$$ 和 $$$3$$$ 位置上的括号:“([)]”。它们组成了RBS“()”。然后留下“[]”,这样你就可以把它整个删除了。

在第四个示例中,没有 RBS 子序列,因此您根本无法执行移动。

在第五个示例中,您可以删除位置 $$$2$$$ 和 $$$4$$$ 上的括号:“)[(]”并得到“)(”作为结果。您不能从中删除任何内容。