括号店老板的微笑
You cannot submit for this problem because the contest is ended. You can click "Open in Problem Set" to view this problem in normal mode.
Description
括号店老板卖两种括号:左括号 和右括号 。
一天,他收到一个只包含括号的字符串 。老板看完后沉默了,因为这个字符串不一定是合法括号序列。
老板可以在字符串的任意位置插入任意数量的括号。请问至少需要插入多少个括号,才能使整个字符串变成一个合法括号序列?
合法括号序列定义如下:
- 空串是合法括号序列;
- 如果 是合法括号序列,那么
(A)也是合法括号序列; - 如果 和 都是合法括号序列,那么 也是合法括号序列。
Format
Input
第一行一个字符串 ,仅由 和 组成。
Output
输出一行一个整数,表示最少需要插入的括号数量。
Samples
(()))(
2
Note
样例说明:
可以在第一个字符前插入一个 来匹配多出来的 ,并在末尾插入一个 来匹配最后的 。
一种合法结果为:。当然,老板并不关心你插在哪里,他只关心你少买点,哦不,少插点。
2026江南程序设计竞赛联盟暑期多校训练-摸底赛(重现)
- Status
- Done
- Rule
- XCPC
- Problem
- 11
- Start at
- 2026-10-14 13:45
- End at
- 2026-10-14 17:45
- Duration
- 4 hour(s)
- Host
- Partic.
- 2