สมมติว่าเรามีสตริงสตริงที่มีวงเล็บปีกกาเหล่านี้ '(', ')', '{', '}', '[' และ ']' เราต้องตรวจสอบว่าวงเล็บมีความสมดุลหรือไม่ เราสามารถพูดได้ว่าวงเล็บมีความสมดุลเมื่อประเภทวงเล็บเปิดและปิดเป็นประเภทเดียวกัน วงเล็บปิดในลำดับที่ถูกต้อง
ดังนั้น หากอินพุตเป็น {([])} ผลลัพธ์จะเป็น True
เพื่อแก้ปัญหานี้ เราจะทำตามขั้นตอนเหล่านี้ -
- cnt :=0
- ผม :=0
- j :=-1
- กำหนดฟังก์ชัน Solve() นี่จะใช้เวลา s, temp
- cnt :=cnt - 1
- s :=รายการใหม่จาก s
- ถ้า j> -1 และ s[j] เหมือนกับ temp แล้ว
- s[i] :='#'
- s[j] :='#'
- ในขณะที่ j>=0 และ s[j] เหมือนกับ '#' ให้ทำ
- j :=j - 1
- ผม :=ผม + 1>
- คืน 1
- มิฉะนั้น
- คืน 0
- จากวิธีหลัก ให้ทำดังต่อไปนี้ −
- ถ้าขนาดของ s เท่ากับ 0 แล้ว
- คืนค่า True
- มิฉะนั้น
- ตอบ :=ผิด
- ในขณะที่ i <ขนาดของ s ไม่ใช่ศูนย์ ให้ทำ
- ถ้า s[i] เหมือนกับ '}' แล้ว
- ตอบ :=แก้ (s, '{')
- ถ้า ans เหมือนกับ 0 แล้ว
- คืนค่าเท็จ
- มิฉะนั้น เมื่อ s[i] เหมือนกับ ')' แล้ว
- ตอบ :=แก้(s, '(')
- ถ้า ans เหมือนกับ 0 แล้ว
- คืนค่าเท็จ
- มิฉะนั้น เมื่อ s[i] เหมือนกับ ']' แล้ว
- ans :=แก้ (s, '[')
- ถ้า ans เหมือนกับ 0 แล้ว
- คืนค่าเท็จ
- มิฉะนั้น
- j :=ฉัน
- ผม :=ผม + 1
- cnt :=cnt + 1
- ถ้า s[i] เหมือนกับ '}' แล้ว
- ถ้า cnt ไม่เหมือนกับ 0 แล้ว
- คืนค่าเท็จ
- คืนค่า True
ตัวอย่าง
ให้เราดูการใช้งานต่อไปนี้เพื่อความเข้าใจที่ดีขึ้น -
cnt = 0
i = 0
j = -1
def solve(s, temp):
global i, j, cnt
cnt -= 1
s = list(s)
if j > -1 and s[j] == temp:
s[i] = '#'
s[j] = '#'
while j >= 0 and s[j] == '#':
j -= 1
i += 1
return 1
else:
return 0
def bracketOrderCheck(s):
global i, j, cnt
if len(s) == 0:
return True
else:
ans = False
while i < len(s):
if s[i] == '}':
ans = solve(s, '{')
if ans == 0:
return False
elif s[i] == ')':
ans = solve(s, '(')
if ans == 0:
return False
elif s[i] == ']':
ans = solve(s, '[')
if ans == 0:
return False
else:
j = i
i += 1
cnt += 1
if cnt != 0:
return False
return True
print(bracketOrderCheck("{([])}")) อินพุต
"{(()[])}" ผลลัพธ์
True
