Xử lý chuỗi
Mô tả
Ban tổ chức hội thảo khoa học tại Đại học Quốc gia TP.HCM đang nhận được hàng nghìn email đăng ký dự thi. Một số email có kèm theo các đoạn mã hoặc ghi chú được bọc trong dấu ngoặc như (), [], {}. Ví dụ, email có thể chứa chuỗi kèm theo: [Thông báo] {Hội nghị (Khoa học) Máy tính}.
Để hệ thống tự động trích xuất thông tin không bị lỗi cú pháp, bạn được giao nhiệm vụ viết một chương trình kiểm tra xem phần chuỗi đính kèm đó có sử dụng dấu ngoặc hợp lệ hay không. Một chuỗi được coi là hợp lệ khi:
- Mỗi dấu mở ngoặc đều có đúng một dấu đóng ngoặc tương ứng cùng loại.
- Các cặp ngoặc không được cắt ngang lẫn nhau (ví dụ
([)]là không hợp lệ, nhưng()[]{}và({[]})thì hợp lệ). - Những ký tự không phải là dấu ngoặc (chữ cái, chữ số, dấu chấm, v.v.) sẽ bị bỏ qua trong quá trình kiểm tra.
Cho một chuỗi s là nội dung đính kèm trong email, hãy trả về true nếu chuỗi có thứ tự dấu ngoặc hợp lệ, ngược lại trả về false.
Đầu vào
- Một chuỗi
s(kiểu dữ liệu: chuỗi) bao gồm các chữ cái tiếng Anh, chữ số, dấu chấm, phẩy, khoảng trắng và các dấu ngoặc(),[],{}.
Đầu ra
- Trả về
true(kiểu boolean) nếu chuỗi dấu ngoặc hợp lệ, ngược lại trả vềfalse.
Ràng buộc
- Độ dài chuỗi
snằm trong khoảng từ0đến10^4. - Chuỗi rỗng được coi là chuỗi dấu ngoặc hợp lệ.
Ví dụ
Ví dụ 1:
- Đầu vào:
"[Đăng ký] {Hội thảo (CNTT) năm 2024}" - Đầu ra:
true - Giải thích: Các cặp ngoặc mở và đóng theo thứ tự
[]->{}->(). Cặp mở sau()được đóng trước tiên, cặp mở trước được đóng ở cuối. Ngoặc không bị cắt ngang, thứ tự hoàn toàn hợp lệ.