Decoding a regular expression with nested repetitions

PHP Hard regex

Task «Decoding a regular expression with nested repetitions»

Given a string containing an encoded regular expression in a special format: letters of the Latin alphabet (a-z) and digits (2-9) in parentheses, indicating the number of repetitions of the previous character or group. Nested parentheses are allowed. It is necessary to expand all repetitions and output the resulting regular expression in standard notation (without parentheses with a number, only characters and quantifiers {n}). For example, 'a3' becomes 'a{3}', '(ab)2' -> '(ab){2}', and '((a2)2b)2' -> '((a{2}){2}b){2}'. It is guaranteed that the input string is valid, the length does not exceed 1000 characters, and the nesting depth is no more than 10.

Input Format

The only string S (1 ≤ |S| ≤ 1000), consisting of lowercase Latin letters, digits 2-9, and parentheses.

Output Format

One line — an expanded regular expression in standard notation.

Examples

Example 1

INPUT

a3

OUTPUT

a{3}

Example 2

INPUT

0 0 4 0 0 3

OUTPUT

  {4}   {3}

Example 3

INPUT

0

OUTPUT

Example 4

INPUT

(ab)2

OUTPUT

(ab){2}

Example 5

INPUT

1 1 4 5 7 1

OUTPUT

  {4} {5} {7} 

main.php