สมมติว่ามีสตริงของวงเล็บ (วงกลม, วงปีกกา, เหลี่ยม) เราต้องตรวจสอบว่าวงเล็บสมดุล (well-formed) หรือไม่
เช่น ถ้าอินพุตคือ s = "([()()]{[]})()" ผลลัพธ์จะเป็น True
ขั้นตอนการแก้ปัญหา
- stack := รายการใหม่
- d := hash map มีคู่ ('}', '{'), (')', '('), (']', '[')
- สำหรับแต่ละตัวอักษร c ใน s
- ถ้า c เป็นหนึ่งใน '}])' ถ้า stack ว่างหรือ top ไม่เท่ากับ d[c] คืนค่า False, pop จาก stack
- มิฉะนั้น push c เข้า stack
- คืนค่า true ถ้า stack ว่าง มิฉะนั้น false
ตัวอย่างโค้ด
class Solution:
def solve(self, s):
stack = []
d = {'}': '{', ')': '(', ']': '['}
for c in s:
if c in '}])':
if not stack or stack[-1] != d[c]:
return False
stack.pop()
else:
stack.append(c)
return not stack
ob = Solution()
print(ob.solve("([()()]{[]})()"))
อินพุต
"([()()]{[]})()"
เอาต์พุต
True
