Як перевірити дійсні дужки в Python

Автор

У цьому керівництві ви ознайомитеся з процесом верифікації коректності розташування дужок у коді Python.

Завдання перевірки правильності комбінацій дужок різних типів є типовим на співбесідах для програмістів. Зараз ви засвоїте методику розв’язання цього питання і створите функцію на Python, яка перевіряє наявність правильно розміщених дужок у заданому рядку.

У чому полягає задача перевірки коректності дужок?

Розпочнімо з визначення, що саме мається на увазі під задачею про коректні дужки.

Припустимо, у вас є рядок, який містить різні види дужок: круглі (), фігурні {} і квадратні []. Ваша задача полягає у визначенні, чи є комбінація цих дужок у рядку правильною.

Рядок із дужками вважається коректним, якщо виконано дві наступні умови:

  • Кожна відкриваюча дужка має відповідну закриваючу дужку того ж типу.
  • Дужки повинні бути закриті у правильному порядку.

Розглянемо кілька прикладів правильних і неправильних комбінацій дужок.

test_str = "{}]" --> НЕПРАВИЛЬНО, закриваюча ] не має відповідної відкриваючої
test_str = "[{}]" --> ПРАВИЛЬНО
test_str = "[]" --> ПРАВИЛЬНО
test_str = "[]{}" --> ПРАВИЛЬНО
test_str = "[{]}" --> НЕПРАВИЛЬНО, порядок закриття дужок не відповідає порядку відкриття

У нашому підході до розв’язання цієї задачі ключову роль відіграватиме структура даних під назвою “стек”. Давайте розглянемо основи стека в наступному розділі.

Коротко про структуру даних “стек”

Стек – це структура даних, що працює за принципом LIFO (останній прийшов, перший вийшов). Ви можете додавати елементи на вершину стека і видаляти їх з вершини стека.

Операція додавання елемента на вершину стека називається “push”, а операція видалення елемента з вершини стека – “pop”.

Ми будемо використовувати такі два правила для створення набору дій, які можна виконувати з рядком, що містить дужки:

  • Усі відкриваючі дужки додаються до стеку.
  • Якщо зустрічається закриваюча дужка, ми видаляємо елемент з вершини стеку.

Переходимо до розв’язання завдання перевірки коректності дужок.

Метод перевірки правильності розміщення дужок

Узагальнивши спостереження з наведених вище прикладів, ми отримуємо наступні висновки.

Перевірка довжини рядка: непарна довжина – рядок некоректний

Оскільки кожна відкриваюча дужка повинна мати відповідну закриваючу, коректний рядок повинен містити парну кількість символів. Якщо довжина рядка непарна, можна одразу сказати, що він містить неправильну комбінацію дужок.

# len(test_str) = 3 (непарна); ] не має відповідної відкриваючої [
test_str = "{}]"

# len(test_str) = 3 (непарна); ( не має відповідної закриваючої )
test_str = "[(]"

# len(test_str) = 5 (непарна); наявна зайва )
test_str = "{())}"

Далі розглянемо, як діяти, коли кількість символів у рядку є парною.

Довжина рядка парна: що далі?

Крок 1: Проходимо по рядку зліва направо. Назвемо наш рядок test_str, а окремі символи в рядку char.

