1121 : สามวงเล็บ (threeparen)
Problem type : Batch
Time limit : 1.0 second(s)
Memory limit : 32 megabyte(s)
พิจารณาสตริงที่ประกอบด้วยเครื่องหมายวงเล็บ 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

ความช่วยเหลือ: ไม่มีคำใบ้สำหรับปัญหานี้

กำลังออนไลน์: 17 ผู้เยี่ยมชมและ 0 สมาชิก (1 บอท)