Како проверити да ли постоје важеће заграде у Питхон-у

Преглед садржаја

Провера исправности заграда у Пајтону

У овом упутству ћете научити како да проверите да ли је распоред заграда у низу знакова исправан користећи Пајтон.

Задатак провере ваљаности низа који садржи заграде је често постављано питање на интервјуима за посао програмера. У наредним минутима ћете се упознати са техником за решавање овог задатка, као и са имплементацијом Пајтон функције која може да изврши проверу исправности за дати низ.

Шта представља проблем исправних заграда?

Да кренемо са дефинисањем самог проблема – шта је то тачно што чини низ заграда исправним?

Добијате низ знакова који се састоји од обичних, витичастих и угаоних заграда: () [] {}. Ваш задатак је да утврдите да ли је задата комбинација заграда валидна или није.

Да би низ заграда био важећи, морају бити испуњена два услова:

Свака отворена заграда мора имати одговарајућу затворену заграду истог типа.
Заграде морају бити затворене правилним редоследом.

У наставку су дати примери низова заграда који су исправни, као и они који нису:

test_str = "{}]"  --> НЕИСПРАВНО, ] никада није отворена
test_str = "[{}]"  --> ИСПРАВНО
test_str = "[]"  --> ИСПРАВНО
test_str = "[]{}"  --> ИСПРАВНО
test_str = "[{]}"  --> НЕИСПРАВНО, заграде нису затворене правилним редоследом!

У нашем приступу решавању проблема, структура података звана стек ће играти кључну улогу. Погледајмо основе стека у следећем одељку.

Структура података стек

Стек је структура података типа „последњи ушао, први изашао“ (LIFO). Елементи се додају и уклањају са врха стека.

Додавање елемента на врх стека се назива операција “push”, док се уклањање елемента са врха стека назива операција “pop”.

Користићемо следећа правила за извођење операција на низу заграда:

Све отворене заграде се додају на стек.
Када наиђемо на затворену заграду, уклањамо елемент са врха стека (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` отворена заграда (, {, или [, додајемо га на врх стека (push) и прелазимо на следећи знак у низу.

Корак 3: Сада, проверавамо да ли је следећи знак `char` отворена или затворена заграда.

Корак 3.1: Ако је у питању отворена заграда, додајемо је на стек (push).

Корак 3.2: Уколико је у питању затворена заграда, уклањамо елемент са врха стека (pop) и настављамо са кораком 4.

Корак 4: Сада, поново имамо 3 могућности, зависно од вредности која је уклоњена са стека:

Корак 4.1: Ако је у питању отворена заграда истог типа, враћамо се на корак 3.

Корак 4.2: Ако је у питању отворена заграда различитог типа, можемо закључити да низ заграда није исправан.

Корак 4.3: Последња могућност је да је стек празан. Ово је такође случај када низ није исправан, јер смо наишли на затворену заграду која нема одговарајућу отворену.

Примери провере низа заграда

Сада ћемо проћи кроз три примера и видети како кораци које смо описали функционишу.

📑 Уколико сте већ разумели како ово функционише, можете прескочити овај одељак.

#1. За први пример, нека је `test_str = “{()”`.

{ је први знак, и то је отворена заграда, па је додајемо на стек.
Следећи знак ( је такође отворена заграда, па је додајемо на стек.
Трећи знак у низу ) је затворена заграда, па уклањамо елемент са врха стека, што враћа (.
У овом тренутку, дошли смо до краја низа. Међутим, стек и даље садржи отворену {, која никада није затворена. Дакле, низ заграда `test_str` није исправан.

#2. У овом другом примеру, нека је `test_str = “()]”`

Први знак ( је отворена заграда; додајемо је на стек.
Други знак ) је затворена заграда; уклањамо елемент са врха стека, што је у овом случају ) – отворена заграда истог типа. Прелазимо на следећи знак.
Трећи знак ] је затворена угаона заграда и требало би поново да уклонимо елемент са врха стека. Међутим, као што видите, стек је празан – што значи да не постоји одговарајућа отворена заграда [. Стога, овај низ није исправан.

#3. У овом последњем примеру, `test_str = “{()}”`.

Прва два знака {( су отворене заграде, додајемо их на стек.
Трећи знак је затворена ), уклањамо елемент са врха стека – (.
Следећи знак } је затворена витичаста заграда, и када уклонимо елемент са врха стека, добијамо { – отворену витичасту заграду.
Након што смо прошли кроз цео низ, стек је празан и `test_str` је исправан! ✅

📌 Припремио сам дијаграм тока који приказује кораке у проблему провере исправности заграда. Можете га сачувати за брзу референцу!

У следећем одељку, видећемо како да преведемо наш концепт у Пајтон код.

Пајтон програм за проверу исправности заграда

У Пајтону можемо користити листу да симулирамо стек.

Метода `.append()` се користи за додавање елемената на крај листе, што је слично операцији “push” на стеку.

Метода `.pop()` враћа последњи елемент са листе, што је слично операцији “pop” са стека – уклањање последњег додатог елемента.

Сада знате како да имплементирате операције “push” и “pop” на Пајтон листи, симулирајући стек.

Следећи корак је одговор на питање: како разликовати отворене и затворене заграде?

Можемо користити Пајтон речник – са отвореним заградама ‘{‘, ‘[‘, ‘(‘ као кључевима речника, а одговарајућим затвореним заградама ‘}’, ‘]’, ‘)’ као вредностима. Можемо користити методу `.keys()` за приступ кључевима у речнику.

Хајде да искористимо све што смо научили да напишемо дефиницију функције `is_valid()`.

Разумевање дефиниције функције

Погледајте следећи код који садржи дефиницију функције. Користили смо кораке са дијаграма тока у комбинацији са претходним објашњењем.

Поред тога, додали смо и docstring који укључује:

кратак опис функције
аргументе функције
повратне вредности функције

▶ Можете користити `help(is_valid)` или `is_valid.__doc__` да бисте добили docstring.

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 == []

Пајтон функција `is_valid` проверава да ли је низ заграда исправан и ради на следећи начин:

Функција `is_valid` прима један параметар, `test_str`, који је низ заграда за проверу. Функција враћа `True` или `False` зависно од тога да ли је низ `test_str` исправан или не.
Овде је стек Пајтон листа која симулира стек.
`par_dict` је Пајтон речник, са отвореним заградама као кључевима и одговарајућим затвореним заградама као вредностима.
Док пролазимо кроз низ, ако наиђемо на било који услов који чини низ заграда неисправним, функција враћа `False` и излази.
Након проласка кроз све знаке у низу, `stack == []` проверава да ли је стек празан. Ако јесте, `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

Из горњег исечка кода можемо закључити да функција ради како се очекује!

Закључак 🧑‍💻

Ево кратког резимеа онога што сте научили:

Прво сте се упознали са проблемом провере исправности низа заграда.
Затим сте научили како да приступите решавању проблема користећи стек као структуру података.
Затим сте научили како да проверите комбинацију заграда користећи Пајтон речник: са отвореним заградама као кључевима и одговарајућим затвореним заградама као вредностима.
На крају сте дефинисали Пајтон функцију која проверава да ли је задати низ заграда исправан.

Као следећи корак, покушајте да кодирате проблем у онлајн Пајтон едитору. Слободно се вратите на ово упутство ако вам треба помоћ!

Погледајте још Пајтон туторијала. Срећно са кодирањем!🎉