Крок 2: Якщо поточний символ char є відкриваючою дужкою (, { або [, додаємо його до стеку і переходимо до наступного символу в рядку.

Крок 3: Тепер перевіряємо, чи наступний символ (char) є відкриваючою або закриваючою дужкою.

Крок 3.1: Якщо це відкриваюча дужка, ми знову додаємо її до стеку.

Крок 3.2: Якщо натомість ми зустріли закриваючу дужку, видаляємо елемент з вершини стека і переходимо до кроку 4.

Крок 4: Тут є 3 варіанти, залежно від значення, вилученого зі стеку:

Крок 4.1: Якщо це відкриваюча дужка того ж типу, повертаємося до кроку 3.

Крок 4.2: Якщо це відкриваюча дужка іншого типу, то можна знову сказати, що рядок не є коректним.

Крок 4.3: Останній варіант – стек порожній. Знову ж таки, це випадок некоректного рядка, оскільки ми зустріли закриваючу дужку, для якої немає відповідної відкриваючої.

Аналіз прикладів рядків з дужками

Давайте розглянемо три приклади та пройдемося по вищенаведених кроках.

📑 Якщо ви вже зрозуміли принцип роботи, можете пропустити цей розділ.

#1. Перший приклад: нехай test_str = “{()”.

  • { – перший символ, це відкриваюча дужка, тому додаємо її до стеку.
  • Наступний символ ( – теж відкриваюча дужка, тому також додаємо її до стеку.
  • Третій символ у рядку ) – це закриваюча дужка, тому треба видалити елемент з вершини стеку, що дає (.
  • На цьому моменті ми досягли кінця рядка. Але стек все ще містить відкриваючу { , яка так і не була закрита. Тому даний рядок з дужками test_str є некоректним.

#2. Другий приклад: нехай test_str = “()]»

  • Перший символ ( – відкриваюча дужка; додаємо її до стеку.
  • Другий символ ) – закриваюча дужка; витягуємо елемент з вершини стека, що є ( – відкриваюча дужка того самого типу. Переходимо до наступного символу.
  • Третій символ ] – закриваюча квадратна дужка, і ми знову повинні витягти елемент з вершини стека. Однак, як бачимо, стек порожній, а це означає, що немає відповідної відкриваючої дужки [. Отже, цей рядок некоректний.

#3. Останній приклад: test_str = “{()}”.

  • Перші два символи {( – відкриваючі дужки, тому додаємо їх до стеку.
  • Третій символ – це закриваюча ), тому видаляємо елемент з вершини стека – (.
  • Наступний символ } – це закриваюча фігурна дужка, і коли ми витягуємо елемент з вершини стека, отримуємо { – відкриваючу фігурну дужку.
  • Після проходження всього рядка стек порожній, а test_str є коректним! ✅

📌 Я склав блок-схему, що ілюструє етапи розв’язання задачі перевірки коректності дужок. Ви можете зберегти її для швидкого ознайомлення!

У наступному розділі розглянемо, як перетворити нашу концепцію в код на Python.

Програма на Python для перевірки правильності дужок

У Python ви можете використовувати список для імітації стека.

Ви можете використовувати метод .append(), щоб додавати елементи в кінець списку. Це аналогічно додаванню на вершину стека.

Метод .pop() повертає останній елемент зі списку, і це аналогічно видаленню з вершини стека – видаленню останнього доданого елемента.

Отже, тепер ви знаєте, як реалізувати операції push і pop зі списком Python, імітуючи стек.

Наступним кроком розглянемо питання: як розрізняти відкриваючі та закриваючі дужки?

Ви можете використовувати словник Python, де відкриваючі дужки ‘{‘, ‘[‘, ‘(‘ є ключами словника, а відповідні закриваючі дужки ‘}’, ‘]’, ‘)’ є значеннями. Ви можете використовувати метод .keys() для доступу до окремих ключів у словнику.

Використаємо все, чого ми навчилися, щоб написати визначення функції is_valid().

Розуміння визначення функції

Ознайомтеся з наступним блоком коду, що містить визначення функції. Ми використали кроки з блок-схеми разом із поясненнями, наведеними вище.

Крім того, ми також додали рядок документації, який включає:

  • короткий опис функції
  • аргументи функції
  • значення, що повертає функція

▶ Ви можете використовувати help(is_valid) або is_valid.__doc__, щоб отримати рядок документації.

def isValid(test_str):
  '''Перевіряє, чи є заданий рядок з дужками правильним.

  Args:
    test_str (str): Рядок з дужками для перевірки
  
  Returns:
    True, якщо test_str правильний; інакше False 
  '''
  # len(test_str) непарна -> некоректно!
  if len(test_str)%2 != 0:
    return False
  # ініціалізуємо словник дужок
  par_dict = {'(':')','{':'}','[':']'}
  stack = []
  for char in test_str:
    # додаємо відкриваючу дужку до стеку
    if char in par_dict.keys():
      stack.append(char)
    else:
      # закриваюча дужка без відповідної відкриваючої
      if stack == []:
          return False
      # якщо закриваюча дужка -> видаляємо елемент з вершини стеку
      open_brac = stack.pop()
      # невідповідна дужка -> некоректно!
      if char != par_dict[open_brac]:
        return False
  return stack == []

Функція Python is_valid перевіряє, чи є рядок з дужками правильним, і працює наступним чином:

  • Функція is_valid приймає один параметр test_str, який є рядком з дужками, який потрібно перевірити. Вона повертає True або False, залежно від того, чи є рядок test_str коректним.
  • Стек – це список Python, який емулює стек.
  • par_dict – це словник Python, де відкриваючі дужки є ключами, а закриваючі – відповідними значеннями.
  • Якщо під час обходу рядка ми зустрічаємо будь-яку умову, яка робить рядок з дужками некоректним, функція повертає False і завершує роботу.
  • Після проходження всіх символів у рядку, стек == [] перевіряє, чи стек порожній. Якщо так, то test_str є правильним, і функція повертає True. Інакше функція повертає False.

Тепер давайте зробимо кілька викликів функції, щоб переконатися, що вона працює правильно. 

str1 = '{}[]'
isValid(str1)
# Вивід: True

str2 = '{((}'
isValid(str2)
# Вивід: False

str3 = '[{()}]'
isValid(str3)
# Вивід: True

str4 = '[{)}]'
isValid(str4)
# Вивід: False

str5 = '[[]}'
isValid(str5)
# Вивід: False

З наведеного вище фрагменту коду можна зробити висновок, що функція працює належним чином!

Висновок 🧑‍💻

Ось короткий підсумок того, що ви вивчили.

  • Ви ознайомилися з проблемою перевірки правильності дужок.
  • Ви дізналися про підхід до розв’язання задачі, використовуючи стек як основну структуру даних.
  • Ви навчилися перевіряти комбінацію дужок за допомогою словника Python: де відкриваючі дужки є ключами, а відповідні закриваючі дужки – значеннями.
  • Нарешті, ви створили функцію Python для перевірки коректності рядка з дужками.

Наступним кроком буде спроба написати код для розв’язання цієї задачі в онлайн-редакторі Python techukraine.net. Не соромтеся звертатися до цього керівництва, якщо вам знадобиться допомога!

Ознайомтеся з іншими посібниками з Python. Бажаємо успішного програмування! 🎉