Decode String

Расшифруйте строку так, как сделали бы это на бумаге. Найдите группу, внутри которой нет других групп, разверните её копии на месте и проверьте снова. В 2[x3[yz]] в группе 3[yz] внутри ничего нет, поэтому строка становится такой: 2[xyzyzyz], а ещё одно раскрытие даст ответ.

Первая ] в строке всегда закрывает такую группу. До неё никакая другая группа не закрылась, поэтому между ней и её [ не может быть скобок. Эта [ — ближайшая слева от неё, а счётчик — это последовательность цифр непосредственно перед ней. Замените счётчик, скобки и содержимое группы на содержимое, записанное k раз, и повторяйте, пока в строке не останется ни одной ].

Это верно, но при каждом раскрытии заново строится вся строка. При b группах и строке, длина которой растёт примерно до m символов, это до b × m копирований символов. Скрытый тест примерно с 1,300 группами подряд требует около 25 миллионов копирований, чтобы получить 27,688 символов, хотя для этого хватило бы одного прохода по входным данным.

Формат рекурсивный: закодированная строка — это последовательность букв и групп, а тело группы — это снова закодированная строка. Поэтому напиши одну функцию decode, которая читает данные с общей позиции, пока не встретит ], завершающую текущий уровень, или конец входных данных, и возвращает прочитанное в декодированном виде.

Когда decode встречает цифру, она считывает всё число, пропускает [ и вызывает себя, чтобы декодировать тело группы. Этот вызов останавливается на соответствующей ], потому что любые более глубокие ] уже были обработаны более глубоким вызовом. Вызывающая функция пропускает ], добавляет тело k раз и продолжает чтение. Для 2[x3[yz]] внешний вызов считывает 2; следующий вызов считывает x и 3; третий вызов возвращает yz; средний вызов возвращает xyzyzyz; внешний вызов записывает результат дважды.

Каждый символ входных данных считывается один раз. Основные затраты связаны с копированием: символ результата копируется по одному разу для каждой окружающей его группы, поэтому время работы составляет O(n + m·d) при глубине вложенности d. Рекурсия также достигает глубины в d вызовов. Для 100 уровней это нормально, но очень глубоко вложенные данные могут переполнить стек вызовов: например, Python по умолчанию останавливается на 1 000 вложенных вызовах.

Рекурсия хранит по одному незавершённому фрагменту текста для каждой открытой группы в кадрах вызовов. Вместо этого можно хранить эти фрагменты в собственном стеке и прочитать строку за один проход цикла.

Отслеживай две величины для текущего уровня: current — текст, декодированный на данный момент, и count — считываемое число. Цифра дополняет count по формуле count × 10 + digit, поэтому значения 10 и 300 обрабатываются правильно. Символ [ открывает уровень: помести current и count в стек, затем начни оба значения заново. Буква добавляется к current. Символ ] закрывает уровень: извлеки из стека сохранённые текст и число, а затем присвой current значение, состоящее из сохранённого текста, за которым следует count копий current.

Проследи за выполнением для 2[x3[yz]]. При первом символе [ ты помещаешь в стек (пустая строка, 2). Символ x задаёт значение x для current. При втором символе [ ты помещаешь в стек (x, 3), а yz записывается в новый current. Первый символ ] извлекает из стека (x, 3), поэтому значением current становится xyzyzyz. Последний символ ] извлекает из стека (пустая строка, 2), и значением current становится xyzyzyzxyzyzyz.

Группы закрываются в порядке, обратном порядку их открытия, поэтому вершина стека всегда соответствует уровню, к которому возвращает символ ]. Объём работы такой же, как у рекурсии, O(n + m·d), но при глубокой вложенности растёт только список, а не стек вызовов.