#P9702. 括号序列
括号序列
括号序列
题目描述
给定仅含 (、)、? 的字符串 ,保证长度为偶数。请将每个 ? 替换为左括号或右括号,使整个字符串为合法括号序列,且它的每个非空真前缀都不是合法括号序列。真前缀指不等于整个字符串的前缀。
合法括号序列递归定义如下:空串合法;若 合法,则 (p) 合法;若 均合法,则它们的拼接 合法。
本题使用特殊判题,可以输出任意一种合法方案。若无解,输出 Are you kidding me?。
输入格式
从标准输入读入一行字符串 。
输出格式
输出一行,表示构造方案;无解时输出 Are you kidding me?。
样例 1 输入
(?????
样例 1 输出
(()())
样例 2 输入
(???(???(?
样例 2 输出
Are you kidding me?
其他样例
样例 3 见下发文件 bracket3.in、bracket3.out,满足子任务 3 的性质。样例 4 见 bracket4.in、bracket4.out,满足子任务 2 的性质。
数据规模
| 子任务 | 长度范围 | 特殊性质 | 依赖关系 | 分值 |
|---|---|---|---|---|
| 1 | 无 | 无 | 15 | |
| 2 | 1 | 25 | ||
| 3 | 不含 ? |
无 | 15 | |
| 4 | 无 | 1、2、3 | 45 |