Hoe te controleren op geldige haakjes in Python

In deze zelfstudie leert u te controleren op geldige haakjes in Python.

Gezien een reeks haakjes, is het controleren of de combinatie van haakjes geldig is een populaire coderingsinterviewvraag. En in de komende minuten leer je de techniek om deze vraag op te lossen en ook een Python-functie te coderen om een ​​bepaalde string te valideren.

Wat is het probleem met geldige haakjes?

Laten we onze discussie beginnen door de vraag te beantwoorden: wat is het geldige probleem met haakjes?

Gegeven een string met de karakters eenvoudige haakjes, accolades en vierkante accolades: () [] {}, moet u controleren of de combinatie van haakjes geldig is.

Een geldige tekenreeks met haakjes voldoet aan de volgende twee voorwaarden:

  • Elke openingsbeugel moet een bijpassende sluitbeugel van hetzelfde type hebben.
  • De haakjes moeten in de juiste volgorde worden gesloten.
  • Hier zijn een paar voorbeelden van geldige en ongeldige tekenreeksen voor haakjes.

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

    In onze probleemoplossende aanpak is de stapel de datastructuur die een cruciale rol zal spelen. Laten we de basisprincipes van een stapel bekijken in de volgende sectie.

    De stapelgegevensstructuur opnieuw bezocht

    De stapel is een last in first out (LIFO) datastructuur, waar u elementen aan de bovenkant van de stapel kunt toevoegen en ze ook van de bovenkant van de stapel kunt verwijderen.

    Wanneer u een element aan de stapeltop toevoegt, voert u een push-bewerking uit, wanneer u een element van de stapeltop verwijdert, voert u een pop-bewerking uit.

    We gebruiken de volgende twee regels om een ​​reeks bewerkingen te bedenken die we kunnen uitvoeren op de tekenreeks met haakjes.

    • Duw alle openingsbeugels op de stapel.
    • Als je een sluithaakje tegenkomt, spring dan van de stapel.

    Laten we doorgaan met het oplossen van het probleem met het controleren van de geldige haakjes.

    Hoe te controleren op geldige haakjes

    Als we alle observaties uit de bovenstaande voorbeelden samenvoegen, hebben we het volgende.

    Controleer de lengte van de tekenreeks tussen haakjes: Indien oneven, is de tekenreeks ongeldig

    Omdat elke openingshaak een haakje sluiten moet hebben, moet een geldige string een even aantal tekens bevatten. Als de lengte van de string oneven is, kun je meteen concluderen dat deze een ongeldige combinatie van haakjes heeft.

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

    Laten we vervolgens eens kijken hoe we kunnen aanpakken wanneer het aantal tekens in de string even is

      Hoe de AT&T U-verse gateway-authenticatiefout op te lossen?

    De lengte van de reeks tussen haakjes is even: wat nu?

    Stap 1: Beweeg de string van links naar rechts. Laten we de string test_str noemen, en de individuele karakters in de string char.

    Stap 2: Als het eerste teken char een openingshaakje is (, {, of [, 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 = “()]”

    • Het eerste teken ( is een openingshaakje; duw het naar de stapel.
    • Het tweede teken ) is een haakje sluiten; spring van de stapeltop, wat toevallig ) is – een openingsbeugel van hetzelfde type. Ga naar het volgende teken.
    • Het derde teken ]is een afsluitend vierkant haakje en je zou weer van de stapel moeten springen. Zoals u kunt zien, is de stapel echter leeg, wat betekent dat er geen bijpassende openingshaak is [. Hence, this string is invalid.
      Gegevens uit meerdere cellen samenvoegen in Google Spreadsheets

    #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 ‘}’, ‘]’, ‘)’ als de waarden. U kunt de methode .keys() gebruiken om toegang te krijgen tot afzonderlijke sleutels in het woordenboek.

    Laten we alles wat we hebben geleerd gebruiken om de definitie van de functie is_valid() te schrijven.

    De functiedefinitie begrijpen

    Lees de volgende codecel door die de functiedefinitie bevat. U kunt zien dat we de stappen in het stroomdiagram hebben gebruikt in combinatie met de bovenstaande uitleg.

    Daarnaast hebben we ook een docstring inclusief:

    • een korte beschrijving van de functie
    • de argumenten in de functieaanroep
    • de geretourneerde waarden van de functie

    ▶ U kunt help(is_valid) of is_valid.__doc__ gebruiken om de docstring op te halen.

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

    De Python-functie is_valid controleert of de tekenreeks met haakjes geldig is en werkt als volgt.

    • De functie is_valid neemt één parameter op, test_str, de tekenreeks met haakjes die moet worden gevalideerd. Het geeft True of False terug, afhankelijk van of de string test_str geldig is of niet.
    • Hier is stack de Python-lijst die de stapel emuleert.
    • En par_dict is het Python-woordenboek, met haakjes openen als de sleutels en haakjes sluiten als de bijbehorende waarden.
    • Als we tijdens het doorlopen van de tekenreeks een voorwaarde tegenkomen die de tekenreeks met haakjes ongeldig maakt, retourneert de functie False en wordt afgesloten.
    • Nadat u alle tekens in de tekenreeks hebt doorlopen, stapelt u == [] controleert of de stapel leeg is. Zo ja, dan is test_str geldig en retourneert de functie True. Anders retourneert de functie False.
      Opmerkingen toevoegen en verwijderen in Word

    Laten we nu een paar functieaanroepen doen om te controleren of onze functie correct werkt.

    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

    Uit het bovenstaande codefragment kunnen we concluderen dat de functie werkt zoals verwacht!

    Conclusie

    Hier is een korte samenvatting van wat je hebt geleerd.

    • Ten eerste maakte u kennis met het probleem van het controleren van geldige haakjes.
    • Vervolgens heb je een aanpak geleerd om het probleem op te lossen met behulp van de stapel als de datastructuur naar keuze.
    • Vervolgens heb je geleerd hoe je een combinatie van haakjes valideert met behulp van een Python-woordenboek: met haakjes openen, de sleutels en de bijbehorende haakjes sluiten als de waarden.
    • Ten slotte heb je de Python-functie gedefinieerd om te controleren of een gegeven tekenreeks met haakjes geldig is.

    Probeer als volgende stap het probleem te coderen in de online Python-editor van epcdream.nl. Voel je vrij om deze gids opnieuw te bezoeken als je hulp nodig hebt!

    Bekijk meer Python-tutorials. Veel plezier met coderen!

    gerelateerde berichten