/ 
実行時間制限: 2 sec / メモリ制限: 1024 MiB
問題文
(, ) からなる文字列のうち、連続する () を消すことを 0 回以上繰り返して空文字列にできる文字列を 正しい括弧列 と呼びます。
- 例えば
(),(()),(()())()は正しい括弧列ですが、)(,()),(()()))(()は正しい括弧列ではありません。
(, ) からなる文字列 S が与えられるので、S が正しい括弧列であるか判定してください。
制約
- S は
(,)からなる長さ 2 \times 10^5 以下の空でない文字列
入力
入力は以下の形式で標準入力から与えられる。
S
出力
S が正しい括弧列である場合は Yes を、そうでない場合は No を出力せよ。
入力例 1
(())
出力例 1
Yes
S から連続する () を以下の操作のように取り除くと S を空文字列にすることができます。よって S は正しい括弧列です。
- 現在の 2 文字目と 3 文字目の
()を取り除く。S は()になる。 - 現在の 1 文字目と 2 文字目の
()を取り除く。S は空文字列になる。
入力例 2
())(
出力例 2
No
入力例 3
(
出力例 3
No
入力例 4
((())()()())()()
出力例 4
Yes
Problem Statement
A string consisting of ( and ) is said to be a correct bracket sequence if it can be made empty by erasing a contiguous occurrence of () zero or more times.
- For instance,
(),(()), and(()())()are correct bracket sequences, while)(,()), and(()()))(()are not.
You are given a string S consisting of ( and ). Determine whether S is a correct bracket sequence.
Constraints
- S is a non-empty string of length at most 2 \times 10^5 consisting of
(and).
Input
The input is given from Standard Input in the following format:
S
Output
If S is a correct bracket sequence, print Yes; otherwise, print No.
Sample Input 1
(())
Sample Output 1
Yes
One can make S empty by removing consecutive occurrences of () as follows, so S is a correct bracket sequence.
- Remove the second and third characters of the current string, making it
(). - Remove the first and second characters of the current string, making it empty.
Sample Input 2
())(
Sample Output 2
No
Sample Input 3
(
Sample Output 3
No
Sample Input 4
((())()()())()()
Sample Output 4
Yes