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

У цьому посібнику ви навчитеся перевіряти дійсні дужки в Python.

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

Що таке проблема дійсних дужок?

Давайте почнемо наше обговорення з відповіді на запитання, що таке дійсна проблема круглих дужок?

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

Правильний рядок у круглих дужках задовольняє такі дві умови:

Кожна відкривна дужка повинна мати відповідну закриваючу дужку того самого типу.

Дужки повинні бути закриті в правильному порядку.

Ось кілька прикладів дійсних і недійсних рядків круглих дужок.

test_str = "{}]" --> INVALID, ] was never opened
test_str = "[{}]" --> VALID
test_str = "[]" --> VALID
test_str = "[]{}" --> VALID
test_str = "[{]}" --> INVALID, brackets closed incorrectly!

У нашому підході до вирішення проблем стек — це структура даних, яка відіграватиме ключову роль. Давайте розглянемо основи стека в наступному розділі.

Перегляд структури стекових даних

Стек — це структура даних за принципом «останній прийшов, перший вийшов» (LIFO), де ви можете додавати елементи до верхньої частини стеку, а також видаляти їх із верхньої частини стеку.

Коли ви додаєте елемент на вершину стека, ви виконуєте операцію проштовхування, коли ви видаляєте елемент із вершини стеку, ви виконуєте операцію вискакування.

Ми використаємо наступні два правила, щоб створити набір операцій, які ми можемо виконувати над рядком у дужках.

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

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

Як перевірити наявність дійсних дужок

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

Перевірте довжину рядка в дужках: якщо непарна, рядок недійсний

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

# len(test_str) = 3 (odd); ] does not have an opening [
test_str = "{}]"

# len(test_str) = 3 (odd); ( does not have a closing )
test_str = "[(]"

# len(test_str) = 5 (odd); there's a spurious )
test_str = "{())}"

Далі подивимося, як ми можемо впоратися, коли кількість символів у рядку парна

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

Крок 1: проведіть рядок зліва направо. Давайте назвемо рядок test_str і окремі символи в рядку char.

Крок 2. Якщо перший символ char є відкриваючою дужкою (, { або [, push it to the top of the stack and proceed to the next character in the string.

Step 3: Now, check if the next character (char) is an opening or a closing bracket.

Step 3.1: If it’s an opening bracket, push it again onto the stack.

Step 3.2: If you encounter a closing bracket instead, pop off the stack top, and proceed to step 4.

Step 4: Here again, there are 3 possibilities based on the value popped off the stack:

Step 4.1: If is an opening bracket of the same type, loop back to step 3.

Step 4.2: If it is an opening bracket of a different type, you can again conclude that it is not a valid parentheses string.

Step 4.3: The final possibility is that the stack is empty. Again, this is the case of an invalid string, as you’ve run into a closing bracket that doesn’t have a matching opening bracket.

Valid Parentheses String Examples Walkthrough

Now let’s take three examples and walk through the above steps.

📑 If you’ve already gotten the hang of how this works, feel free to skip to the next section.

#1. As a first example, let test_str = “{()”.

• { is the first character, and it’s an opening bracket, so you push it to the stack.
• The next character ( is also an opening bracket, so go ahead and push it onto the stack as well.
• The third character in the string ) is a closing bracket, so you have to pop off the stack top, which returns (.
• At this point, you’ve reached the end of the string. But the stack still contains the opening { , which was never closed. So the given parentheses string test_str is invalid.

#2. In this second example, let test_str = “()]»

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

#3. In this final example, test_str = “{()}”.

• The first two characters {( are opening brackets, so push them onto the stack.
• The third character is a closing ), so pop off the stack top – (.
• The next character } is a closing curly brace, and when you pop the stack top, you get { – an opening curly brace.
• After you have traversed the entire string, the stack is empty and test_str is valid! ✅

📌 I’ve put together the following flowchart outlining the steps in the valid parentheses checking problem. You may save it for quick reference!

In the next section, let’s see how to translate our concept to Python code.

Python Program to Check for Valid Parentheses

In Python, you can use the list to emulate a stack.

You can use the .append() method to add elements to the end of the list. This is similar to pushing to the top of the stack.

The .pop() method returns the last element from the list, and this is similar to the popping off the top of the stack – to remove the last-added element.

So you now know how to implement the push and pop operations on a Python list, emulating the stack.

As a next step, let’s answer the question: how to differentiate between opening and closing brackets?

Well, you can use a Python dictionary – with the opening brackets ‘{‘, ‘[‘, ‘(‘ as the keys of the dictionary and the corresponding closing brackets ‘}’, ‘]’, ‘)’ як значення. Ви можете використовувати метод .keys() для доступу до окремих ключів у словнику.

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

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

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

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

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

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

def isValid(test_str):
  '''Check if a given parentheses string is valid.

  Args:
    test_str (str): The parentheses string to be validated
  
  Returns:
    True if test_str is valid; else False 
  '''
  # len(test_str) is odd -> invalid!
  if len(test_str)%2 != 0:
    return False
  # initialize parentheses dict
  par_dict = {'(':')','{':'}','[':']'}
  stack = []
  for char in test_str:
    # push opening bracket to stack
    if char in par_dict.keys():
      stack.append(char)
    else:
      # closing bracket without matching opening bracket
      if stack == []:
          return False
      # if closing bracket -> pop stack top
      open_brac = stack.pop()
      # not matching bracket -> invalid!
      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)
# Output: True

str2 = '{((}'
isValid(str2)
# Output: False

str3 = '[{()}]'
isValid(str3)
# Output: True

str4 = '[{)}]'
isValid(str4)
# Output: False

str5 = '[[]}'
isValid(str5)
# Output: False

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

Висновок 🧑‍💻

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

• По-перше, ви познайомилися з проблемою перевірки дійсних дужок.
• Далі ви навчилися підходу до вирішення проблеми, використовуючи стек як обрану структуру даних.
• Потім ви дізналися, як перевірити комбінацію круглих дужок за допомогою словника Python: із відкриваючими дужками, ключами та відповідними закриваючими дужками як значеннями.
• Нарешті, ви визначили функцію Python, щоб перевірити, чи дійсний заданий рядок у дужках.

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

Перегляньте інші посібники з Python. Щасливого кодування!🎉