Bỏ qua đến nội dung chính
Mục lục

Kiểm tra dấu ngoặc cân bằng bằng Python (valid parentheses)

AIDev Team · duyệt: Nguyễn Việt Chung

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

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:

python
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
([)]                  True

Dict 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:

python
s = "([)]"
for mo, dong in ["()", "[]", "{}"]:
    print(mo + dong, s.count(mo), s.count(dong))

KẾT QUẢ

() 1 1
[] 1 1
{} 0 0

Chỗ 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:

python
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

  1. 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 ____.

  2. Trong cách 2, vì sao vế len(ngan_xep) == 0 phải đứng trước ngan_xep.pop() trong câu if?

    • Để 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
  3. Những chuỗi nào hàm ngoac_can_bang của cách 2 trả về False?

    • ")("
    • ""
    • "(("
    • "{(})"
Đúng hết lần đầu +15 XP

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,

  • -1 khi 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.

python
DONG_MO = {")": "(", "]": "[", "}": "{"}

def vi_tri_loi(s):
    pass  # Viết thân hàm thay cho dòng này

Câ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ủ đề

kiểm tra dấu ngoặc cân bằng python

Bài này có hữu ích?

Hỏi đáp

Đang tải câu hỏi…

Tham vấn chuyên môn

Nguyễn Việt Chung

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.
Biên soạn: AIDev Team · Rà soát · Quy trình biên tập