Gyldige parenteser i Python: En komplett guide

Sjekk av gyldige parenteser i Python

Denne veiledningen leder deg gjennom prosessen med å identifisere korrekte parentesstrukturer i Python.

Gitt en samling parenteser, er det en vanlig programmeringsutfordring å avgjøre om rekkefølgen av parentesene er gyldig. I løpet av de kommende minuttene vil du lære strategien for å håndtere denne problemstillingen, samt utvikle en Python-funksjon for å verifisere en gitt streng.

Hva er egentlig problemet med gyldige parenteser?

La oss begynne med å definere hva problemet med gyldige parenteser innebærer.

Du får en tekststreng som inneholder vanlige parenteser, krøllparenteser og hakeparenteser: (), {} og []. Oppgaven din er å undersøke om kombinasjonen av disse parentesene i strengen er lovlig.

En gyldig parentesstreng må oppfylle disse to kravene:

• Hver startparentes må ha en tilhørende sluttparentes av samme type.
• Parentesene må lukkes i korrekt rekkefølge.

Her er noen eksempler som illustrerer gyldige og ugyldige parentesstrenger.

test_str = "{}]" --> UGYLDIG, ] ble aldri åpnet
test_str = "[{}]" --> GYLDIG
test_str = "[]" --> GYLDIG
test_str = "[]{}" --> GYLDIG
test_str = "[{]}" --> UGYLDIG, parentesene er lukket feil!

For å løse dette problemet vil vi benytte oss av datastrukturen som kalles en stabel. La oss derfor repetere de grunnleggende prinsippene for en stabel i det neste avsnittet.

Repetisjon av stabeldatastrukturen

En stabel er en LIFO (Last In First Out) datastruktur. Det betyr at elementer legges til på toppen av stabelen, og de fjernes også fra toppen.

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

Vi vil anvende følgende to regler for å etablere en serie handlinger som vi kan gjennomføre på parentesstrengen:

• Legg alle startparentesene inn på stabelen.
• Når du støter på en sluttparentes, fjern det øverste elementet fra stabelen.

La oss nå gå videre og løse oppgaven med å sjekke gyldige parenteser.

Hvordan sjekke gyldigheten av parenteser

Ved å samle alle observasjonene fra eksemplene over, har vi følgende.

Undersøk lengden på parentesstrengen: Hvis oddetall, er strengen ugyldig

Siden hver startparentes må ha en tilsvarende sluttparentes, skal en gyldig streng ha et partall antall tegn. Hvis strengens lengde er et oddetall, kan vi umiddelbart konkludere med at kombinasjonen av parenteser er ugyldig.

    # len(test_str) = 3 (odde); ] har ingen tilsvarende start [
    test_str = "{}]"
    
    # len(test_str) = 3 (odde); ( har ingen tilsvarende slutt )
    test_str = "[(]"

    # len(test_str) = 5 (odde); det er en overflødig )
    test_str = "{())}"
  

La oss nå undersøke hvordan vi skal gå frem når antall tegn i strengen er partall.

Lengden på parentesstrengen er partall: hva nå?

Trinn 1: Gå gjennom strengen fra venstre mot høyre. La oss kalle strengen test_str og hvert enkelt tegn i strengen char.

