Скобочная последовательность — это строка, содержащая только символы «(» и «)». Правильная скобочная последовательность (или, коротко говоря, ПСП) — это скобочная последовательность, которая может быть преобразована в правильное арифметическое выражение путем вставки символов «1» и «+» между исходными символами последовательности. Например:
- скобочные последовательности «()()» и «(())» являются правильными (возможные выражения: «(1)+(1)» и «((1+1)+1)»);
- скобочные последовательности «)(», «(» и «)» не являются правильными.
В начале была некоторая ПСП. Некоторые скобки заменили на знаки вопроса. Верно ли, что существует единственный способ заменить знаки вопроса на скобки так, чтобы получилась ПСП?
Выходные данные
На каждый набор входных данных выведите «YES», если способ заменить знаки вопроса на скобки так, чтобы получилась ПСП, единственный. Если существует больше одного способа, то выведите «NO».
Примечание
В первом наборе входных данных единственная возможная оригинальная ПСП — это «(())».
Во втором наборе существует несколько способов восстановить ПСП.
В третьем и четвертом наборах единственная возможная ПСП — это «()».
В пятом наборе оригинальная ПСП может быть «((()()))» или «(())()()».
Примеры
| № | Входные данные | Выходные данные |
|
1
|
5
(?))
??????
()
??
?(?)()?)
|
YES
NO
YES
YES
NO
|