ฝึกการเเก้โจทย์ด้วย Python โจทย์ "สามวงเล็บ (Threeparen)"

โจทย์ "สามวงเล็บ (Threeparen)"

       พิจารณาสตริงที่ประกอบด้วยเครื่องหมายวงเล็บ 3 ชนิด คือวงเล็บกลม ( ) วงเล็บเหลี่ยม [ ] และวงเล็บปีกกา { } เราจะเรียกสตริงหนึ่งว่าเป็น "สตริงวงเล็บสมดุล" เมื่อวงเล็บในสตริงนั้นสามารถจับคู่กันได้อย่างถูกต้อง ซึ่งเราสามารถนิยามสตริงวงเล็บสมดุลอย่างเป็นทางการได้ดังนี้

       1. (), [] และ {} เป็นสตริงวงเล็บสมดุล

       2. ถ้า A เป็นสตริงวงเล็บสมดุล แล้ว (A), [A] และ {A} ก็เป็นสตริงวงเล็บสมดุลเช่นกัน

       3. ถ้า A และ B เป็นสตริงวงเล็บสมดุล แล้ว AB ก็เป็นสตริงวงเล็บสมดุลเช่นกัน

       สังเกตว่า เราจะสามารถสร้างสตริงวงเล็บสมดุลความยาวต่างๆ ได้โดยใช้กฎสามข้อข้างบนนี้ เช่น เราสามารถสร้าง [(){}] โดยเริ่มจากใช้กฎข้อที่ 1 สร้าง () และ {} แล้วใช้กฎข้อที่ 3 สร้าง (){} แล้วจึงใช้กฎข้อที่ 2 สร้าง [(){}]

งานของคุณ

จงเขียนโปรแกรมเพื่อตอบคำถามทั้งหมด Q คำถามว่า สตริงที่ให้มาเป็นสตริงวงเล็บสมดุลหรือไม่

ข้อมูลนำเข้า

บรรทัดแรกระบุจำนวนเต็ม Q (2 ≤ Q ≤ 10) แทนจำนวนคำถามทั้งหมด

อีก Q บรรทัดต่อมา ในบรรทัดที่ i+1 (1 ≤ i ≤ Q) จะมีสตริงในคำถามที่ i ซึ่งแต่ละสตริงจะประกอบไปด้วยเครื่องหมายวงเล็บกลม วงเล็บเหลี่ยม หรือวงเล็บปีกกาเท่านั้น และแต่ละสตริงจะมีความยาวไม่เกิน 100,000

ข้อมูลส่งออก

มีทั้งหมด Q บรรทัด โดยในบรรทัดที่ i (1 ≤ i ≤ Q) ให้พิมพ์ yes ถ้าสตริงในคำถามที่ i เป็นสตริงวงเล็บสมดุล และพิมพ์ no ถ้าสตริงในคำถามที่ i ไม่เป็นสตริงวงเล็บสมดุล

การให้คะแนน

30% ของข้อมูลทดสอบ สตริงในคำถามทุกสตริงจะประกอบด้วยวงเล็บเพียงชนิดเดียวเท่านั้น คือวงเล็บกลม

50% ของข้อมูลทดสอบ สตริงในคำถามทุกสตริงจะมีความยาวไม่เกิน 100

15% ของข้อมูลทดสอบ จะสอดคล้องกับเงื่อนไขด้านบนทั้งสองข้อ 

ที่มา

การแข่งขัน IOI Thailand League เดือนมิถุนายน 2553

โจทย์โดย: สุธี เรืองวิเศษ

ตัวอย่างข้อมูลนำเข้า ตัวอย่างข้อมูลส่งออก

3

(())            yes

(()))(()        no

(()())() yes 

3

({])[]          no

[({}])          no

()[{}()] yes

ความช่วยเหลือ: ไม่มีคำใบ้สำหรับปัญหานี้
ที่มาของโจทย์: www.programming.in.th

วิเคราะห์โจทย์ 

• รับค่าข้อมูลจำนวน 2 ค่า คือค่า จำนวนข้อมูลที่ต้องการตรวจสอบ เเละ ข้อมูลของ วงเล็บ
• ทำการตรวจสอบข้อมูลว่าถูกต้องหรือไม่

เเนวคิดในการเเก้โจทย์ 

• ทำการตรวจสอบเป็น "คู่" ว่าถูกต้องหรือไม่ถ้าถูกก็ให้เอาข้อมูลออกจาก List เเล้วเอาข้อมูลใน List ไปตรวจสอบ คือถ้ายังมีข้อมูลเหลืออยู่ใน List เเสดงว่าข้อมูลนั้นไม่ถูกต้อง เเต่ถ้าไม่มีข้อมูลเหลืออยู่เเสดงว่าข้อมูลนั้นถูกต้อง  

Code Python 

 
     def Get_Data(Input):
         New_List = []
             for i in range(len(Input)):
                 New_List.append(Input[i])
         return Check_Twain(New_List)
                       
     def Check_Twain(List_Data):
         for b in range(int((len(List_Data)/2)+1)):
             for a in range(len(List_Data)-1):
                 if List_Data[a] == "(" and List_Data[a+1] == ")" or List_Data[a] == "[" and List_Data[a+1] == "]" or List_Data[a] == "{" and List_Data[a+1] == "}":
                     List_Data.pop((a+1))
                     List_Data.pop(a)
                     break
         return len(List_Data)  
  
     Input_Number = int(input("กรุณาใส่จำนวนข้อมูลที่ต้องการตรวจสอบ : "))
     List_Data = []

     for i in range(Input_Number):
         List_Data.append(input("กรุณาใส่ข้อมูลที่ต้องการตรวจสอบ : "))
    
     for s in range(len(List_Data)):
         if Get_Data(List_Data[s]) > 0 :
             print (" no")
         else: 
             print(" yes")
                                                                  

ผลลัพธ์ที่ได้... 

         กรุณาใส่จำนวนข้อมูลที่ต้องการตรวจสอบ : 3
         กรุณาใส่ข้อมูลที่ต้องการตรวจสอบ : (())
         กรุณาใส่ข้อมูลที่ต้องการตรวจสอบ : (()))(()
         กรุณาใส่ข้อมูลที่ต้องการตรวจสอบ : (()())()
          yes
          no
          yes

         กรุณาใส่จำนวนข้อมูลที่ต้องการตรวจสอบ : 3
         กรุณาใส่ข้อมูลที่ต้องการตรวจสอบ : ({])[]
         กรุณาใส่ข้อมูลที่ต้องการตรวจสอบ : [({}])
         กรุณาใส่ข้อมูลที่ต้องการตรวจสอบ : ()[{}()]
          no
          no
          yes