Kiểm định cấu trúc ngoặc của biểu thức

Bối cảnh và bài toán

Một bộ phân tích cú pháp nhận chuỗi chỉ gồm bốn ký hiệu (, ), [ và ]. Một chuỗi được xem là hợp lệ nếu mọi dấu đóng ghép đúng với dấu mở gần nhất chưa được ghép và toàn bộ dấu mở đều được đóng.

Yêu cầu

Xác định chuỗi đầu vào có hợp lệ hay không.

Input

• Một dòng chứa chuỗi s; dòng có thể rỗng.

Output

In YES nếu chuỗi hợp lệ, ngược lại in NO.

Ràng buộc

• 0 <= |s| <= 2 * 10^5
• s[i] thuộc tập { (, ), [, ] }

Chấm điểm

Ví dụ 1

Input

([()[]])

Output

YES

Giải thích. Mỗi dấu đóng khớp đúng loại với dấu mở gần nhất chưa đóng.

Ví dụ 2

Input

([)]

Output

NO

Giải thích. Dấu ) gặp khi dấu mở gần nhất là [, nên cấu trúc sai ngay tại vị trí đó.

Thông tin bài tập

Nguồn: Phỏng theo UVa Online Judge 673 – Parentheses Balance.

Tham khảo: https://onlinejudge.org/external/6/673.pdf