Expression Expand (Ladder)

Description

Given an expression s includes numbers, letters and brackets. Number represents the number of repetitions inside the brackets(can be a string or another expression)．Please expand expression to be a string.

Example
s = abc3[a] return abcaaa
s = 3[abc] return abcabcabc
s = 4[ac]dy, return acacacacdy
s = 3[2[ad]3[pf]]xyz, return adadpfpfpfadadpfpfpfadadpfpfpfxyz

Challenge: Can you do it without recursion? we are here

Assumption

1. "[]" buckets are right appearence
2. number/[]/char are perfect and no mistake
3. known data format

Link

Lintcode_ladder

Method

1. DFS/double pointers with Stack
2. backTracking with recursion

Example

1. 1

code

Similar problems

calculator, parse JSON

Tags

Divide and Conquer, Recursion, Stack, Non Recursion,
Yahoo