Напомним, что скобочная последовательность называется правильной, если путем вставки в нее символов + и 1 можно получить из нее корректное математическое выражение. Например, последовательности (())(), () и (()(())) — правильные, в то время как )(, (() и (()))( — нет. Назовем правильную скобочную последовательность — «ПСП».
Вам задана последовательность \(s\) из \(n\) символов (, ) и/или ?. В этой последовательности есть ровно один символ ( и ровно один символ ).
Вам необходимо заменить каждый символ ? либо на ), либо на ( (разные символы ? могут быть заменены разными скобками). Вы не можете изменять порядок символов, удалять их, вставить другие символы, и каждый ? должен быть заменен.
Определите, возможно ли получить ПСП после этих замен.
Выходные данные
Для каждого набора входных выведите YES, если можно получить правильную скобочную последовательность, или NO в противном случае}.
Вы можете вывести каждую букву в любом регистре (например, YES, Yes, yes, yEs будут распознаны как положительный ответ).
Примечание
В первом примере последовательность уже является ПСП.
В третьем примере вы можете получить ПСП следующим образом: ()() или (()).
В четвертом примере вы можете получить ПСП следующим образом: ()().
Примеры
| № | Входные данные | Выходные данные |
|
1
|
5
()
(?)
(??)
??()
)?(?
|
YES
NO
YES
YES
NO
|