Hvordan se etter gyldige parenteser i Python

I denne opplæringen lærer du å se etter gyldige parenteser i Python.

Gitt en rekke parenteser, er det et populært kodende intervjuspørsmål å sjekke om parenteskombinasjonen er gyldig. Og i løpet av de neste minuttene vil du lære teknikken for å løse dette spørsmålet og også kode opp en Python-funksjon for å validere en gitt streng.

Hva er problemet med gyldige parenteser?

La oss starte diskusjonen med å svare på spørsmålet, hva er problemet med gyldige parenteser?

Gitt en streng som inneholder tegnene enkle parenteser, krøllete og firkantede klammeparenteser: () [] {}, må du sjekke om den gitte parenteskombinasjonen er gyldig eller ikke.

En gyldig parentesstreng oppfyller følgende to betingelser:

Hver åpningsbrakett skal ha en matchende lukkebeslag av samme type.

Beslagene skal lukkes i riktig rekkefølge.

Her er noen eksempler på gyldige og ugyldige parentesstrenger.

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

I vår problemløsningstilnærming er stabelen datastrukturen som vil spille en sentral rolle. La oss gå gjennom det grunnleggende om en stabel i neste avsnitt.

Stabeldatastrukturen gjenopptatt

Stakken er en sist inn først ut (LIFO) datastruktur, hvor du kan legge til elementer på toppen av stabelen og også fjerne dem fra toppen av stabelen.

Når du legger til et element til stabeltoppen, utfører du en push-operasjon, når du fjerner et element fra stabeltoppen, utfører du en pop-operasjon.

Vi vil bruke følgende to regler for å komme opp med et sett med operasjoner som vi kan utføre på parentesstrengen.

• Skyv alle åpningsbraketter på stabelen.
• Hvis du kommer over en lukkebrakett, ta av stabeltoppen.

La oss fortsette med å løse problemet med kontroll av gyldige parenteser.

Hvordan sjekke for gyldige parenteser

Ved å sette sammen alle observasjonene fra eksemplene ovenfor, har vi følgende.

Sjekk lengden på parentesstrengen: Hvis oddetall, er strengen ugyldig

Siden hver åpningsparentes må ha en avsluttende parentes, bør en gyldig streng inneholde et partall av tegn. Hvis lengden på strengen er odde, kan du konkludere med en gang at den har en ugyldig kombinasjon av 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 = "{())}"

Deretter, la oss se hvordan vi kan takle når antall tegn i strengen er partall

Lengden på parentesstrengen er jevn: hva neste?

Trinn 1: Traverser strengen fra venstre til høyre. La oss kalle strengen test_str, og de individuelle tegnene i strengen char.

Trinn 2: Hvis det første tegnet er en åpningsparentes (, {, 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.

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

• Det første tegnet ( er en åpningsparentes; skyv den til stabelen.
• Det andre tegnet ) er en avsluttende parentes; sprett av stabeltoppen, som tilfeldigvis er ) – en åpningsbrakett av samme type. Fortsett til neste tegn.
• Det tredje tegnet ]er en avsluttende hakeparentes, og du bør hoppe av stabeltoppen igjen. Men som du kan se, er stabelen tom – noe som betyr at det ikke er noen matchende åpningsbrakett [. 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 verdiene. Du kan bruke .keys()-metoden for å få tilgang til individuelle nøkler i ordboken.

La oss bruke alt vi har lært til å skrive definisjonen av funksjonen is_valid().

Forstå funksjonsdefinisjonen

Les gjennom følgende kodecelle som inneholder funksjonsdefinisjonen. Du kan se at vi har brukt trinnene i flytskjemaet sammen med forklaringen ovenfor.

I tillegg har vi også lagt til en docstring gjelder også:

• en kort beskrivelse av funksjonen
• argumentene i funksjonskallet
• returverdiene fra funksjonen

▶ Du kan bruke help(is_valid) eller is_valid.__doc__ for å 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-funksjonen is_valid sjekker om parentesstrengen er gyldig, og den fungerer som følger.

• Funksjonen is_valid tar inn én parameter, test_str som er parentesstrengen som skal valideres. Den returnerer True eller False avhengig av om strengen test_str er gyldig eller ikke.
• Her er stack Python-listen som emulerer stabelen.
• Og par_dict er Python-ordboken, med åpningsparenteser som tastene og avsluttende parenteser som tilsvarende verdier.
• Mens vi krysser strengen, hvis vi kommer inn i en tilstand som gjør parentesstrengen ugyldig, returnerer funksjonen False og avsluttes.
• Etter å ha krysset alle tegnene i strengen, stable == [] sjekker om stabelen er tom. Hvis ja, er test_str gyldig, og funksjonen returnerer True. Ellers returnerer funksjonen False.

Nå, la oss gå videre og foreta noen funksjonsanrop for å bekrefte at funksjonen vår fungerer som den skal.

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

Fra kodebiten ovenfor kan vi konkludere med at funksjonen fungerer som forventet!

Konklusjon 🧑‍💻

Her er en rask oppsummering av det du har lært.

• For det første ble du introdusert for problemet med kontroll av gyldige parenteser.
• Deretter lærte du en tilnærming for å løse problemet ved å bruke stabelen som den valgte datastrukturen.
• Deretter lærte du hvordan du validerer en parenteskombinasjon ved å bruke en Python-ordbok: med åpningsparenteser, tastene og de tilsvarende avsluttende parentesene som verdier.
• Til slutt definerte du Python-funksjonen for å sjekke om en gitt parentesstreng er gyldig.

Som et neste trinn, prøv å kode problemet på tipsbilk.nets online Python-redigeringsprogram. Ta gjerne en titt på denne guiden hvis du trenger hjelp!

Sjekk ut flere Python-opplæringer. Lykke til med kodingen!🎉