Kiểm Tra Dấu Ngoặc Hợp Lệ Bằng Ngăn Xếp (Stack)

Mô tả bài toán

Trong các trình biên dịch và phân tích cú pháp biểu thức toán học, việc kiểm tra các cặp ngoặc đóng mở có ăn khớp và đúng thứ tự hay không là bài toán kinh điển ứng dụng cấu trúc dữ liệu Ngăn xếp (Stack).

Yêu cầu

Kiểm tra xem chuỗi ngoặc có hợp lệ hay không bằng cấu trúc dữ liệu Ngăn xếp (Stack):

• Mỗi dấu ngoặc mở phải được đóng bởi dấu ngoặc cùng loại.
• Các dấu ngoặc phải được đóng theo đúng thứ tự (LIFO - Vào sau ra trước).
• Chuỗi rỗng được coi là hợp lệ.

Quy ước nộp bài

• Chỉ cần viết một chương trình đọc stdin và in ra stdout. Bài này không yêu cầu viết hàm.
• Không truyền lời nhắc vào input(). Lời nhắc sẽ bị in vào stdout và làm bài sai.
• Chỉ in đúng nội dung ở mục Output. Không in thêm nhãn, dòng trống hay ký tự thừa.
• Output được so khớp từng ký tự, phân biệt chữ hoa/thường và dấu câu.

Ràng buộc

• Độ dài chuỗi S từ 0 đến 10⁵.
• Chuỗi chỉ chứa các ký tự trong tập ()[]{}.