Πώς να ελέγξετε για έγκυρες παρενθέσεις στην Python

Σε αυτό το σεμινάριο, θα μάθετε να ελέγχετε για έγκυρες παρενθέσεις στην Python.

Λαμβάνοντας υπόψη μια σειρά από παρενθέσεις, ο έλεγχος εάν ο συνδυασμός παρενθέσεων είναι έγκυρος είναι μια δημοφιλής ερώτηση συνέντευξης κωδικοποίησης. Και μέσα στα επόμενα λεπτά, θα μάθετε την τεχνική για να λύσετε αυτήν την ερώτηση και θα κωδικοποιήσετε επίσης μια συνάρτηση Python για να επικυρώσετε μια δεδομένη συμβολοσειρά.

Ποιο είναι το πρόβλημα της έγκυρης παρένθεσης;

Ας ξεκινήσουμε τη συζήτησή μας απαντώντας στην ερώτηση, ποιο είναι το πρόβλημα της έγκυρης παρένθεσης;

Δίνεται μια συμβολοσειρά που περιέχει τους χαρακτήρες απλές παρενθέσεις, σγουρές και τετράγωνες αγκύλες: () [] {}, πρέπει να ελέγξετε αν ο συνδυασμός παρενθέσεων είναι έγκυρος ή όχι.

