Нормалізувати рядок зі шляхом

Задача

У текстовому рядку вказано шлях до файлу чи директорії. В ньому можуть також зустрічатися дві крапки що позначають директорію на один рівень вгору. Треба прибати усі комбінації з двох крапок так щоб “/dir1/dir3” та “/dir1/dir2/../dir3/” стали ідентичними.

Рішення

Маабуть найпростішим буде рішення з вказівниками для читання та запису. Пересуваємо вказівник для читання доки не знайдемо послідовність “/../”. Далі пересуваємося від знайденої послідовності назад до першого попереднього символу “/” – це буде вказівник для запису.

Потім копіюємо рядок починаючи з позиції (вказвіник для читання + 3) у позицію (вказівник для запису). Після копіювання читання треба продовжити з тієї позиції в яку почали записувати (на випадок якщо у рядку є послідовності з більше ніж двох “..” послідовно).

int remove_double_dots(char *s) { for (char *r = s; *r;) { if (r[0] == '/' && r[1] == '.' && r[2] == '.' && (r[3] == '/' || r[3] == '')) { char *w = r - 1; for (; w >= s && *w != '/'; --w); if (w < s) return -1; char *p = w; r += 3; while (*w++ = *r++); r = p; } else { ++r; } } return 0; }

У такого рішення є недолік – частини рядку постійно копіюються і при великій кількості “..” цей алгоритм буде неефективним.

Для покращення ми можемо зробити наступне. Кожного разу коли знаходимо у рядку символ “/” за яким йде звичайна директорія додаємо адресу цієї піддиректорії у спеціальний масив. Коли ж знаходимо послідовність “/../” то вилучаємо з масиву останній елемент і пропускаємо знайдену послідовність. Таким чином ми знаходимо адреси усих піддиректорій за один прохід.

Далі треба послідовно скопіювати усі піддиректорії з масиву у результуючий рядок.

int remove_double_dots_with_stack(char *s) { size_t slashes = 0; for (char *p = s; *p; ++p) { if (*p == '/') ++slashes; } if (slashes == 0) return 0; std::vector<char*> words(slashes + 1); size_t word = 0; for (char *p = s; *p; ) { if (*p == '/') { if (p[1] == '.' && p[2] == '.' && (p[3] == '/' || p[3] == '')) { if (word > 0) { --word; p += 3; } else { return -1; } } else { words[word++] = ++p; } } else { ++p; } } char *w = s; for (size_t i = 0; i < word; ++i) { *w++ = '/'; for (char *p = words[i]; *p && *p != '/'; ++p) { *w++ = *p; } } *w = ''; return 0; }

Залишити відповідь

Зайти з допомогою: