Chuẩn hóa lệnh có chuỗi trong ngoặc kép

Bối cảnh

Một công cụ dòng lệnh nhận một command dưới dạng một chuỗi. Ngoài ngoặc kép "...", mọi nhóm whitespace phải được nén thành một space và space đầu/cuối bị loại. Bên trong ngoặc kép, whitespace phải được giữ nguyên vì nó thuộc dữ liệu. Dấu " bên trong quote biểu diễn một dấu " literal và không kết thúc quote; ký tự \ biểu diễn một backslash literal. Ngoài quote, backslash không có ý nghĩa đặc biệt.

Nếu chuỗi kết thúc khi vẫn đang ở trong quote hoặc có escape dang dở bên trong quote, in INVALID. Nếu hợp lệ, in chuỗi đã normalize nhưng vẫn giữ cặp dấu quote và các escape như input. Ví dụ run "hello world" now trở thành run "hello world" now.

Bài Advanced yêu cầu thiết kế state machine với hai state chính inQuote và escape. Khó ở chỗ cùng một ký tự space có semantics khác tùy state, và dấu quote chỉ toggle state khi không bị escape. Đây là bài rất gần parser nhập môn nhưng vẫn chỉ dùng duyệt ký tự của B20, chưa cần tokenization/stringstream của B21.

Một cách tiếp cận tốt là tự vẽ state transition cho các ký tự ", \, whitespace và ký tự thường. Cùng một dấu " có thể là quote mở, quote đóng hoặc ký tự literal tùy inQuote/escape. Nếu code chỉ dùng nhiều if rời rạc mà không xác định state trước, rất dễ đóng quote nhầm hoặc nén whitespace trong dữ liệu được bảo vệ.

Yêu cầu

1. Đọc toàn bộ command line.
2. Nén whitespace chỉ ở ngoài quote.
3. Giữ nguyên nội dung/space trong quote.
4. Xử lý escape \" và \\ trong quote.
5. Quote/escape không đóng → INVALID.

Yêu cầu tổ chức code

Không dùng regex hoặc parser library.

Online Judge chấm output. Giảng viên có thể review source code để kiểm tra việc sử dụng đúng pointer/lifetime/string pipeline theo phạm vi buổi học.

Input

Một dòng command.

Output

INVALID hoặc command đã normalize.

Ràng buộc

|s|≤5000.

Ví dụ 1

Input

run   "hello   world"   now

Output

run "hello   world" now

Giải thích

Chuỗi bắt đầu ở state ngoài quote. Ba space sau run chỉ tạo một pending separator và được flush thành một space trước dấu ". Khi vào quote, chuỗi hello world được append nguyên trạng nên ba space bên trong vẫn còn. Quote đóng đưa parser về state ngoài; nhóm space trước now lại bị nén thành một. Kết quả cuối run "hello world" now.

Ví dụ 2

Input

cmd   a   b

Output

cmd a b

Giải thích

Input không chứa quote nên parser luôn ở state ngoài. Space đầu không được phát vì output đang rỗng; các nhóm space giữa cmd, a, b mỗi nhóm chỉ tạo một pending separator rồi flush thành một space khi gặp token kế tiếp. Space cuối không được flush khi input kết thúc. Vì vậy output canonical là cmd a b.

Thông tin học tập

• Module: M06
• Buổi: B20
• Loại bài: ADVANCED
• Độ khó: Hard
• Concepts: std::string, state machine, quoted segment, escape handling, whitespace normalization, validation
• Giới hạn kiến thức: B01-B20
• Time limit: 2 second(s)
• Memory limit: 256 MB
• Point: 100