Mô tả
Tổ Công nghệ BHXH Việt Nam đang bảo trì hệ thống ERP dùng để tính phụ cấp tự động cho người lao động. Trong hệ thống này, bộ phận nhân sự nhập công thức tính phụ cấp dưới dạng biểu thức có nhiều lớp ngoặc lồng nhau. Ba loại ngoặc được phép dùng là ngoặc tròn (), ngoặc vuông [] và ngoặc nhọn {}.
Ví dụ một công thức hợp lệ: [luong_co_ban + {phu_cap_an * (so_ngay + 2)}]. Để máy tính hiểu đúng ý nghĩa thứ tự ưu tiên, mọi ngoặc mở phải có đúng một ngoặc đóng cùng loại ở phía sau, và không được phép giao nhau sai quy tắc.
Nhiệm vụ của bạn là viết một chương trình nhận vào một chuỗi công thức, kiểm tra xem chuỗi đó có tổ chức ngoặc hoàn toàn đúng quy tắc hay không. Quy tắc áp dụng như sau:
- Mỗi ngoặc mở phải được đóng bởi đúng loại ngoặc tương ứng.
- Ngoặc mở sau phải được đóng trước (nguyên tắc LIFO).
- Không được phép có ngoặc giao nhau, ví dụ
[(])là sai.
Lưu ý: Chuỗi công thức có thể chứa các chữ cái, chữ số và các ký tự toán học khác như +, -, *, /. Bạn chỉ cần quan tâm đến các ký tự ngoặc.
Đầu vào
Một chuỗi s duy nhất là công thức cần kiểm tra. Độ dài chuỗi từ 1 đến 10.000 ký tự.
Đầu ra
- Trả về
truenếu chuỗi có tổ chức ngoặc hoàn toàn hợp lệ. - Trả về
falsetrong mọi trường hợp còn lại (thiếu ngoặc đóng, thừa ngoặc đóng, sai loại ngoặc đóng, ngoặc giao nhau).
Ràng buộc
- 1 ≤ độ dài chuỗi
s≤ 10.000. - Chuỗi chỉ chứa các ký tự in được trong bảng mã ASCII (chữ cái, chữ số, ký tự hiệu, dấu ngoặc).
- Đảm bảo tổng số lượng các ký tự ngoặc trong chuỗi không vượt quá 10.000.
Ví dụ
Ví dụ 1:
Đầu vào:
[luong_co_ban + {phu_cap_an * (so_ngay + 2)}]
Đầu ra:
true
Giải thích: Ta duyệt qua chuỗi. Gặp [ ta đẩy vào ngăn xếp. Gặp { ta tiếp tục đẩy. Gặp ( ta đẩy tiếp. Gặp ) khớp với đỉnh ngăn xếp ( nên ta rút ( ra. Gặp } khớp với { nên rút { ra. Cuối cùng gặp ] khớp với [ nên rút [ ra. Kết thúc chuỗi, ngăn xếp trống, vậy công thức hợp lệ.
Ví dụ 2:
[(])
Đầu ra:
false
Giải thích: Gặp [ đẩy vào. Gặp ( đẩy vào. Gặp ] nhưng đỉnh ngăn xếp là ( không khớp, vậy công thức sai ngay lập tức.