魏老四OJ Home ProblemSet Source/Category Contest 题单 Status Ranklist F.A.Qs
Login

2292: 括号匹配(一)

Memory Limit：128 MB Time Limit：1.000 S
： Creator：
Submit：5 Solved：4

Description

给定一个仅由 ( 与 ) 构成的括号序列，请求出最少删去多少括号可以使它变成匹配的。匹配定义如下：
  • 空序列是匹配的；
  • 如果括号序列 s 是匹配的，那么 (s) 也是匹配的；
  • 如果括号序列 s 与 t 是匹配的，那么 st 也是匹配的。

Input

单个字符串：表示输入的序列。

Output

单个整数：表示最少删去多少个括号才能使输入序列变成匹配的。

Sample Input 

()()()()

Sample Output 

0

HINT

设 nn 表示输入序列的长度

  • 对于 50% 的数据，1≤n≤1,000；
  • 对于 100% 的数据，1≤n≤1,000,000；

Source/Category

SubmitStatistics