Đăng ký
cpp-009Đọc toàn bộ đề miễn phí

Kiểm tra biểu thức dấu ngoặc hợp lệ

Bộ tiền xử lý cú pháp của trình biên dịch ngôn ngữ truy vấn AI tại AI Empire Academy cần kiểm tra xem một chuỗi biểu thức S chỉ gồm các ký tự mở ngoặc (, [, { và đóng ngoặc ), ], }…

C++Trung bình25 phút

Tiến độ của tôi ở bài này

Điểm được lưu vào tài khoản sau khi chấm bài.

Đang tải điểm của bạn…

Kiến thức và chủ đề

stackdata structuresstringsparsing

Kiến thức tiên quyết: std stack, std string, loops.

Nội dung đề bài

Mục tiêu kiến thức

  • Hiểu và vận dụng cấu trúc dữ liệu Ngăn xếp (std::stack) với cơ chế vào sau - ra trước (LIFO).
  • Xử lý các cặp dấu ngoặc đóng/mở tương ứng với 3 loại: tròn (), vuông [], và nhọn/xoắn {}.
  • Kiểm tra an toàn trước khi lấy phần tử đỉnh (empty() trước top() và pop()).
  • Phân tích độ phức tạp thời gian O(N) và không gian O(N).

Mô tả bài toán

Bộ tiền xử lý cú pháp của trình biên dịch ngôn ngữ truy vấn AI tại AI Empire Academy cần kiểm tra xem một chuỗi biểu thức S chỉ gồm các ký tự mở ngoặc (, [, { và đóng ngoặc ), ], } có hợp lệ hay không.

Một chuỗi dấu ngoặc được gọi là hợp lệ khi và chỉ khi:

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

Nếu chuỗi hợp lệ, in ra: HOP LE. Nếu chuỗi không hợp lệ, in ra: KHONG HOP LE.

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 dùng cout để in lời nhắc trước khi đọc dữ liệu. Lời nhắc sẽ lọt 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.

Input

Dòng đầu tiên chứa số nguyên T là số lượng bộ test (1 ≤ T ≤ 50). T dòng tiếp theo, mỗi dòng chứa một chuỗi ký tự S chỉ gồm các ký tự ngoặc ()[]{} (0 ≤ |S| ≤ 105). Tổng độ dài các chuỗi trong tất cả các test không vượt quá 2 · 105.

Output

Gồm T dòng, mỗi dòng in kết quả HOP LE hoặc KHONG HOP LE cho bộ test tương ứng.

Ràng buộc

  • 1 ≤ T ≤ 50.
  • Tổng độ dài chuỗi ∑ |S| ≤ 2 · 105.
  • Thời gian chạy: 1000ms.
  • Bộ nhớ tối đa: 256MB.

Ví dụ 1

Input

3
{[()]}
{[(])}
(([])){}

Output

HOP LE
KHONG HOP LE
HOP LE

Giải thích

  • {[()]}: Các cặp ngoặc mở {, [, ( được đóng đúng thứ tự ), ], } → Hợp lệ.
  • {[(])}: Dấu [ mở trước nhưng lại đóng bằng ) trước khi đóng ] → Sai thứ tự lồng nhau.
3 cấp độ gợi ýMở dần khi bạn thật sự cần hỗ trợ.
Phân tích lời giảiGiải thích hướng tư duy và thuật toán.
Code tham khảoDùng để đối chiếu sau khi tự làm.

Gợi ý và lời giải chỉ mở sau khi bạn bấm Nộp bài. Giáo viên và quản trị viên mở được ngay.

Bài tập liên quan cùng chuyên đề

Ngăn xếp đơn điệu tìm phần tử lớn hơn đầu tiên bên phải
Trung bình30p
Cài đặt bộ nhớ đệm LRU Cache: Danh sách liên kết kép kết hợp Bảng băm
Trung bình35p
Hàng đợi ưu tiên duy trì Top K phần tử lớn nhất
Trung bình30p
Hình chữ nhật lớn nhất trong biểu đồ cột: Ngăn xếp đơn điệu O(N)
Nâng cao40p

Góp ý & báo lỗi bài tập

Đề bài chưa rõ, test có vấn đề hay bạn có ý tưởng giúp bài tốt hơn? Gửi cho đội ngũ AI Empire nhé — mỗi góp ý đều được đọc.