Trinn 2: Hvis det første tegnet er en startparentes (, {, eller [, legg det til toppen av stabelen og fortsett til neste tegn i strengen.

Trinn 3: Sjekk om det neste tegnet (char) er en start- eller sluttparentes.

Trinn 3.1: Hvis det er en startparentes, legg det også på stabelen.

Trinn 3.2: Hvis du derimot støter på en sluttparentes, fjern det øverste elementet fra stabelen og fortsett til trinn 4.

Trinn 4: Her er det igjen tre muligheter basert på verdien som fjernes fra stabelen:

Trinn 4.1: Hvis det er en startparentes av samme type, gå tilbake til trinn 3.

Trinn 4.2: Hvis det er en startparentes av en annen type, kan du konkludere med at det ikke er en gyldig parentesstreng.

Trinn 4.3: Den siste muligheten er at stabelen er tom. Også dette indikerer en ugyldig streng, siden du har støtt på en sluttparentes uten en tilhørende startparentes.

Gjennomgang av eksempler på gyldige parentesstrenger

La oss nå se på tre eksempler og gå gjennom trinnene ovenfor.

📑 Hvis du allerede har forstått hvordan dette fungerer, kan du gjerne hoppe over til neste avsnitt.

#1. Som et første eksempel, la test_str = «{()».

• { er det første tegnet og er en startparentes, så du legger den på stabelen.
• Det neste tegnet ( er også en startparentes, så legg det også på stabelen.
• Det tredje tegnet i strengen ) er en sluttparentes, så du må fjerne det øverste elementet fra stabelen, som er (.
• På dette tidspunktet har du nådd slutten av strengen. Men stabelen inneholder fortsatt startparentesen { som aldri ble lukket. Derfor er den gitte parentesstrengen test_str ugyldig.

#2. I dette andre eksemplet, la test_str = «()]»

• Det første tegnet ( er en startparentes; skyv den til stabelen.
• Det andre tegnet ) er en sluttparentes; fjern det øverste elementet fra stabelen, som tilfeldigvis er ( – en startparentes av samme type. Fortsett til neste tegn.
• Det tredje tegnet ] er en slutt hakeparentes, og du bør fjerne det øverste elementet igjen. Men som du ser er stabelen tom – som betyr at det ikke finnes en matchende startparentes [. Derfor er denne strengen ugyldig.

#3. I dette siste eksemplet er test_str = «{()}».

• De to første tegnene {( er startparenteser, så legg dem på stabelen.
• Det tredje tegnet er en slutt ), så fjern det øverste elementet fra stabelen – (.
• Det neste tegnet } er en slutt krøllparentes, og når du fjerner det øverste elementet fra stabelen, får du { – en start krøllparentes.
• Etter at du har gått gjennom hele strengen, er stabelen tom og test_str er gyldig! ✅

📌 Jeg har utarbeidet et flytskjema som oppsummerer trinnene i problemstillingen med sjekk av gyldige parenteser. Du kan lagre det for rask referanse!

La oss i neste avsnitt se hvordan vi oversetter denne strategien til Python-kode.

Python-program for å sjekke gyldigheten av parenteser

I Python kan du benytte en liste for å simulere en stabel.

Du kan bruke metoden .append() for å legge til elementer på slutten av listen. Dette tilsvarer å legge til et element på toppen av stabelen.

Metoden .pop() returnerer det siste elementet fra listen, noe som er det samme som å fjerne det øverste elementet fra stabelen – altså det sist tilføyde elementet.

Du vet nå hvordan du utfører push- og pop-operasjonene på en Python-liste for å etterligne en stabel.

La oss nå se på hvordan vi kan skille mellom start- og sluttparenteser.

Du kan bruke en Python-ordbok med startparentesene ‘{‘, ‘[‘, ‘(‘ som nøkler, og de tilhørende sluttparentesene ‘}’, ‘]’, ‘)’ som verdier. Du kan bruke metoden .keys() for å få tilgang til de individuelle nøklene i ordboken.

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

Forstå funksjonsdefinisjonen

Ta en titt på kodesnutten nedenfor, som inneholder funksjonsdefinisjonen. Du vil se at vi har brukt trinnene fra flytskjemaet sammen med forklaringen ovenfor.

I tillegg har vi også lagt til en docstring som omfatter:

• en kort beskrivelse av funksjonen
• argumentene som funksjonen tar inn
• returverdiene fra funksjonen

▶ Du kan bruke help(is_valid) eller is_valid.__doc__ for å hente docstringen.

    def isValid(test_str):
      '''Sjekker om en gitt parentesstreng er gyldig.
    
      Args:
        test_str (str): Parentesstrengen som skal valideres
      
      Returns:
        True hvis test_str er gyldig; ellers False 
      '''
      # len(test_str) er odde -> ugyldig!
      if len(test_str)%2 != 0:
        return False
      # initialiserer parentesordbok
      par_dict = {'(':')','{':'}','[':']'}
      stack = []
      for char in test_str:
        # legger startparentes til stabelen
        if char in par_dict.keys():
          stack.append(char)
        else:
          # sluttparentes uten tilhørende startparentes
          if stack == []:
              return False
          # hvis sluttparentes -> fjern det øverste elementet fra stabelen
          open_brac = stack.pop()
          # ikke tilhørende parentes -> ugyldig!
          if char != par_dict[open_brac]:
            return False
      return stack == []
  

Python-funksjonen is_valid kontrollerer om parentesstrengen er gyldig og fungerer som følger.

• Funksjonen is_valid tar inn en 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 stabelen Python-listen som simulerer stabelen.
• Og par_dict er Python-ordboken, med startparenteser som nøkler og tilsvarende sluttparenteser som verdier.
• Mens vi går gjennom strengen, returnerer funksjonen False og avsluttes hvis vi støter på en tilstand som gjør parentesstrengen ugyldig.
• Etter å ha gått gjennom alle tegnene i strengen, sjekker stack == [] om stabelen er tom. Hvis dette er tilfellet, er test_str gyldig, og funksjonen returnerer True. Ellers returnerer funksjonen False.

La oss nå gå videre og foreta noen funksjonskall for å bekrefte at funksjonen 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 kodesnutten 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 problemstillingen med å sjekke gyldigheten av parenteser.
• Deretter lærte du en tilnærming for å løse problemet ved å bruke stabelen som den foretrukne datastrukturen.
• Videre lærte du hvordan du validerer en parenteskombinasjon ved å bruke en Python-ordbok: med startparentesene som nøkler og de tilhørende sluttparentesene som verdier.
• Til slutt definerte du en Python-funksjon for å sjekke om en gitt parentesstreng er gyldig.

Som et neste steg kan du prøve å kode dette problemet på en nettbasert Python-editor. Ta gjerne en titt på denne guiden hvis du trenger hjelp!

Sjekk ut flere Python-veiledninger. Lykke til med programmeringen!🎉