Dãy ngoặc hợp lệ
Đề bài
Mô tả
Một dãy ngoặc được gọi là hợp lệ (regular bracket sequence — RBS) nếu có thể chèn thêm các ký tự + và 1 vào dãy để thu được một biểu thức số học đúng. Ví dụ, các dãy (())(), () và (()(())) là hợp lệ, còn )(, (() và (()))( thì không.
Cho một dãy gồm ký tự, mỗi ký tự là (, ), hoặc ?. Trong có đúng một ký tự ( và đúng một ký tự ).
Bạn phải thay thế mỗi ký tự ? bằng ( hoặc ) (các ? khác nhau có thể được thay khác nhau). Không được thay đổi thứ tự, không được xoá hay chèn ký tự khác, và bắt buộc phải thay mọi ?.
Hãy xác định xem có thể thu được một dãy ngoặc hợp lệ sau khi thay thế hay không.
Dữ liệu vào
- Dòng đầu chứa số nguyên () — số test.
- Mỗi test gồm một dòng chứa dãy (), gồm các ký tự
(,),?. Đảm bảo có đúng một(và đúng một).
Dữ liệu ra
Với mỗi test, in YES nếu có thể thu được dãy ngoặc hợp lệ, ngược lại in NO.
Ví dụ
| Input | Output | Giải thích |
|---|---|---|
| 5 () (?) (??) ??() )?(? |
YES NO YES YES NO |
Test 1: đã hợp lệ. Test 3: thay thành (()) hoặc ()(). Test 4: thay thành ()(). Test 2 độ dài lẻ nên không thể. Test 5: ký tự ) đứng đầu nên mọi cách thay đều bắt đầu bằng ). |
| 3 )??( ()?? ??)( |
NO YES NO |
Test 1: )??( luôn bắt đầu bằng ), không thể hợp lệ. Test 2: thay thành ()(). Test 3: ??)( — ) đứng trước (, mọi cách thay đều mất cân bằng tại vị trí của ). |
Bình luận