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

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

С обзиром на низ заграда, провера да ли је комбинација заграда исправна је популарно питање за интервју за кодирање. И током наредних неколико минута научићете технику за решавање овог питања и такође кодирати Питхон функцију за валидацију датог стринга.

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

Шта је проблем са важећим заградама?

Хајде да започнемо нашу дискусију одговором на питање, шта је проблем са важећим заградама?

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

Важећи низ заграда задовољава следећа два услова:

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

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

Ево неколико примера важећих и неважећих низова заграда.

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

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

Ревидирана структура података стека

Стек је структура података последњи ушао први изашао (ЛИФО), где можете додати елементе на врх стека и уклонити их са врха стека.

Када додате елемент на врх стека, изводите операцију гурања, када уклоните елемент са врха стека, изводите операцију искапања.

Користићемо следећа два правила да бисмо дошли до скупа операција које можемо да изведемо на низу заграда.

Гурните све отворне заграде на сноп.
Ако наиђете на заграду за затварање, искочите са врха хрпе.

Хајде да наставимо са решавањем проблема провере валидних заграда.

Како проверити да ли постоје важеће заграде

Стављајући заједно сва запажања из горњих примера, имамо следеће.

Проверите дужину низа заграда: ако је непаран, стринг је неважећи

Како свака почетна заграда мора имати заграду за затварање, важећи низ треба да садржи паран број знакова. Ако је дужина стринга непарна, можете одмах закључити да има неважећу комбинацију заграда.

# 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: Пређите низ низ с лева на десно. Позовимо стринг тест_стр, и појединачне знакове у стрингу цхар.

Корак 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.

Ламбдатест је олакшао тестирање мобилних и веб апликација

#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 ‘}’, ‘]’, ‘)’ као вредности. Можете користити методу .кеис() за приступ појединачним кључевима у речнику.

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

Како омогућити тамни режим у Бинг Цхат-у

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

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

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

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

▶ Можете користити хелп(ис_валид) или ис_валид.__доц__ да бисте преузели доцстринг.

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

Питхон функција ис_валид проверава да ли је низ заграда валидан и ради на следећи начин.

Функција ис_валид узима један параметар, тест_стр, који је низ заграда за проверу. Враћа Тачно или Нетачно у зависности од тога да ли је стринг тест_стр важећи или не.
Овде, стек је Питхон листа која емулира стек.
А пар_дицт је Питхон речник, са почетним заградама као кључевима и завршним заградама као одговарајућим вредностима.
Док прелазимо низ низ, ако наиђемо на било који услов који чини низ заграда неважећим, функција враћа Фалсе и излази.
Након преласка свих знакова у низу, стек == [] проверава да ли је стек празан. Ако јесте, тест_стр је важећи, а функција враћа Тачно. У супротном, функција враћа Фалсе.

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

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

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

Закључак 🧑‍💻

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

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

Као следећи корак, покушајте да кодирате проблем на вдзвдз-овом онлајн Питхон уређивачу. Будите слободни да поново погледате овај водич ако вам је потребна помоћ!

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