Как да проверите за валидни скоби в 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), където можете да добавяте елементи към горната част на стека и също така да ги премахвате от горната част на стека.

Когато добавите елемент към горната част на стека, вие извършвате операция за избутване, когато премахнете елемент от горната част на стека, вие извършвате операция за изскачане.

Ще използваме следните две правила, за да създадем набор от операции, които можем да извършим върху низа в скоби.

Натиснете всички отварящи скоби върху стека.
Ако попаднете на затваряща скоба, извадете горната част на стека.

Нека продължим с решаването на проблема с проверката на валидни скоби.

Как да проверите за валидни скоби

Обединявайки всички наблюдения от горните примери, имаме следното.

Проблем с драйвера на USB устройство за масово съхранение (ФИКСИРАН)

Проверете дължината на низа в скобите: Ако е странно, низът е невалиден

Тъй като всяка отваряща скоба трябва да има затваряща скоба, валидният низ трябва да съдържа четен брой знаци. Ако дължината на низа е странна, можете веднага да заключите, че има невалидна комбинация от скоби.

# 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: Ако първият символ е отваряща скоба (, { или [, 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.

Как да преместите Microsoft Authenticator на нов телефон

#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().

Как да намерите и изпратите GIF файлове на Slack

Разбиране на дефиницията на функцията

Прочетете следната кодова клетка, съдържаща дефиницията на функцията. Можете да видите, че сме използвали стъпките в блок-схемата в тандем с горното обяснение.

Освен това добавихме и a документен низ включително:

кратко описание на функцията
аргументите в извикването на функцията
върнатите стойности от функцията

▶ Можете да използвате help(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 == []

Функцията is_valid на Python проверява дали низът в скоби е валиден и работи по следния начин.

Функцията 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 на pctechbg.net. Чувствайте се свободни да прегледате това ръководство, ако имате нужда от помощ!

Вижте още уроци по Python. Приятно кодиране!🎉