【題目描述】
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
給出一個(gè)表達(dá)式?s，此表達(dá)式包括數(shù)字，字母以及方括號(hào)。在方括號(hào)前的數(shù)字表示方括號(hào)內(nèi)容的重復(fù)次數(shù)(括號(hào)內(nèi)的內(nèi)容可以是字符串或另一個(gè)表達(dá)式)，請(qǐng)將這個(gè)表達(dá)式展開成一個(gè)字符串。
樣例
S =?abc3[a]?返回?abcaaa
S =?3[abc]?返回?abcabcabc
S =?4[ac]dy?返回?acacacacdy
S =?3[2[ad]3[pf]]xyz?返回?adadpfpfpfadadpfpfpfadadpfpfpfxyz
【題目鏈接】
www.lintcode.com/en/problem/decode-string/
【題目解析】
遞歸的思路
遞歸計(jì)算出括號(hào)最里面的字符串，依次再處理外面一層的字符串，每個(gè)單元內(nèi)的字符串類似于一個(gè)結(jié)點(diǎn)，個(gè)數(shù)則為結(jié)點(diǎn)的個(gè)數(shù)。父結(jié)點(diǎn)則是將這些個(gè)數(shù)的字符串組合在一起，以此類推到跟結(jié)點(diǎn)，就是我們要求的結(jié)果。
迭代的思路
用兩個(gè)棧來(lái)分別保存下單元中的個(gè)數(shù)，另一個(gè)則保存單元中的字符串，注意的是，要將最新的處理完后的字符串加入到棧中。一直加入，直到最后返回棧頂字符串則為所求結(jié)果。
【參考答案】
