Задача. Упростить относительный путь
Задача. Дан строковый путь, который представляет собой абсолютный путь (начинается с символа '/') к файлу или папке в файловой системе в стиле Unix. Необходимо упростить этот путь.
Справка
В файловой системе в стиле Unix точка '.' относится к текущему каталогу, двойная точка «..» относится к папке более высокого уровня, а любые несколько последовательных косых черт обрабатываются как одиночная косая черта «/». Любые другие форматы точек, такие как «...», рассматриваются как имена файлов или папок.
Упрощенный путь должен иметь следующий формат:
- Путь начинается с косой черты '/'.
- Любые две папке разделяются одинарной косой чертой '/'.
- Путь не заканчивается символом '/'.
- Путь содержит только папки на пути от корневой папки к целевому файлу или папки (т.е. без точки '.' или двойной точки '..')
Входные данные: path - строка, которая содержит только символы английского алфавита, символы '.', '/'. Размер строки от 1 до 3 тыс.символов.
Вывод: упрощенный путь исходной строки.
1. path = "/home/"
Output: "/home"
3. path = "/a/./b/../../c/"
Output: "/c"
Разбор
Воспользуемся стеком для реализации нашего алгоритма.
- Для начала нам нужно разделить исходную строку на состовляющие, которые разделены обратным слэшом.
- Далее начинаем обрабатывать получившийся массив блоков.
- Если текущий блок - это '.'' или пустая строка, пропускаем.
- Если текущий блок - это '..', то это значит, что нам нужно подняться на 1 уровень вверх по текущему пути. То есть необходимо удалить последний блок из нашего стека, если он не пустой.
- В противном случае, мы встретили имя каталога и просто добавляем его в наш стек. - После обработки всех блоков нам останется только соединить все имена папок из нашего стека обратным слэшом и вывести результирующую строку. Это и будет упрощенный относительный путь от исходного.
Детали реализации смотрите ниже.