Μια έγκυρη συμβολοσειρά παρενθέσεων ικανοποιεί τις ακόλουθες δύο προϋποθέσεις:

  • Κάθε βραχίονας ανοίγματος πρέπει να έχει αντίστοιχο βραχίονα κλεισίματος του ίδιου τύπου.
  • Οι αγκύλες πρέπει να κλείσουν με τη σωστή σειρά.
  • Ακολουθούν μερικά παραδείγματα έγκυρων και μη έγκυρων συμβολοσειρών παρενθέσεων.

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

    Στην προσέγγισή μας επίλυσης προβλημάτων, η στοίβα είναι η δομή δεδομένων που θα παίξει κεντρικό ρόλο. Ας εξετάσουμε τα βασικά μιας στοίβας στην επόμενη ενότητα.

    Επανεξετάστηκε η δομή δεδομένων στοίβας

    Η στοίβα είναι μια δομή δεδομένων τελευταίας εισόδου (LIFO), όπου μπορείτε να προσθέσετε στοιχεία στην κορυφή της στοίβας και επίσης να τα αφαιρέσετε από την κορυφή της στοίβας.

    Όταν προσθέτετε ένα στοιχείο στο επάνω μέρος της στοίβας, εκτελείτε μια λειτουργία ώθησης, όταν αφαιρείτε ένα στοιχείο από το επάνω μέρος της στοίβας, εκτελείτε μια λειτουργία pop.

    Θα χρησιμοποιήσουμε τους παρακάτω δύο κανόνες για να καταλήξουμε σε ένα σύνολο πράξεων που μπορούμε να εκτελέσουμε στη συμβολοσειρά παρενθέσεων.

    • Σπρώξτε όλα τα ανοιγόμενα στηρίγματα στη στοίβα.
    • Αν συναντήσετε ένα βραχίονα κλεισίματος, βγείτε από το επάνω μέρος της στοίβας.

    Ας προχωρήσουμε στην επίλυση του προβλήματος ελέγχου έγκυρης παρένθεσης.

    Πώς να ελέγξετε για έγκυρες παρενθέσεις

    Συγκεντρώνοντας όλες τις παρατηρήσεις από τα παραπάνω παραδείγματα, έχουμε τα εξής.

      Τρόπος επαναφοράς μιας παρουσίασης PowerPoint

    Ελέγξτε το μήκος της συμβολοσειράς των παρενθέσεων: Αν είναι μονό, η συμβολοσειρά δεν είναι έγκυρη

    Καθώς κάθε αγκύλη ανοίγματος πρέπει να έχει μια αγκύλη κλεισίματος, μια έγκυρη συμβολοσειρά πρέπει να περιέχει ζυγό αριθμό χαρακτήρων. Εάν το μήκος της συμβολοσειράς είναι μονό, μπορείτε να συμπεράνετε αμέσως ότι έχει μη έγκυρο συνδυασμό παρενθέσεων.

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

    Στη συνέχεια, ας δούμε πώς μπορούμε να αντιμετωπίσουμε όταν ο αριθμός των χαρακτήρων στη συμβολοσειρά είναι ζυγός

    Το μήκος της συμβολοσειράς των παρενθέσεων είναι άρτιο: τι μετά;

    Βήμα 1: Διασχίστε τη συμβολοσειρά από αριστερά προς τα δεξιά. Ας ονομάσουμε τη συμβολοσειρά test_str και τους μεμονωμένους χαρακτήρες στη συμβολοσειρά char.

    Βήμα 2: Εάν ο πρώτος χαρακτήρας χαρακτήρων είναι μια αρχική αγκύλη (, {, ή [, 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.
      Πώς να παρακολουθήσετε το Netflix με τους φίλους σας στο Διαδίκτυο

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

    • Ο πρώτος χαρακτήρας ( είναι ένα ανοιγόμενο στήριγμα, σπρώξτε το στη στοίβα.
    • Ο δεύτερος χαρακτήρας ) είναι μια αγκύλη κλεισίματος. βγείτε από το επάνω μέρος της στοίβας, που τυχαίνει να είναι ) – ένα ανοιγόμενο στήριγμα του ίδιου τύπου. Προχωρήστε στον επόμενο χαρακτήρα.
    • Ο τρίτος χαρακτήρας ]είναι μια αγκύλη που κλείνει και θα πρέπει να βγείτε ξανά από την κορυφή της στοίβας. Ωστόσο, όπως μπορείτε να δείτε, η στοίβα είναι άδεια—πράγμα που σημαίνει ότι δεν υπάρχει αντίστοιχο πλαίσιο ανοίγματος [. 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 ‘}’, ‘]’, ‘)’ ως τιμές. Μπορείτε να χρησιμοποιήσετε τη μέθοδο .keys() για να αποκτήσετε πρόσβαση σε μεμονωμένα κλειδιά στο λεξικό.

    Ας χρησιμοποιήσουμε όλα όσα μάθαμε για να γράψουμε τον ορισμό της συνάρτησης is_valid().

      13 καλύτερες πλατφόρμες και ανταλλαγές κρυπτονομισμάτων το 2022

    Κατανόηση του ορισμού της συνάρτησης

    Διαβάστε το ακόλουθο κελί κώδικα που περιέχει τον ορισμό της συνάρτησης. Μπορείτε να δείτε ότι χρησιμοποιήσαμε τα βήματα στο διάγραμμα ροής παράλληλα με την παραπάνω εξήγηση.

    Επιπλέον, προσθέσαμε επίσης ένα docstring συμπεριλαμβανομένου:

    • μια σύντομη περιγραφή της λειτουργίας
    • τα ορίσματα στην κλήση συνάρτησης
    • τις επιστρεφόμενες τιμές από τη συνάρτηση

    ▶ Μπορείτε να χρησιμοποιήσετε help(is_valid) ή is_valid.__doc__ για να ανακτήσετε τη συμβολοσειρά εγγράφων.

    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 is_valid ελέγχει αν η συμβολοσειρά των παρενθέσεων είναι έγκυρη και λειτουργεί ως εξής.

    • Η συνάρτηση is_valid λαμβάνει μία παράμετρο, test_str που είναι η συμβολοσειρά παρενθέσεων που πρέπει να επικυρωθεί. Επιστρέφει True ή False ανάλογα με το αν η συμβολοσειρά test_str είναι έγκυρη ή όχι.
    • Εδώ, η στοίβα είναι η λίστα Python που μιμείται τη στοίβα.
    • Και το par_dict είναι το λεξικό Python, με τις αγκύλες ανοίγματος ως κλειδιά και τις αγκύλες κλεισίματος ως τις αντίστοιχες τιμές.
    • Κατά τη διέλευση της συμβολοσειράς, εάν συναντήσουμε οποιαδήποτε συνθήκη που καθιστά τη συμβολοσειρά των παρενθέσεων άκυρη, η συνάρτηση επιστρέφει False και βγαίνει.
    • Αφού διασχίσετε όλους τους χαρακτήρες της συμβολοσειράς, στοιβάστε == [] ελέγχει εάν η στοίβα είναι άδεια. Εάν ναι, το test_str είναι έγκυρο και η συνάρτηση επιστρέφει True. Διαφορετικά, η συνάρτηση επιστρέφει False.

    Τώρα, ας προχωρήσουμε και να κάνουμε μερικές κλήσεις συναρτήσεων για να επαληθεύσουμε ότι η λειτουργία μας λειτουργεί σωστά.

    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

    Από το παραπάνω απόσπασμα κώδικα, μπορούμε να συμπεράνουμε ότι η συνάρτηση λειτουργεί όπως αναμένεται!

    Συμπέρασμα 🧑‍💻

    Ακολουθεί μια γρήγορη περίληψη των όσων μάθατε.

    • Αρχικά, μυθήκατε στο πρόβλημα του ελέγχου έγκυρων παρενθέσεων.
    • Στη συνέχεια, μάθατε μια προσέγγιση για την επίλυση του προβλήματος χρησιμοποιώντας τη στοίβα ως δομή δεδομένων επιλογής.
    • Στη συνέχεια μάθατε πώς να επικυρώνετε έναν συνδυασμό παρενθέσεων χρησιμοποιώντας ένα λεξικό Python: με τιμές ανοίγματος, τα κλειδιά και τις αντίστοιχες αγκύλες κλεισίματος.
    • Τέλος, καθορίσατε τη συνάρτηση Python για να ελέγξετε εάν μια δεδομένη συμβολοσειρά παρενθέσεων είναι έγκυρη.

    Ως επόμενο βήμα, προσπαθήστε να κωδικοποιήσετε το πρόβλημα στον διαδικτυακό επεξεργαστή Python του grtechpc.org. Μη διστάσετε να επισκεφτείτε ξανά αυτόν τον οδηγό εάν χρειάζεστε βοήθεια!

    Δείτε περισσότερα μαθήματα Python. Καλή κωδικοποίηση!🎉