Problem H
Dekompression

Många metoder för att komprimera data bygger på att hitta återkommande mönster och representera dessa på ett mer effektivt sätt. Till exempel kan strängen $\mathtt{aaaaaaaaaaab}$ representeras kortare som $\mathtt{11ab}$, och strängen $\mathtt{ababababa}$ kan representeras som $\mathtt{4(ab)a}$. Som man kan förstå av dessa exempel antar vi att talet 11 i strängen $\mathtt{11ab}$ anger att nästa symbol $\mathtt{a}$ ska repeteras 11 gånger. Om vi vill att ett längre mönster ska upprepas används parenteser: Talet 4 i strängen $\mathtt{4(ab)a}$ anger att delsträngen $\mathtt{ab}$ ska upprepas 4 gånger.

Parenteser kan vara nästlade i ett godtyckligt antal nivåer. Till exempel kan strängen $\mathtt{bbbabababbbbababab}$ först komprimeras till $\mathtt{3b3(ab)3b3(ab)}$ och sedan ytterligare en gång till $\mathtt{2(3b3(ab))}$. I allmänhet är det ett mycket svårt problem att givet en sträng $s$ hitta den kortaste komprimerade representationen av $s$.

I denna uppgift ska vi lösa det (mycket lättare) omvända problemet, nämligen: Givet en komprimerad representation av en sträng $s$, återskapa $s$. Som en förenkling antar vi att alla okomprimerade strängar bara är uppbyggda av de två symbolerna $\mathtt{a}$ och $\mathtt{b}$, medan de komprimerade strängarna även kan innehålla siffror och parenteser som i exemplen ovan.

Indata

Indata består av en enda (komprimerad) sträng ur mängden $I$, definierad på följande sätt:

• $I$ innehåller strängarna $\mathtt{a}$, $\mathtt{b}$, samt alla strängar $n\mathtt{a}$ och $n\mathtt{b}$, där $n$ är ett tal mellan 1 och 99 (inklusivt).

• Om de två strängarna $s$ och $t$ tillhör $I$, så innehåller $I$ även den sammansatta strängen $st$.

• Om strängen $s$ tillhör $I$, så innehåller $I$ även alla strängar $n(s)$, där $n$ är ett tal mellan 1 och 99 (inklusivt).

• Inga andra strängar tillhör $I$.

Exempel på indatasträngar är $\mathtt{a}$, $\mathtt{11ab}$, $\mathtt{4(ab)a}$, $\mathtt{2(3b3(ab))}$.

Utdata

Utdata ska bestå av en enda sträng, som utgör den dekomprimerade versionen av indatasträngen.

11ab

aaaaaaaaaaab

4(ab)

abababab

2(3b3(ab))

bbbabababbbbababab