В українській пунктуації застосовують
круглі, або заокруглені, ( ),
квадратні [ ]
і кутові, або ламані, < > дужки
Епіграф з чудової книжки, що зветься «Український правопис». Чинна редакція 2019 року містить 393 сторінки і безкоштовно лежить на сайті МОН. В pdf файлі є текстовий шар, відповідно, працює пошук. Прекрасна книжка для розвіювання власних синтаксично-пунктуаційних ілюзій, рекомендую.
І саме про дужки наразі буде задача. Про круглі. На сайті basecamp.eolymp.com коефіцієнт прийняття задачі наразі складає 37% при 12к відправлень.
Задача «Дужкові послідовності».
https://basecamp.eolymp.com/uk/problems/5327
Умова:
Дужкова послідовність - це правильний арифметичний вираз, з якого видалили усі числа та знаки. Наприклад,
1+(((2+3)+5)+(3+4))→((())())
Вхідні дані
Задано послідовність з відткриваючих та закриваючих дужок довжиною не більше 4⋅106.
Вихідні дані
Виведіть "YES" якщо дужкова послідовність правильна та "NO" інакше.
Приклади
Вхідні дані #1
((())())
Відповідь #1
YES
Вхідні дані #2
(()
Відповідь #2
NO
Для успішного розв’язання задачі пропоную сформулювати умови правильної послідовності. Це через те, що тестові приклади підібрані так, що можуть трохи заплутати.
Чому в другому прикладі послідовність неправильна і виводиться «NO»? Через те, що кількість відкритих дужок не дорівнює кількості закритих дужок. Давайте запишемо цю очевидну умову червоним кольором:
У правильній послідовності кількість відкритих дужок дорівнює кількості закритих дужок.
Якщо проаналізувати приклад #1, то кількість відкритих і закритих дужок однакова. І програмісту початківцю може здатися, що умова, яка записана червоним кольором – єдина. І програміст-початківець пише щось на кшталт
s = input()
if s.count('(') == s.count(')'):
print('YES')
else:
print('NO')
За такий код сайт eolymp дає 96 балів зі 100. Якщо це – олімпіада з програмування, то це чимало, можна порадіти і поїсти чесно заробленого шоколаду. А якщо це випробування для прийому на роботу зі заблокованим штучним інтелектом, то треба шукати ще якісь умови правильної послідовності.
Пропоную ще один, мій приклад, що нам допоможе:
Вхідні дані #3
)(
Відповідь #2
NO
Кількість дужок співпадає, але бачимо, що існує, як мінімум, ще одна умова правильної послідовності. Давайте її сформулюємо знову червоним текстом:
При перегляді послідовності зліва направо кількість закритих дужок жодного разу не може перевищувати кількість відкритих дужок.
Тепер давайте спробуємо написати код, що враховує вже дві умови. Якщо програміст вміє, можна використати регулярні вирази або ще щось гарне. А якщо треба швидко і просто, то можна скористатися циклом і розгалуженням.
Логіка змінних:
t - текстова послідовність
v – кількість відкритих дужок
z – кількість закритих дужок
x – елемент текстової послідовності, що наразі аналізується
f – прапорець (flag), що підніметься якщо станеться ситуація, коли закритих дужок більше відкритих, по замовчуванню прапорець опущений (False). Якщо прапорець піднявся, то не варто продовжувати дослідження текстової послідовності, все одно вона неправильна.
t = input()
v = 0
z = 0
f = False
for x in t:
if x == '(':
v += 1
else:
if v > z:
z += 1
else:
f = True
break
if not f and v == z:
print('YES')
else:
print('NO')