22364번 - そこそこバランスのとれた括弧列 다국어

「そこそこバランスのとれた括弧列」とは，以下のいずれかの条件を満たす文字列である．

• 空文字列
• そこそこバランスのとれた括弧列 A が存在し，'(' を 1 個または 2 個, A, ')' を 1 個または 2 個 をこの順に結合した文字列
• 空文字列でないそこそこバランスのとれた括弧列 A, B が存在し，A, B をこの順に結合した文字列

たとえば，'())' や '())(()()' などはそこそこバランスのとれた括弧列であるが，'((' や '()))((()' などはそこそこバランスのとれた括弧列ではない．

'(' と ')' のみからなる文字列 S が与えられる．S がそこそこバランスのとれた括弧列になるように括弧を追加する．ただし，括弧はどの位置に追加しても良い．追加する最小の括弧の数を求めよ．

入力は最大 50 データセットからなる．各データセットは 1 行からなり，長さが 1 以上 2 × 10⁵ 以下の '(' と ')' のみからなる文字列が与えられる．

入力の終わりは，'#' からなる行で表される．文字列の長さの合計は 5 × 10⁶ を超えない．

各データセットについて，そこそこバランスのとれた括弧列にするために追加する最小の括弧の数を 1 行に出力せよ．