最长括号匹配

题目描述

对一个由 $\boldsymbol{(}$，$\boldsymbol{)}$，$\boldsymbol{[}$，$\boldsymbol{]}$ 括号组成的字符串，求出其中最长的括号匹配子串。具体来说，满足如下条件的字符串成为括号匹配的字符串：

• $\boldsymbol{()}$，$\boldsymbol{[]}$ 是括号匹配的字符串。

2.若 $A$ 是括号匹配的串，则 $\boldsymbol{(}A\boldsymbol{)}$，$\boldsymbol{[}A\boldsymbol{]}$是括号匹配的字符串。

3.若 $A$，$B$ 是括号匹配的字符串，则 $AB$ 也是括号匹配的字符串。

例如：$\boldsymbol{()}$，$\boldsymbol{[]}$，$\boldsymbol{([])}$，$\boldsymbol{()()}$都是括号匹配的字符串，而 $\boldsymbol{][,[(])}$ 则不是。

字符串 $A$ 的子串是指由 $A$ 中连续若干个字符组成的字符串。

例如：$A$，$B$，$C$，$ABC$，$CAB$，$ABCABC$ 都是$ABCABC$ 的子串，空串是任何字符串的子串。

输入格式

输入一行，为一个仅由 $\boldsymbol{()[]}$ 组成的非空字符串。

输出格式

输出也仅有一行，为最长的括号匹配子串。若有相同长度的子串，输出位置靠前的子串。

样例 #1

样例输入 #1

([(][()]]()

样例输出 #1

[()]

样例 #2

样例输入 #2

())[]

样例输出 #2

()

提示

【数据范围】

对 $20\%$的数据，字符串长度 $\le 10^{2}$.

对 $50\%$ 的数据，字符串长度 $\le10^{4}$.

对 $100\%$的数据，字符串长度 $\le 10^{6}$ .

# 最长括号匹配

## 题目描述

对一个由 $\boldsymbol{(}$，$\boldsymbol{)}$，$\boldsymbol{[}$，$\boldsymbol{]}$ 括号组成的字符串，求出其中最长的括号匹配子串。具体来说，满足如下条件的字符串成为括号匹配的字符串：

- $\boldsymbol{()}$，$\boldsymbol{[]}$ 是括号匹配的字符串。

2.若 $A$ 是括号匹配的串，则 $\boldsymbol{(}A\boldsymbol{)}$，$\boldsymbol{[}A\boldsymbol{]}$是括号匹配的字符串。

3.若 $A$，$B$ 是括号匹配的字符串，则 $AB$ 也是括号匹配的字符串。

例如：$\boldsymbol{()}$，$\boldsymbol{[]}$，$\boldsymbol{([])}$，$\boldsymbol{()()}$都是括号匹配的字符串，而 $\boldsymbol{][,[(])}$ 则不是。

字符串 $A$ 的子串是指由 $A$ 中连续若干个字符组成的字符串。

例如：$A$，$B$，$C$，$ABC$，$CAB$，$ABCABC$ 都是$ABCABC$ 的子串，空串是任何字符串的子串。

## 输入格式

输入一行，为一个仅由 $\boldsymbol{()[]}$ 组成的非空字符串。

## 输出格式

输出也仅有一行，为最长的括号匹配子串。若有相同长度的子串，输出位置靠前的子串。

## 样例 #1

### 样例输入 #1

([(][()]]()

### 样例输出 #1

[()]

## 样例 #2

### 样例输入 #2

())[]

### 样例输出 #2

()

## 提示

【数据范围】

对 $20\%$的数据，字符串长度 $\le 10^{2}$.

对 $50\%$ 的数据，字符串长度 $\le10^{4}$.

对 $100\% $的数据，字符串长度 $\le 10^{6}$ .