โจทย์ "สามวงเล็บ (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
วิเคราะห์โจทย์
- รับค่าข้อมูลจำนวน 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
