[Java] Decompress k[value] format strings

Here is an interesting problem: decompress a compressed string.

Your input is a compressed string of the format number[string] and the decompressed output form should be the string written number times. For example:

3[abc]4[ab]c

Would be output as

abcabcabcababababc

Number can have more than one digit. For example, 10[a] is allowed, and just means aaaaaaaaaa

One repetition can occur inside another. For example, 2[3[a]b] decompresses into aaabaaab

Characters allowed as input include digits, small English letters and brackets [ ].

Digits are only to represent amount of repetitions.

Letters are just letters.

Brackets are only part of syntax of writing repeated substring.

Input is always valid, so no need to check its validity.

This can be done in one pass of the string by either applying recursion or explicitly using a stack for an additional O(N) space and overall O(N) time.

Gotchas are:

• treat 0 repetitions and missing k correctly
• remember that when concatenating data that comes from the stack we are actually prepending
• run a last round of popping after the string is fully parsed

You can check the implementation of decompress on my Gist alongside some test cases in DecompressJTests.