Bài 26.2. Chuẩn hóa Đường dẫn Hệ thống Tệp - [Độ khó: Khá]

Trong việc phát triển một tiện ích quản lý tệp đa nền tảng, bạn gặp phải vấn đề với các đường dẫn tệp do người dùng nhập vào. Các đường dẫn này thường chứa các ký tự thừa, ký hiệu đặc biệt không cần thiết, hoặc không theo một quy tắc nhất định. Nhiệm vụ của bạn là chuẩn hóa các đường dẫn này về một định dạng thống nhất, dễ đọc và xử lý.

Định dạng chuẩn hóa yêu cầu:

1. Loại bỏ các dấu / thừa (ví dụ: //, /./).
2. Xử lý ký hiệu . (thư mục hiện tại) và .. (thư mục cha):
   • /./ sẽ trở thành /.
   • /../ sẽ di chuyển lên một cấp thư mục. Nếu đã ở thư mục gốc (/), .. không có tác dụng.
3. Đường dẫn phải luôn bắt đầu bằng / nếu nó là đường dẫn tuyệt đối. Nếu sau khi chuẩn hóa, đường dẫn trở thành rỗng (ví dụ: . hoặc .. khi đã ở gốc), nó phải được biểu diễn là /.
4. Không có / ở cuối đường dẫn trừ khi đường dẫn đó là /.
5. Các ký tự phân cách phải là /, không phải \ (Windows style).
6. Giả sử các thành phần tên thư mục/tệp chỉ chứa các ký tự chữ cái, số, dấu gạch dưới (_), dấu gạch ngang (-), và dấu chấm (.).

INPUT FORMAT

Một chuỗi duy nhất là đường dẫn cần chuẩn hóa. Chuỗi có độ dài tối đa 1000 ký tự.

Ví dụ:

/usr/./local/../bin//scripts/./my_script.sh

OUTPUT FORMAT

Một chuỗi duy nhất là đường dẫn đã được chuẩn hóa.

Ví dụ:

Input:

/usr/./local/../bin//scripts/./my_script.sh

Output:

/usr/bin/scripts/my_script.sh

Giải thích:

• usr -> /usr
• ./ -> /usr/ (loại bỏ .)
• local -> /usr/local
• ../ -> quay về usr, vậy thành /usr
• bin// -> /usr/bin/ (loại bỏ / thừa)
• scripts -> /usr/bin/scripts
• ./ -> /usr/bin/scripts/ (loại bỏ .)
• my_script.sh -> /usr/bin/scripts/my_script.sh

Input (ví dụ khác):

../a/b/c

Output:

/a/b/c

Giải thích:

• Đường dẫn này không bắt đầu bằng /, nhưng theo quy ước, nếu nó là đường dẫn không tuyệt đối, sau khi xử lý .. ở đầu và không có thư mục gốc để quay về, nó sẽ được hiểu là một đường dẫn tuyệt đối bắt đầu từ gốc (ví dụ: cd ../a/b/c từ thư mục gốc / sẽ là /a/b/c). Để đơn giản, giả sử luôn bắt đầu bằng / sau khi chuẩn hóa nếu không có .. gây ra vấn đề, và không cần xử lý các trường hợp tương đối phức tạp. Hoặc, ta có thể đơn giản là xem xét nó trong ngữ cảnh Unix, nơi .. ở đầu đường dẫn không có ý nghĩa nếu không có thư mục cha. Để làm bài tập Khá đơn giản hơn, hãy giả định: Mọi đường dẫn đầu vào sẽ được xử lý như thể chúng bắt đầu từ thư mục gốc ảo (virtual root) nếu không bắt đầu bằng /. Kết quả chuẩn hóa cuối cùng luôn bắt đầu bằng /.
• .. : Không có thư mục cha, vẫn ở gốc ảo. Stack: []
• a: Push a. Stack: [a]
• b: Push b. Stack: [a, b]
• c: Push c. Stack: [a, b, c] Kết quả: /a/b/c

Input (ví dụ khác):

/.././

Output:

/

Giải thích:

• Bắt đầu với /.
• ..: Quay về thư mục cha, nhưng đã ở gốc. Stack: []
• .: Giữ nguyên. Stack: []
• Kết quả cuối cùng là /.