题目描述

给定一个合法的括号序列，要求通过对其进行若干次（或不进行）的相邻合法括号子序列的交换，得到字典序最大的括号序列。每个合法的括号序列由左右括号组成，并且是有效的括号匹配。

解题思路

这道题的核心在于递归拆分括号子序列，然后对子序列进行字典序排序。我们可以将括号表达式看作是树状的结构，递归处理括号内部的子结构并保证排序合并后的结果是字典序最大的表达式。

思路步骤

题目内容

有效括号表达式定义:

$1$、空串和$()$均为有效表达式。

$2$、当$A、B为$有效表达式时，则$(A)、AB$也均是有效的括号表达式，比如:$A$为$()$，则 $()()和$(())$均为有效括号表达式。

括号表达式的值:左括号用$1$表示，右括号用$0$表示，该二进制序列对应的值即为括号表达式的值。

现给定一个有效括号表达式，对其中任意两个相邻的子"有效表达式”进行交换，求在任意次数(包含0次)的交换之后，能够得到的值最大的括号表达式。

说明:

$1$、表达式自身是有效表达式。

$2$、交换的必须是相邻且有效的。

输入描述

给定一个有效括号表达式，只包含左右括号"()”。 表达式的长度不超过$60$。

输出描述

在任意次数(包含$0$次)的交换之后，能够得到的值最大的括号表达式

样例1

输入

((()(())))	

输出

(((())()))

说明

将在$s[2]$出现的有效表达式“$()$”和在$s[4]$出现的有效表达式$(())$进行交换。 对应二进制: $11\ 10\ 1100\ 00$转换为$11\ 1100\ 10\ 00$

样例2

输入

()()

输出

()()

说明

无需交换，交换后也一样

样例3

输入

()(())((()(())))

输出

(((())()))(())()

说明

交换$s[8-9]$与$s[10-13]$，得到$()(())(((())()))$

交换$s[2-5]$与$s[6-15]$，得到$()(((())()))(())$

交换$s[0-1]$与$s[2-11]$，得到$(((())()))()(())$

交换$s[10-11]$与$s[12-15]$，得到$(((())()))(())()$