Time Limit: 2 sec / Memory Limit: 1024 MB
問題文
(
, )
からなる文字列のうち、連続する ()
を消すことを 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