Условие:

• Написать на Java программу распаковывания строки. На вход поступает строка вида число[строка], на выход — строка, содержащая повторяющиеся подстроки.
• Проверить входную строку на валидность.

Ограничения:

• одно повторение может содержать другое. Например: 2[3[x]y] = xxxyxxxy
• допустимые символы на вход: латинские буквы, числа и скобки [ ]
• числа означают только число повторений
• скобки только для обозначения повторяющихся подстрок
• входная строка всегда валидна.

Пример:

Вход: 3[xyz]4[xy]z
Выход: xyzxyzxyzxyxyxyxyz

Решение:

Напишем два метода: метод isValid для проверки входной строки на валидность и метод getString для преобразования строки.

Метод isValid

Идея: проверить каждый символ на соответствие с предыдущим символом строки, проверить соответствие количества входных, выходных скобок и чисел, проверить на наличие символов в скобках и проверить на недопустимые символы.

Заведем две переменные типа boolean и три переменные типа int:

• digit - для проверки символа на число,
• waitingForSymbol - для проверки наличия символа между скобками,
• openBrackets - для подсчета количества открывающих скобок,
• closeBrackets - для подсчета количества закрывающих скобок,
• numbers - для подсчета количества цифр.
  Пройдем циклом по каждому символу строки. Можно выделить 5 случаев символов строки:

1. Число
   • Если прошлый символ НЕ число -> numbers += 1
   • символ - число (digit = true)
2. Скобка [
   • Если прошлый символ НЕ число -> Строка некорректна
   • символ — НЕ число (digit = false)
   • ожидаем символ (waitingForSymbol = true)
   • openBrackets += 1
3. Скобка ]
   • Если прошлый символ число ИЛИ ожидаем символ -> Строка некорректна
   • символ — НЕ число (digit = false)
   • closeBrackets += 1
4. Буква
   • Если прошлый символ число -> Строка некорректна
   • Если ожидаем символ -> НЕ ожидаем символ (waitingForSymbol = false)
   • символ = НЕ число (digit = false)
5. Остальное
   • Строка некорректна

После прохода по всем символам строки необходимо сделать финальные проверки:

• Если (openBrackets = closeBrackets) и (число скобок равно числу чисел) -> Строка корректна

Метод getString

Идея: обрезать строку, проверяя каждый символ, пока она не станет пустой. Если символ — буква, то добавить его в обработанную строку, если число, то считать его до скобок. Содержимое скобок рекурсивно обработать.

Можно выделить два случая символов строки:

1. Буква
   • добавить символ в результат
   • удалить первый символ строки
2. Цифра
   • Считать число до скобки, удаляя символы из строки
   • Удалить символ "["
   • Считать содержимое скобок в подстроку
   • Рекурсивно обработать подстроку
   • Добавить результат рекурсивной обработки "число" раз в результат

После обработки всех символов подпрограмма возвращает строку результат.