Задача «Расшифровка регулярного выражения с вложенными повторениями»

Дана строка, содержащая закодированное регулярное выражение в специальном формате: буквы латинского алфавита (a-z) и цифры (2-9) в круглых скобках, обозначающие количество повторений предыдущего символа или группы. Вложенные скобки разрешены. Необходимо раскрыть все повторения и вывести получившееся регулярное выражение в стандартной нотации (без скобок с числом, только символы и квантификаторы {n}). Например, 'a3' превращается в 'a{3}', '(ab)2' -> '(ab){2}', а '((a2)2b)2' -> '((a{2}){2}b){2}'. Гарантируется, что входная строка корректна, длина не превышает 1000 символов, глубина вложенности не более 10.

Пример 1

Пример 2

Пример 3

Пример 4

Пример 5