Hur man kontrollerar giltiga parenteser i Python

I den här handledningen lär du dig att leta efter giltiga parenteser i Python.

Med tanke på en rad parenteser är det en populär kodningsintervjufråga att kontrollera om kombinationen av parenteser är giltig. Och under de närmaste minuterna kommer du att lära dig tekniken för att lösa denna fråga och även koda upp en Python-funktion för att validera en given sträng.

Innehållsförteckning

Vad är problemet med giltiga parenteser?

Låt oss börja vår diskussion med att svara på frågan, vad är problemet med giltiga parenteser?

Givet en sträng som innehåller tecknen enkla parenteser, lockiga och fyrkantiga klammerparenteser: () [] {} måste du kontrollera om den angivna parenteskombinationen är giltig eller inte.

En giltig parentessträng uppfyller följande två villkor:

Varje öppningsfäste måste ha ett matchande stängningsfäste av samma typ.

Fästena ska stängas i rätt ordning.

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

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ösningsstrategi är stacken datastrukturen som kommer att spela en avgörande roll. Låt oss gå igenom grunderna för en stack i nästa avsnitt.

Stackdatastrukturen återbesökt

Stacken är en sist in först ut (LIFO) datastruktur, där du kan lägga till element till toppen av stacken och även ta bort dem från toppen av stacken.

När du lägger till ett element till stacktoppen, utför du en push-operation, när du tar bort ett element från stack-toppen, utför du en pop-operation.

Vi kommer att använda följande två regler för att komma fram till en uppsättning operationer som vi kan utföra på parentessträngen.

Skjut alla öppningsfästen på stapeln.
Om du stöter på ett stängningsfäste, ta bort buntöverdelen.

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

Hur man kontrollerar giltiga parenteser

Genom att sammanställa alla observationer från exemplen ovan har vi följande.

Kontrollera längden på parentessträngen: Om den är udda är strängen Invalid

Eftersom varje inledande parentes måste ha en avslutande parentes, bör en giltig sträng innehålla ett jämnt antal tecken. Om längden på strängen är udda kan du dra slutsatsen direkt att den har en ogiltig kombination 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 = "{())}"

Låt oss sedan se hur vi kan hantera när antalet tecken i strängen är jämnt

Längden på parentessträngen är jämn: vad härnäst?

Steg 1: Traversera strängen från vänster till höger. Låt oss kalla strängen test_str, och de individuella tecknen i strängen char.

Steg 2: Om det första tecknet är en öppningsparentes (, {, 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örsta tecknet ( är en öppningsparentes; skjut den till stapeln.
Det andra tecknet ) är en avslutande parentes; skjut av stapelöverdelen, som råkar vara ) – ett öppningsfäste av samma typ. Fortsätt till nästa tecken.
Det tredje tecknet ]är en avslutande hakparentes, och du bör hoppa av högen igen. Men som du kan se är stacken tom – vilket betyder att det inte finns någon matchande öppningsparentes [. 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ärden. Du kan använda metoden .keys() för att komma åt enskilda nycklar i ordboken.

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

Förstå funktionsdefinitionen

Läs igenom följande kodcell som innehåller funktionsdefinitionen. Du kan se att vi har använt stegen i flödesschemat tillsammans med ovanstående förklaring.

Dessutom har vi också lagt till en docstring Inklusive:

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):
  '''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 kontrollerar om parentessträngen är giltig, och den fungerar enligt följande.

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 stack Python-listan som emulerar stacken.
Och par_dict är Python-ordboken, med öppnande parenteser som nycklar och avslutande parenteser som motsvarande värden.
När vi korsar strängen, om vi stöter på något tillstånd som gör parentessträngen ogiltig, returnerar funktionen False och avslutas.
Efter att ha korsat alla tecken i strängen, stapla == [] kontrollerar om stacken är tom. Om ja, är test_str giltig och funktionen returnerar True. Annars returnerar funktionen False.

Nu ska vi gå vidare och göra några funktionsanrop för att verifiera att vår funktion fungerar 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

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

Slutsats 🧑‍💻

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

För det första introducerades du till problemet med att kontrollera giltiga parenteser.
Därefter lärde du dig ett tillvägagångssätt för att lösa problemet med hjälp av stacken som valfri datastruktur.
Du lärde dig sedan hur man validerar en parenteskombination med hjälp av en Python-ordbok: med öppnande parenteser, nycklarna och motsvarande avslutande parenteser som värden.
Slutligen definierade du Python-funktionen för att kontrollera om en given parentessträng är giltig.

Som ett nästa steg, försök att koda problemet på adminvista.com online Python-redigerare. Besök gärna den här guiden igen om du behöver hjälp!

Kolla in fler Python-tutorials. Lycka till med kodningen!🎉