Mô tả
Tại trung tâm điều độ của EVN Cần Thơ, hệ thống tính tiền điện tự động mỗi tháng tải về hàng nghìn hóa đơn ghi rõ công thức phụ phí. Mỗi công thức là một chuỗi chứa nhiều loại dấu ngoặc để nhóm các khoản: dấu ngoặc tròn () cho phụ phí biến đổi, dấu ngoặc vuông [] cho phụ phí cố định, và dấu ngoặc nhọn {} cho tổng nhóm phụ phí đặc biệt.
Ví dụ một công thức hợp lệ: ([vuong] {tron}). Trái lại, ([)] là sai vì dấu ngoặc vuông mở trước phải đóng sau cùng ở cùng tầng, nhưng dấu ngoặc tròn lại đóng chen ngang vào giữa.
Nhiệm vụ của bạn: cho một chuỗi công thức, hãy xác định xem toàn bộ dấu ngoặc trong chuỗi có khớp nhau hoàn toàn hay không. Các ký tự khác (chữ cái, chữ số, dấu chấm phẩy...) bạn cứ bỏ qua, chỉ quan tâm tới sáu ký tự (, ), [, ], {, }.
Một chuỗi được gọi là hợp lệ khi:
- Mỗi dấu mở đều có đúng một dấu đóng cùng loại đi kèm.
- Các cặp đóng-mở không được cắt chéo nhau.
- Không có dấu đóng thừa hay dấu mở thiếu.
Đầu vào
- Một tham số
slà chuỗi biểu thức (kiểu chuỗi).
Đầu ra
- Trả về
Truenếu dấu ngoặc hợp lệ, ngược lại trả vềFalse(kiểu luận lý).
Ràng buộc
- Độ dài chuỗi
s:1 ≤ |s| ≤ 10^5. - Chuỗi chỉ chứa các ký tự ASCII có thể in được (từ mã 32 đến 126).
Ví dụ
Ví dụ 1
- Đầu vào:
"([vuong] {tron})" - Đầu ra:
True - Giải thích: Lần lượt mở
(rồi mở[, đóng]khớp vuông, tiếp theo mở{rồi đóng}khớp nhọn, cuối cùng đóng)khớp tròn. Không có dấu nào cắt chéo.
Ví dụ 2
- Đầu vào:
"([)]" - Đầu ra:
False - Giải thích: Mở
(rồi mở[, nhưng tiếp theo lại là)đóng tròn trong khi dấu mở gần nhất là[. Cắt chéo nên không hợp lệ.
Ví dụ 3
- Đầu vào:
"phu_phi_5000_dong" - Đầu ra:
True - Giải thích: Không có dấu ngoặc nào, xem như hợp lệ.