Mô tả
Tổ công nghệ thông tin Viettel đang nâng cấp hệ thống ERP dùng để xuất hóa đơn lương cho hàng vạn cán bộ kỹ thuật đi triển khai trạm phát sóng khắp cả nước. Trong file cấu hình tiền lương, mỗi khoản phụ cấp được biểu diễn bằng một công thức dài ngoằn, ví dụ ((luong_co_ban + phu_cap_di_lai) * he_so_khu_vuc). Nếu chỉ cần thiếu hoặc dư một dấu ngoặc đơn, toàn bộ quy trình xuất lương sẽ báo lỗi vào lúc nửa đêm.
Nhiệm vụ của bạn là viết một bộ kiểm tra nhỏ: cho trước một chuỗi công thức chỉ chứa các ký tự chữ cái thường, dấu cộng +, dấu trừ -, dấu sao *, chữ x, dấu gạch dưới _ và dấu ngoặc đơn (, ). Hãy xác định xem các dấu ngoặc đơn trong chuỗi có hợp lệ hay không. Một chuỗi hợp lệ khi mỗi dấu ( mở ra đều có đúng một dấu ) đóng lại theo đúng thứ tự lồng nhau, và không có dấu ngoặc nào bị sót.
Đầu vào
Một chuỗi s duy nhất chứa công thức cần kiểm tra.
Đầu ra
In ra VALID nếu dấu ngoặc hợp lệ, ngược lại in ra INVALID.
Ràng buộc
- Độ dài chuỗi
snằm trong khoảng từ 1 đến 100000. - Chuỗi chỉ chứa các ký tự: chữ cái thường
atớiz, dấu+,-,*,x,_,(,).
Ví dụ
Ví dụ 1
- Đầu vào:
(luong_co_ban + phu_cap) * he_so - Đầu ra:
VALID - Giải thích: Một dấu
(mở ở đầu và một dấu)đóng ở giữa khớp hoàn toàn với nhau, phần còn lại không có dấu ngoặc nào khác.
** Ví dụ 2**
- Đầu vào:
((a + b) * (c - d) - Đầu ra:
INVALID - Giải thích: Có hai dấu
(mở nhưng chỉ có một dấu)đóng, nên một cặp chưa được đóng.