Задача. Расшифровывать строку
Задача: Дана закодированная строка, необходимо вернить ее декодированную строку.
Правило кодирования: k [закодированная_строка], где закодированная_строка в квадратных скобках повторяется ровно k раз. k - строго положительное число.
Входные данные: входная строка валидна: нет лишних пробелов, правильные квадратные скобки. Также, полностью раскодированная строка не содержит цифр.
Разбор
Итак, у нас есть строка в форме K [шаблон], необходимо декодировать ее. Например, 2[abc] -> abcabc.
Сложность задачи заключается в том, что необходимо также учесть вложенные шаблоны. Например, 3[a2[b]] -> abbabbabb. То есть мы должны декодировать сначала самый внутрениий шаблон и дальше продолжать, пока мы не декодируем всю строку.
Мы знаем, что входная строка валидна и содержит только буквы английского алфавита, цифры и квадратные скобки. Шаблон всегда начинается с некоторого числа K, за ним следуют квадратные скобки, внутри находится строка или другой вложенный шаблон, например, K[строкаK[строка]].
Так как нам нужно начать декодирование с самого внутреннего шаблона, то мы должны дойти в строке до 1го вхождения закрывающейся квадратной скобки и начать процесс декодирования. Для этих целей мы можем воспользоваться стеком.
Алгоритм
- Записываем символ, если он не равен ']'
- В противном случае, начинаем процесс декодирования:
- Вверху стека находится внутренний шаблон. Извлекаем его, пока не встретим символ '['.
- Убираем символ '[' из стека.
- Дальше извлекаем число K и преобразуем его в численный тип.
- ВАЖНО: теперь мы получили текуший шаблон и число K. Теперь нужно добавить K раз этот шаблон обратно в стек и перейти к след.итерации. - После прохождения всей входной строки в стеке мы получим необходимый результат. Его нужно извлечь в обратном порядке и преобразовать в результирующую строку.
Детали реализации смотрите ниже!