#P1241. 括号序列

括号序列

题目描述

定义如下规则:

  1. 空串是「平衡括号序列」
  2. 若字符串 SS 是「平衡括号序列」,那么 [S]\texttt{[}S\texttt](S)\texttt{(}S\texttt) 也都是「平衡括号序列」
  3. 若字符串 AABB 都是「平衡括号序列」,那么 ABAB(两字符串拼接起来)也是「平衡括号序列」。

例如,下面的字符串都是平衡括号序列:

  • ()[](())([])()[]()[()]

而以下几个则不是:

  • ([])(())([()

现在,给定一个仅由 ()[]构成的字符串 ss,请你按照如下的方式给字符串中每个字符配对:

  1. 从左到右扫描整个字符串。
  2. 对于当前的字符,如果它是一个右括号,考察它与它左侧离它最近未匹配的的左括号。如果该括号与之对应(即小括号匹配小括号,中括号匹配中括号),则将二者配对。如果左侧未匹配的左括号不存在或与之不对应,则其配对失败。

配对结束后,对于 ss 中全部未配对的括号,请你在其旁边添加一个字符,使得该括号和新加的括号匹配。

输入格式

输入只有一行一个字符串,表示 ss

输出格式

输出一行一个字符串表示你的答案。

([()

()[]()

([)
()[]()

提示

数据规模与约定

对于全部的测试点,保证 ss 的长度不超过 100100,且只含 ()[] 四种字符。