Kiểm tra dấu ngoặc cân bằng bằng Python (valid parentheses)
Bài 4/10 · Chương 25
Bài tập phỏng vấn Python
- 6 phút
- Trung cấp
- Python 3.14
- Cập nhật
Trong bài này · 11
Kiểm tra dấu ngoặc cân bằng bằng Python là hỏi các dấu ngoặc tròn, vuông, nhọn trong một chuỗi có đóng mở đúng cặp, đúng thứ tự không. Trình soạn thảo code làm việc này mỗi lần tô đỏ một dấu ngoặc thừa. Trang này đi từ cách đếm dấu tới cách dùng ngăn xếp, rồi cho bạn một bài tập được chấm ngay trên trang.
Cần biết trước: ngăn xếp, dict và duyệt chuỗi.
Đề bài
Viết hàm ngoac_can_bang(s) trả về True khi mọi dấu ngoặc (), [], {} trong s đóng mở đúng cặp và đúng thứ tự, False trong mọi trường hợp khác. Đúng thứ tự nghĩa là dấu mở sau cùng phải được đóng trước.
Ví dụ vào ra: "tong(gia[0], {2: 3})" cho True, "([)]" cho False.
Câu hỏi làm rõ trước khi viết code:
Ký tự không phải dấu ngoặc thì sao? Bỏ qua.
Chuỗi rỗng, hay chuỗi không có dấu ngoặc nào? Là cân bằng.
Dấu ngoặc nằm trong nháy của một dòng code, như
print("("), có được bỏ qua không? Ở bài này: không, dấu ngoặc nào cũng tính.
Cách 1: đếm số dấu mở và dấu đóng
Cách đầu tiên nhiều người nghĩ tới là đếm: mỗi loại ngoặc một biến đếm trong dict, dấu mở cộng 1, dấu đóng trừ 1. Số đếm âm nghĩa là đóng khi chưa mở, hết chuỗi mà còn số dương nghĩa là thiếu dấu đóng:
DONG_MO = {")": "(", "]": "[", "}": "{"}
def ngoac_can_bang(s):
dem = {"(": 0, "[": 0, "{": 0}
for c in s:
if c in dem:
dem[c] += 1
elif c in DONG_MO:
dem[DONG_MO[c]] -= 1
if dem[DONG_MO[c]] < 0:
return False
return dem["("] == 0 and dem["["] == 0 and dem["{"] == 0
for s in ["tong(gia[0], {2: 3})", "())(", "((", "([)]"]:
print(f"{s:<22}{ngoac_can_bang(s)}")KẾT QUẢ
tong(gia[0], {2: 3}) True
())( False
(( False
([)] TrueDict DONG_MO cho biết mỗi dấu đóng đi với dấu mở nào. Ba dòng đầu đúng. Dòng cuối sai: "([)]" đóng ) khi [ còn đang mở, vậy mà hàm trả True.
Vì sao đếm số dấu không đủ
Hàm đếm chỉ biết mỗi loại có bao nhiêu dấu đang mở, không biết dấu nào mở sau cùng. Với "([)]", số đếm của từng loại khớp hoàn toàn:
s = "([)]"
for mo, dong in ["()", "[]", "{}"]:
print(mo + dong, s.count(mo), s.count(dong))KẾT QUẢ
() 1 1
[] 1 1
{} 0 0Chỗ sai nằm ở thứ tự: khi gặp ), dấu mở gần nhất chưa đóng là [, còn ( đã mở trước nó. Đếm vẫn đủ khi chuỗi chỉ có một loại ngoặc. Có từ hai loại trở lên thì mỗi dấu đóng phải khớp với dấu mở gần nhất chưa đóng, tức dấu vào sau cùng: đúng thứ tự "vào sau, ra trước" của ngăn xếp.
Cách 2: ghép từng cặp bằng ngăn xếp
Mỗi dấu mở được đặt lên đỉnh ngăn xếp bằng append(). Mỗi dấu đóng lấy đỉnh ra bằng pop() và so với dấu mở mà DONG_MO cho:
DONG_MO = {")": "(", "]": "[", "}": "{"}
def ngoac_can_bang(s):
ngan_xep = []
for c in s:
if c in "([{":
ngan_xep.append(c)
elif c in DONG_MO:
if len(ngan_xep) == 0 or ngan_xep.pop() != DONG_MO[c]:
return False
return len(ngan_xep) == 0
for s in ["tong(gia[0], {2: 3})", "())(", "((", "([)]", ""]:
print(f"{s!r:<24}{ngoac_can_bang(s)}")KẾT QUẢ
'tong(gia[0], {2: 3})' True
'())(' False
'((' False
'([)]' False
'' TrueĐổi "([)]" thành "([])" rồi chạy lại: dòng thứ tư in True.
Hàm có ba chỗ trả False, mỗi chỗ một kiểu hỏng: đóng khi chưa có gì mở, đóng sai loại, và hết chuỗi mà vẫn còn dấu mở. c in DONG_MO hỏi khóa của dict, tức ba dấu đóng. Vế len(ngan_xep) == 0 đứng trước or, nên khi ngăn xếp rỗng Python dừng ở vế đó và không gọi pop(). Mỗi ký tự được xét một lần, và append(), pop() ở cuối list là O(1), nên số bước tăng cùng nhịp với độ dài chuỗi.
Dòng return cuối cùng của cách 2 cũng là một quyết định, không chỉ là chỗ kết thúc hàm.
Nói gì với người phỏng vấn
Hỏi trước các câu của mục Đề bài: có mấy loại ngoặc, ký tự khác có bỏ qua không, dấu ngoặc trong nháy có tính không. Rồi trình bày:
"Nếu chỉ có một loại ngoặc, một biến đếm là đủ. Có nhiều loại thì đếm sai với
"([)]", vì số đếm không nhớ thứ tự.""Tôi dùng list làm ngăn xếp: dấu mở thì
append(), dấu đóng thìpop()đỉnh ra và so với dấu mở khớp trong một dict.""Mỗi ký tự xét một lần, nên thời gian là O(n). Bộ nhớ tối đa O(n) khi mọi ký tự là dấu mở."
"Tôi đã xét chuỗi rỗng, dấu đóng khi chưa có gì mở, đóng sai loại, và hết chuỗi mà còn dấu mở."
Kiểm tra nhanh
Cách 2 đọc chuỗi
"{[(])}"từ trái sang. Lúc gặp dấu], dấu mở ở đỉnh ngăn xếp là dấu ____.Trong cách 2, vì sao vế
len(ngan_xep) == 0phải đứng trướcngan_xep.pop()trong câuif?- Để dấu mở chưa đóng được báo ở cuối hàm
- Để Python không gọi
pop()trên list rỗng khi chuỗi có dấu đóng thừa - Để
pop()lấy phần tử đầu list thay cho phần tử cuối
Những chuỗi nào hàm
ngoac_can_bangcủa cách 2 trả vềFalse?")(""""((""{(})"
Bài tập
Tìm chỗ sai đầu tiên của dấu ngoặc
Trình soạn thảo muốn tô đỏ đúng chỗ sai. Viết hàm vi_tri_loi(s) đọc s từ trái sang với một ngăn xếp (list, append() và pop()) và trả về:
chỉ số của dấu đóng đầu tiên không ghép được: ngăn xếp rỗng, hoặc đỉnh là dấu mở khác loại,
nếu đọc hết mà còn dấu mở chưa đóng, chỉ số của dấu mở chưa đóng đứng sớm nhất,
-1khi mọi dấu ngoặc cân bằng.
Ký tự khác bỏ qua. Dict DONG_MO có sẵn trong starter.
Ví dụ: vi_tri_loi("tong(gia[0)]") trả về 10, chỉ số của dấu ).
Trả về: chỉ số, một int.
Ôn lại: ngăn xếp.
DONG_MO = {")": "(", "]": "[", "}": "{"}
def vi_tri_loi(s):
pass # Viết thân hàm thay cho dòng nàyCâu hỏi thường gặp
Đề valid parentheses bằng Python thường khác bài này ở đâu?
Đề valid parentheses hay gặp chỉ cho chuỗi gồm toàn dấu ngoặc, không có ký tự khác, và hỏi True hay False. Lời giải vẫn là cách 2: hàm của trang chạy đúng trên đề đó, vì nhánh bỏ qua ký tự khác không bao giờ được dùng tới.
Kiểm tra balanced parentheses bằng replace() trong Python có được không?
Được với chuỗi chỉ có dấu ngoặc: lặp lại việc xóa các cặp "()", "[]", "{}" liền nhau cho tới khi không xóa được nữa, rồi xem chuỗi có rỗng không. Mỗi lượt xóa chép lại cả chuỗi, nên chuỗi lồng sâu tốn khoảng O(n²) bước, chậm hơn ngăn xếp. Phương thức replace() nằm ở bài replace.
Ngăn xếp trong Python nên dùng list hay deque?
List là đủ cho ngăn xếp, vì append() và pop() ở cuối list là O(1), như bài ngăn xếp đã giải thích. collections.deque cần khi bạn lấy phần tử ở đầu, tức hàng đợi, bài hàng đợi dạy kỹ.
Chủ đề
Bài này có hữu ích?
Hỏi đáp
Tham vấn chuyên môn
Nhà sáng lập AIDev và VietPlatform · Thạc sĩ AI MSE
- Tốt nghiệp thủ khoa xuất sắc Thạc sĩ AI MSE.
- Đồng sáng lập, CTO E-University, SVOnline: số hóa 10+ đại học, 40.000+ sinh viên.
- Xây hệ thống AI cho doanh nghiệp tại VietPlatform.