Hợp Lệ Dấu Ngoặc Thương Mại

Mô tả

Cô Lan mở một tiệm tạp hóa nhỏ giữa Sài Gòn. Mỗi sáng, cô nhận một chồng đơn đặt hàng từ các ứng dụng giao hàng được in trên những dải giấy dài. Trên mỗi dải giấy, ngoài thông tin sản phẩm, hệ thống còn in những ký hiệu đóng gói bằng dấu ngoặc để đánh dấu khuyến mãi hoặc ghi chú, ví dụ như [KM-Coca], {ghi-chú}, (túi nilon). Đôi khi các ghi chú này nằm lồng nhau phức tạp.

Tuy nhiên, máy in của cô Lan đã cũ và đôi khi in lỗi, làm mất dấu đóng hoặc mở ngoặc. Một dải giấy chỉ được coi là hợp lệ khi mọi dấu ngoặc đều khớp đôi: dấu mở nào thì phải có dấu đóng cùng loại tương ứng, và thứ tự đóng phải ngược lại với thứ tự mở theo cấu trúc lồng nhau đúng quy tắc. Cô Lan nhờ bạn viết một chương trình nhỏ để tự động lọc ra những đơn hàng in lỗi.

Các dấu ngoặc cần kiểm tra bao gồm: ngoặc đơn (), ngoặc vuông [] và ngoặc nhọn {}. Những ký tự khác (nếu có) chỉ là thông tin sản phẩm, bạn cứ bỏ qua, chỉ quan tâm đến ba loại dấu ngoặc trên.

Đầu vào

• Dòng duy nhất chứa một chuỗi s (chiều dài từ 0 đến 1000 ký tự) là nội dung được in trên dải giấy đơn hàng.

Đầu ra

• In ra 1 nếu chuỗi dấu ngoặc hợp lệ.
• In ra 0 nếu chuỗi dấu ngoặc không hợp lệ.

Ràng buộc

• 0 ≤ độ dài s ≤ 1000.
• Chuỗi s chỉ chứa các ký tự ASCII in được (chữ cái, chữ số, dấu câu, dấu ngoặc, khoảng trắng).

Ví dụ

Ví dụ 1:

• Đầu vào:

  KM1{dung-roi}

• Đầu ra:

  1

• Giải thích: Mở ngoặc vuông rồi đóng vuông, mở đơn rồi đóng đơn, mở nhọn rồi đóng nhọn. Tất cả khớp đúng.

Ví dụ 2:

• Đầu vào:

  (x[]{y})