วิธีตรวจสอบวงเล็บที่ถูกต้องใน 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) ซึ่งคุณสามารถเพิ่มองค์ประกอบที่ด้านบนสุดของสแต็กและลบออกจากด้านบนสุดของสแต็กได้

    เมื่อคุณเพิ่มองค์ประกอบลงในสแต็กท็อป คุณจะต้องดำเนินการพุช เมื่อคุณลบองค์ประกอบออกจากสแต็กท็อป คุณจะดำเนินการป๊อปอัป

    เราจะใช้กฎสองข้อต่อไปนี้เพื่อสร้างชุดของการดำเนินการที่เราสามารถทำได้ในสตริงวงเล็บ

    • ดันวงเล็บเปิดทั้งหมดลงบนกอง
    • หากคุณเจอวงเล็บปิด ให้ดึงส่วนบนของสแตกออก

    มาแก้ปัญหาการตรวจสอบวงเล็บที่ถูกต้องกัน

    วิธีตรวจสอบวงเล็บที่ถูกต้อง

    เมื่อรวบรวมข้อสังเกตทั้งหมดจากตัวอย่างข้างต้น เรามีดังต่อไปนี้

    ตรวจสอบความยาวของสตริงวงเล็บ: ถ้าคี่ สตริงนั้นไม่ถูกต้อง

    เนื่องจากวงเล็บเปิดทุกอันต้องมีวงเล็บปิด สตริงที่ถูกต้องจึงควรมีอักขระเป็นจำนวนคู่ หากความยาวของสตริงเป็นเลขคี่ คุณสามารถสรุปได้ทันทีว่าวงเล็บมีวงเล็บที่ไม่ถูกต้อง

    # 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.

      Microsoft 365 คืออะไร?

    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 = “()]”

    • อักขระตัวแรก ( คือวงเล็บเปิด ดันไปที่สแต็ก
    • อักขระตัวที่สอง ) เป็นวงเล็บปิด โผล่ออกมาจากด้านบนของสแต็กซึ่งก็คือ ) – วงเล็บเปิดประเภทเดียวกัน ไปที่ตัวละครถัดไป
    • อักขระตัวที่สาม ]เป็นวงเล็บเหลี่ยมปิด และคุณควรดึงออกจาก stack top อีกครั้ง อย่างไรก็ตาม อย่างที่คุณเห็น สแต็กว่างเปล่า—ซึ่งหมายความว่าไม่มีวงเล็บเปิดที่ตรงกัน [. 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! ✅
      11 สุดยอดเครื่องมือโซเชียลมีเดีย Analytics และแดชบอร์ดข้อมูลธุรกิจ

    📌 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()

    การทำความเข้าใจนิยามฟังก์ชัน

    อ่านโค้ดเซลล์ต่อไปนี้ที่มีคำจำกัดความของฟังก์ชัน คุณจะเห็นว่าเราได้ใช้ขั้นตอนในผังงานควบคู่ไปกับคำอธิบายข้างต้น

    นอกจากนี้เรายังได้เพิ่ม a docstring รวมทั้ง:

    • คำอธิบายสั้น ๆ ของฟังก์ชัน
    • อาร์กิวเมนต์ในการเรียกใช้ฟังก์ชัน
    • ค่าที่ส่งกลับจากฟังก์ชัน

    ▶ คุณสามารถใช้ help(is_valid) หรือ is_valid.__doc__ เพื่อดึง docstring

    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 ถูกต้องหรือไม่
    • ที่นี่ stack เป็นรายการ Python ที่จำลอง stack
    • และ par_dict คือพจนานุกรม Python โดยมีวงเล็บเปิดเป็นคีย์และวงเล็บปิดเป็นค่าที่สอดคล้องกัน
    • ขณะสำรวจสตริง หากเราพบเงื่อนไขใด ๆ ที่ทำให้สตริงในวงเล็บไม่ถูกต้อง ฟังก์ชันจะคืนค่า False และออก
    • หลังจากผ่านอักขระทั้งหมดในสตริงแล้ว stack == [] ตรวจสอบว่า stack ว่างหรือไม่ ถ้าใช่ test_str ถูกต้อง และฟังก์ชันจะคืนค่า True มิฉะนั้น ฟังก์ชันจะคืนค่าเป็นเท็จ
      วิธีที่ง่ายที่สุดในการวิดีโอแชทกับครอบครัวในวันแม่

    ตอนนี้ ไปข้างหน้าและเรียกใช้ฟังก์ชันบางอย่างเพื่อตรวจสอบว่าฟังก์ชันของเราทำงานอย่างถูกต้อง

    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 ออนไลน์ของ admintrick.com โปรดอ่านคู่มือนี้อีกครั้งหากต้องการความช่วยเหลือ!

    ดูบทช่วยสอน Python เพิ่มเติม มีความสุขในการเข้ารหัส!🎉

    เรื่องล่าสุด

    x