Sådan tjekker du for gyldige parenteser i Python

I denne vejledning lærer du at tjekke for gyldige parenteser i Python.

Med en række parenteser er det et populært kodende interviewspørgsmål at kontrollere, om kombinationen af parenteser er gyldig. Og i løbet af de næste par minutter vil du lære teknikken til at løse dette spørgsmål og også kode en Python-funktion for at validere en given streng.

Indholdsfortegnelse

Hvad er problemet med gyldige parenteser?

Lad os starte vores diskussion med at besvare spørgsmålet, hvad er problemet med gyldige parenteser?

Givet en streng, der indeholder tegnene simple parenteser, krøllede og firkantede klammeparenteser: () [] {}, skal du kontrollere, om den angivne parenteskombination er gyldig eller ej.

En gyldig parentesstreng opfylder følgende to betingelser:

Hvert åbningsbeslag skal have et matchende lukkebeslag af samme type.

Beslagene skal lukkes i den rigtige rækkefølge.

Her er et par eksempler på gyldige og ugyldige parentesstrenge.

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

I vores problemløsningstilgang er stakken den datastruktur, der kommer til at spille en central rolle. Lad os gennemgå det grundlæggende i en stak i næste afsnit.

Stakdatastrukturen genbesøgt

Stakken er en last in first out (LIFO) datastruktur, hvor du kan tilføje elementer til toppen af stakken og også fjerne dem fra toppen af stakken.

Når du tilføjer et element til staktoppen, udfører du en push-operation, når du fjerner et element fra stack-toppen, udfører du en pop-operation.

Vi bruger de følgende to regler til at komme med et sæt operationer, som vi kan udføre på parentesstrengen.

Skub alle åbningsbeslag på stakken.
Hvis du støder på et lukkebeslag, skal du tage stabletoppen af.

Lad os fortsætte med at løse det gyldige parenteskontrolproblem.

Sådan tjekker du for gyldige parenteser

Ved at sammensætte alle observationerne fra ovenstående eksempler har vi følgende.

Tjek længden af parentesstrengen: Hvis ulige, er strengen ugyldig

Da hver åbningsparentes skal have en afsluttende parentes, bør en gyldig streng indeholde et lige antal tegn. Hvis længden af strengen er ulige, kan du konkludere med det samme, at den har en ugyldig kombination af parenteser.

# 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 = "{())}"

Lad os derefter se, hvordan vi kan tackle, når antallet af tegn i strengen er lige

Sådan går du ind i gendannelsestilstand på din iPhone 7 og 7 Plus

Længden af parentesstrengen er lige: hvad nu?

Trin 1: Kør strengen fra venstre mod højre. Lad os kalde strengen test_str, og de individuelle tegn i strengen char.

Trin 2: Hvis det første tegn tegn er en åbningsparentes (, { eller [, 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.

Sådan starter du en blog ved hjælp af Google Blogger

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

Det første tegn ( er en åbningsparentes; skub den til stakken.
Det andet tegn ) er en afsluttende parentes; pop stabeltoppen af, som tilfældigvis er ) – en åbningsbeslag af samme type. Fortsæt til næste tegn.
Det tredje tegn ]er en afsluttende firkantet parentes, og du bør springe af stabeltoppen igen. Men som du kan se, er stakken tom – hvilket betyder, at der ikke er nogen matchende åbningsbeslag [. 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 ‘}’, ‘]’, ‘)’ som værdierne. Du kan bruge metoden .keys() til at få adgang til individuelle nøgler i ordbogen.

Lad os bruge alt det, vi har lært, til at skrive definitionen af funktionen is_valid().

Forstå funktionsdefinitionen

Læs den følgende kodecelle, der indeholder funktionsdefinitionen. Du kan se, at vi har brugt trinene i flowchartet sammen med ovenstående forklaring.

Sådan sælger du din bærbare computer, telefon eller tablet for højeste dollar

Derudover har vi også tilføjet en docstring inklusive:

en kort beskrivelse af funktionen
argumenterne i funktionskaldet
returværdierne fra funktionen

▶ Du kan bruge help(is_valid) eller is_valid.__doc__ til at hente docstringen.

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-funktionen is_valid kontrollerer, om parentesstrengen er gyldig, og den fungerer som følger.

Funktionen is_valid tager én parameter, test_str, som er parentesstrengen, der skal valideres. Det returnerer True eller False afhængigt af om strengen test_str er gyldig eller ej.
Her er stak Python-listen, der emulerer stakken.
Og par_dict er Python-ordbogen, med åbne parenteser som tasterne og afsluttende parenteser som de tilsvarende værdier.
Mens vi krydser strengen, hvis vi støder ind i en tilstand, der gør parentesstrengen ugyldig, returnerer funktionen False og afsluttes.
Efter at have krydset alle tegnene i strengen, stak == [] tjekker om stakken er tom. Hvis ja, er test_str gyldig, og funktionen returnerer True. Ellers returnerer funktionen Falsk.

Lad os nu gå videre og foretage et par funktionskald for at bekræfte, at vores funktion fungerer korrekt.

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

Ud fra kodestykket ovenfor kan vi konkludere, at funktionen fungerer som forventet!

Konklusion 🧑‍💻

Her er en hurtig oversigt over, hvad du har lært.

For det første blev du introduceret til problemet med kontrol af gyldige parenteser.
Dernæst lærte du en tilgang til at løse problemet ved at bruge stakken som den valgte datastruktur.
Du lærte derefter, hvordan du validerer en parenteskombination ved hjælp af en Python-ordbog: med åbne parenteser, tasterne og de tilsvarende afsluttende parenteser som værdier.
Til sidst definerede du Python-funktionen for at kontrollere, om en given parentesstreng er gyldig.

Som et næste trin kan du prøve at kode problemet på toadmin.dk’s online Python-editor. Du er velkommen til at gense denne guide, hvis du har brug for hjælp!

Se flere Python-tutorials. God kodning!🎉