Hur man kontrollerar giltiga parenteser i Python

I den här handledningen kommer du att utforska hur man identifierar korrekta parentesstrukturer i Python.

Att avgöra om en given sträng av parenteser är giltig är en återkommande fråga i kodningsintervjuer. Under de kommande minuterna kommer du att lära dig strategier för att hantera denna utmaning och implementera en Python-funktion för att verifiera en sträng.

Vad innebär problemställningen med giltiga parenteser?

Låt oss börja med att klargöra vad problemet med giltiga parenteser egentligen handlar om.

Med en sträng bestående av enkla parenteser, måsvingar och hakparenteser: () [] {}, är uppgiften att kontrollera om den givna kombinationen av parenteser är korrekt eller inte.

En korrekt parentessträng måste uppfylla dessa två kriterier:

• Varje öppningsparentes måste ha en motsvarande stängningsparentes av samma typ.
• Parenteserna måste stängas i den korrekta ordningen.

Här är några exempel som visar giltiga och ogiltiga parentessträngar.

test_str = "{}]" --> OGILTIG, ] har aldrig öppnats
test_str = "[{}]" --> GILTIG
test_str = "[]" --> GILTIG
test_str = "[]{}" --> GILTIG
test_str = "[{]}" --> OGILTIG, parenteserna stängs felaktigt!

I vår strategi för problemlösning kommer datastrukturen stack att spela en central roll. Låt oss utforska grunderna för en stack i nästa avsnitt.

En återblick på datastrukturen stack

En stack är en LIFO-datastruktur (last in, first out), där element läggs till och tas bort från stackens topp.

När du lägger till ett element på stackens topp utförs en push-operation, och när du tar bort ett element från toppen utförs en pop-operation.

Vi kommer att använda följande två riktlinjer för att skapa en uppsättning operationer som vi kan applicera på parentessträngen:

• Placera alla öppningsparenteser på stacken.
• När du stöter på en stängningsparentes, ta bort det översta elementet från stacken.

Låt oss fortsätta för att lösa problemet med att verifiera giltiga parenteser.

Metod för att kontrollera giltiga parenteser

Genom att sammanfatta alla observationer från exemplen ovan, har vi följande strategi.

Granska längden på parentessträngen: Udda längd innebär ogiltig sträng

Eftersom varje inledande parentes måste ha en motsvarande stängningsparentes, bör en giltig sträng innehålla ett jämnt antal tecken. Om strängens längd är udda, kan du direkt dra slutsatsen att den har en felaktig kombination av parenteser.

# len(test_str) = 3 (udda); ] saknar en öppnings [
test_str = "{}]"

# len(test_str) = 3 (udda); ( saknar en stängnings )
test_str = "[(]"

# len(test_str) = 5 (udda); det finns en felaktig )
test_str = "{())}"

Låt oss sedan undersöka hur vi ska hantera situationer där antalet tecken i strängen är jämnt.

Jämn längd på parentessträngen: Vad kommer härnäst?

Steg 1: Gå igenom strängen från vänster till höger. Låt oss referera till strängen som test_str, och de enskilda tecknen i strängen som char.

