括号序列

题目来源

戳我

题目描述

合法括号序列的定义是：

1.空序列是合法括号序列。

2.如果S是合法括号序列，那么(S)是合法括号序列。

3.如果A和B都是合法括号序列，那么AB是合法括号序列。

现在有一个括号序列，现在要计算一下它有多少非空子段是合法括号序列。

PS: 为了方便给出了5个样例， 但是丢在一个框框里

输入格式

一个字符串S

输出格式

有多少个非空子段是合法括号序列

样例输入

(
()
()()
(()
(())

样例输出

0
1
3
1
2

数据范围

$1 \leq |S| \leq 10^6$