← 返回题单

题单练习基础数据结构

← 上一题下一题 →

A5334 | $移动括号$

时间限制1s

内存限制128MB

通过 / 提交0/0

题目描述

给你一个只由左括号 (和右括号) 组成的字符串 $s$，长度为 $n$，并且 $n$ 是偶数；同时 $s$ 里有一半是左括号、另一半是右括号。 一次操作你可以： 选取字符串里的 一个 括号，把它挪到 最前面 或者 最后面 。 问：把 $s$ 变成 合法括号序列 ，至少需要多少次操作？ 合法括号序列的定义： - "()" 是合法； - 如果 $x$ 是合法，那么 "(" + x + ")" 也是合法； - 如果 $x,y$ 都合法，那么 x + y 也合法。 例如： "()()" 、 "(())" 、 "(())()" 都合法；而 ")(" 、 "()(" 不合法。 你需要回答 $t$ 组独立测试。

输入格式

第一行：一个整数 $t$，表示测试组数。 每组测试包含两行： - 第一行：一个偶数 $n$（$2 \le n \le 50$）； - 第二行：一个长度为 $n$ 的括号串 $s$，其中 ( 和 ) 的数量各为 $n/2$。

输出格式

对每组测试，输出一行一个整数：把 $s$ 变成合法括号序列的最少操作次数。

输入输出样例

输入 #1

4
2
)(
4
()()
8
())()()(
10
)))((((())

输出 #1

C++ 编辑器

输入

输出