Steg 2: Om det första tecknet är en öppningsparentes (, {, eller [, placera det högst upp i stacken och gå vidare till nästa tecken i strängen.

Steg 3: Kontrollera om nästa tecken (char) är en öppnings- eller stängningsparentes.

Steg 3.1: Om det är en öppningsparentes, placera den igen på stacken.

Steg 3.2: Om du stöter på en stängningsparentes istället, ta bort det översta elementet från stacken och fortsätt till steg 4.

Steg 4: Här finns det återigen tre möjligheter baserat på det värde som togs bort från stacken:

Steg 4.1: Om det är en öppningsparentes av samma typ, gå tillbaka till steg 3.

Steg 4.2: Om det är en öppningsparentes av en annan typ, kan du återigen dra slutsatsen att det inte är en giltig parentessträng.

Steg 4.3: Det sista alternativet är att stacken är tom. Även detta är ett fall av en ogiltig sträng, eftersom du har stött på en stängningsparentes som saknar en motsvarande öppningsparentes.

Exempel på genomgång av giltiga parentessträngar

Låt oss nu granska tre exempel steg för steg genom att följa de ovanstående anvisningarna.

📑 Om du redan har förstått hur det fungerar, är du välkommen att gå vidare till nästa avsnitt.

#1. I det första exemplet, låt test_str = “{()”.

• { är det första tecknet, och det är en öppningsparentes, så placera det i stacken.
• Nästa tecken ( är också en öppningsparentes, så lägg även till det i stacken.
• Det tredje tecknet i strängen ) är en stängningsparentes, så du måste ta bort det översta elementet från stacken, vilket returnerar (.
• Vid den här tidpunkten har du nått slutet av strängen. Men stacken innehåller fortfarande den öppna { , som aldrig stängdes. Så den givna parentessträngen test_str är ogiltig.

#2. I det andra exemplet, låt test_str = “()]”

• Det första tecknet ( är en öppningsparentes; lägg till det i stacken.
• Det andra tecknet ) är en stängningsparentes; ta bort stackens topp, som råkar vara (. Fortsätt till nästa tecken.
• Det tredje tecknet ] är en stängande hakparentes, och du bör ta bort högen igen. Men som du kan se är stacken tom – vilket betyder att det inte finns någon matchande öppningsparentes [. Därför är denna sträng ogiltig.

#3. I det sista exemplet, test_str = “{()}”.

• De två första tecknen {( är öppningsparenteser, så placera dem i stacken.
• Det tredje tecknet är en stängningsparentes ), så ta bort det översta elementet från stacken – (.
• Nästa tecken } är en stängande måsvinge, och när du tar bort det översta elementet från stacken får du { – en öppnande måsvinge.
• När du har gått igenom hela strängen är stacken tom och test_str är giltig! ✅

📌 Jag har sammanställt följande flödesschema som beskriver stegen i problemet med att verifiera giltiga parenteser. Du kan spara det för snabb referens!

I nästa avsnitt ska vi se hur vi omvandlar vårt koncept till Python-kod.

Python-program för att kontrollera giltiga parenteser

I Python kan du använda en lista för att simulera en stack.

Du kan använda metoden .append() för att lägga till element i slutet av listan. Detta liknar att lägga till högst upp i stacken.

Metoden .pop() returnerar det sista elementet från listan, och detta liknar att ta bort det översta elementet från stacken – för att ta bort det senast tillagda elementet.

Så nu vet du hur du implementerar push- och pop-operationer på en Python-lista, och simulerar därmed en stack.

Låt oss nu ta nästa steg och svara på frågan: hur skiljer vi mellan öppnings- och stängningsparenteser?

Jo, du kan använda en Python-ordbok – med öppningsparenteserna ’{’, ’[’, ’(’ som nycklar i ordlistan och motsvarande stängningsparenteser ’}’, ’]’, ’)’ som värden. Du kan använda metoden .keys() för att komma åt de enskilda nycklarna i ordlistan.

Låt oss använda allt vi har lärt oss för att skriva definitionen av funktionen is_valid().

Förståelse av funktionsdefinitionen

Ta en titt på följande kodcell som innehåller funktionsdefinitionen. Du ser att vi har använt stegen i flödesschemat tillsammans med ovanstående förklaring.

Dessutom har vi även lagt till en docstring, som innehåller:

• en kort beskrivning av funktionen
• argumenten i funktionsanropet
• returvärdena från funktionen

▶ Du kan använda help(is_valid) eller is_valid.__doc__ för att hämta docstringen.

def isValid(test_str):
  '''Kontrollera om en given parentessträng är giltig.

  Argument:
    test_str (str): Parentessträngen som ska valideras
  
  Returnerar:
    True om test_str är giltig; annars False 
  '''
  # len(test_str) är udda -> ogiltig!
  if len(test_str)%2 != 0:
    return False
  # initiera parentesordbok
  par_dict = {'(':')','{':'}','[':']'}
  stack = []
  for char in test_str:
    # lägg till öppningsparentes i stacken
    if char in par_dict.keys():
      stack.append(char)
    else:
      # stängningsparentes utan matchande öppningsparentes
      if stack == []:
          return False
      # om stängningsparentes -> ta bort översta elementet från stacken
      open_brac = stack.pop()
      # icke-matchande parentes -> ogiltig!
      if char != par_dict[open_brac]:
        return False
  return stack == []

Python-funktionen is_valid undersöker om parentessträngen är giltig, och den fungerar på följande sätt.

• Funktionen is_valid tar in en parameter, test_str, som är parentessträngen som ska valideras. Den returnerar True eller False beroende på om strängen test_str är giltig eller inte.
• Här är stacken en Python-lista som simulerar en stack.
• Och par_dict är en Python-ordbok, med öppningsparenteserna som nycklar och stängningsparenteserna som motsvarande värden.
• När vi går igenom strängen, om vi stöter på ett tillstånd som gör parentessträngen ogiltig, returnerar funktionen False och avslutas.
• Efter att ha gått igenom alla tecken i strängen, kontrollerar stack == [] om stacken är tom. Om så är fallet, är test_str giltig och funktionen returnerar True. Annars returnerar funktionen False.

Nu ska vi fortsätta och göra några funktionsanrop för att verifiera att vår funktion fungerar som den ska.

str1 = '{}[]'
isValid(str1)
# Utdata: True

str2 = '{((}'
isValid(str2)
# Utdata: False

str3 = '[{()}]'
isValid(str3)
# Utdata: True

str4 = '[{)}]'
isValid(str4)
# Utdata: False

str5 = '[[]}'
isValid(str5)
# Utdata: False

Från kodavsnittet ovan kan vi konstatera att funktionen fungerar som förväntat!

Slutsats 🧑‍💻

Här är en kort sammanfattning av vad du har lärt dig.

• Först blev du introducerad till problemet med att verifiera giltiga parenteser.
• Därefter fick du lära dig en metod för att lösa problemet med hjälp av stacken som en lämplig datastruktur.
• Du lärde dig sedan hur man validerar en parenteskombination med hjälp av en Python-ordbok: med öppningsparenteser som nycklar och motsvarande stängningsparenteser som värden.
• Slutligen definierade du en Python-funktion för att kontrollera om en given parentessträng är giltig.

Som nästa steg, prova att koda problemet i en online Python-editor. Känn dig fri att besöka den här guiden igen om du behöver hjälp!

Utforska fler Python-tutorials. Lycka till med kodningen!🎉