Задачи
December 10, 2021

Задача. Упростить относительный путь

Задача. Дан строковый путь, который представляет собой абсолютный путь (начинается с символа '/') к файлу или папке в файловой системе в стиле Unix. Необходимо упростить этот путь.

Справка
В файловой системе в стиле Unix точка '.' относится к текущему каталогу, двойная точка «..» относится к папке более высокого уровня, а любые несколько последовательных косых черт обрабатываются как одиночная косая черта «/». Любые другие форматы точек, такие как «...», рассматриваются как имена файлов или папок.

Упрощенный путь должен иметь следующий формат:

  • Путь начинается с косой черты '/'.
  • Любые две папке разделяются одинарной косой чертой '/'.
  • Путь не заканчивается символом '/'.
  • Путь содержит только папки на пути от корневой папки к целевому файлу или папки (т.е. без точки '.' или двойной точки '..')

Входные данные: path - строка, которая содержит только символы английского алфавита, символы '.', '/'. Размер строки от 1 до 3 тыс.символов.

Вывод: упрощенный путь исходной строки.

Примеры:

1. path = "/home/"
Output: "/home"

2. path = "/../"
Output: "/"

3. path = "/a/./b/../../c/"
Output: "/c"

Разбор

Воспользуемся стеком для реализации нашего алгоритма.

Алгоритм

  1. Для начала нам нужно разделить исходную строку на состовляющие, которые разделены обратным слэшом.
  2. Далее начинаем обрабатывать получившийся массив блоков.
    - Если текущий блок - это '.'' или пустая строка, пропускаем.
    - Если текущий блок - это '..', то это значит, что нам нужно подняться на 1 уровень вверх по текущему пути. То есть необходимо удалить последний блок из нашего стека, если он не пустой.
    - В противном случае, мы встретили имя каталога и просто добавляем его в наш стек.
  3. После обработки всех блоков нам останется только соединить все имена папок из нашего стека обратным слэшом и вывести результирующую строку. Это и будет упрощенный относительный путь от исходного.

Детали реализации смотрите ниже.

Реализация

Протестировать код можно тут

https://dotnetfiddle.net/ZyeDxb