「そこそこバランスのとれた括弧列」とは,以下のいずれかの条件を満たす文字列である.
たとえば,'())' や '())(()()' などはそこそこバランスのとれた括弧列であるが,'((' や '()))((()' などはそこそこバランスのとれた括弧列ではない.
'(' と ')' のみからなる文字列 S が与えられる.S がそこそこバランスのとれた括弧列になるように括弧を追加する.ただし,括弧はどの位置に追加しても良い.追加する最小の括弧の数を求めよ.
入力は最大 50 データセットからなる.各データセットは 1 行からなり,長さが 1 以上 2 × 105 以下の '(' と ')' のみからなる文字列が与えられる.
入力の終わりは,'#' からなる行で表される.文字列の長さの合計は 5 × 106 を超えない.
各データセットについて,そこそこバランスのとれた括弧列にするために追加する最小の括弧の数を 1 行に出力せよ.
(() ())()(() ((())))) ))(()( ))()()))()(((())))))))((((()( #
0 0 0 2 5