Kiểm tra biểu thức dấu ngoặc hợp lệ bằng Stack
Trình phân tích cú pháp (parser) của AI Empire Academy cần xác thực biểu thức chứa các dấu ngoặc do người dùng nhập vào.
Tiến độ của tôi ở bài này
Điểm được lưu vào tài khoản sau khi chấm bài.
Đang tải điểm của bạn…
Kiến thức và chủ đề
Kiến thức tiên quyết: stack operations, dictionaries.
Nội dung đề bài
Mục tiêu kiến thức
- Ứng dụng cấu trúc dữ liệu Ngăn xếp (Stack - LIFO) để kiểm tra tính cân bằng và đóng mở ngoặc.
- Kết hợp
dictánh xạ giữa dấu đóng và dấu mở tương ứng. - Xử lý các trường hợp biên: stack rỗng khi gặp dấu đóng, còn dư dấu mở khi hết chuỗi.
Mô tả bài toán
Trình phân tích cú pháp (parser) của AI Empire Academy cần xác thực biểu thức chứa các dấu ngoặc do người dùng nhập vào.
Chuỗi chỉ chứa các ký tự ngoặc sau: (, ), {, }, [, ]. Biểu thức được coi là hợp lệ nếu:
- Mỗi dấu mở ngoặc phải được đóng bằng dấu ngoặc cùng loại.
- Các dấu ngoặc phải được đóng theo đúng thứ tự mở trước đóng sau (LIFO).
- Mọi dấu đóng ngoặc đều phải có dấu mở ngoặc tương ứng xuất hiện trước nó.
Hãy viết hàm is_valid_parentheses(s: str) -> bool trả về True nếu chuỗi dấu ngoặc hợp lệ, ngược lại trả về False. Chuỗi rỗng được coi là hợp lệ.
Input
Chuỗi ký tự s (str).
Output
Trả về giá trị boolean True hoặc False.
Ràng buộc
- Độ dài 0 ≤ |s| ≤ 105.
- Ký tự chỉ gồm:
(,),{,},[,]. - Thời gian chạy tối đa: 1000ms.
- Giới hạn bộ nhớ: 256MB.
Ví dụ 1
Input
`s = "()[]{}"`Output
`True`Ví dụ 2
Input
`s = "(]"`Output
`False`Ví dụ 3
Input
`s = "([)]"`Output
`False`Gợi ý và lời giải chỉ mở sau khi bạn bấm Nộp bài. Giáo viên và quản trị viên mở được ngay.
Góp ý & báo lỗi bài tập
Đề bài chưa rõ, test có vấn đề hay bạn có ý tưởng giúp bài tốt hơn? Gửi cho đội ngũ AI Empire nhé — mỗi góp ý đều được đọc.