Đóng Gói Màn Hình Trực Sinh Tuổi Trẻ

Mô tả

Tòa soạn báo Tuổi Trẻ chuẩn bị đưa bài viết lên khuôn in. Trong bản nháp còn lẫn nhiều ngoặc đơn ( ) do phóng viên chú thích thêm. Trước khi in, biên tập viên phải chắc chắn rằng mỗi ngoặc mở đều có đúng một ngoặc đóng tương ứng phía sau, và không xuất hiện ngoặc đóng thừa. Nhiệm vụ của bạn là viết chương trình nhận vào một chuỗi văn bản và cho biết chuỗi ngoặc đơn bên trong có hợp lệ hay không.

Một chuỗi được coi là hợp lệ khi thoả cả hai điều kiện sau:

• Số lượng ngoặc mở bằng số lượng ngoặc đóng.
• Xét từ trái sang phải, tại mọi vị trí, số ngoặc mở đã gặp luôn lớn hơn hoặc bằng số ngoặc đóng đã gặp.

Đầu vào

• Một chuỗi s gồm các ký tự bảng chữ cái, dấu câu, khoảng trắng và ngoặc đơn (, ).

Đầu ra

• In ra VALID nếu chuỗi ngoặc hợp lệ, ngược lại in ra INVALID.

Ràng buộc

• Độ dài chuỗi s nằm trong khoảng từ 0 đến 10^5 ký tự.

Ví dụ

Ví dụ 1

• Đầu vào: (Bai viet) (moi)
• Đầu ra: VALID
• Giải thích: Có hai ngoặc mở và hai ngoặc đóng, thứ tự đúng: ngoặc mở đầu khớp với ngoặc đóng số 1, cặp thứ hai khớp tương tự.

Ví dụ 2

• Đầu vào: (An ninh)) (Giao thong)
• Đầu ra: INVALID
• Giải thích: Sau khi khớp cặp đầu tiên, ngoặc đóng thứ hai xuất hiện khi không còn ngoặc mở nào đang chờ, nên không hợp lệ.