LeetCode Decode String Given an encoded string, return it’s decoded string. The encoding rule is: k[encoded_string], where the encoded_string inside the square brackets is being repeated exactly k times. Note that k is guaranteed to be a positive integer. You may assume that the input string is always valid; No extra white spaces, square brackets are well-formed, etc. Furthermore, you may assume that the original data does not contain any digits and that digits are only for those repeat numbers, k. For example, there won’t be input like 3a or 2[4]. Examples:

s = "3[a]2[bc]", return "aaabcbc".
s = "3[a2[c][/c]]", return "accaccacc".
s = "2[abc]3[cd]ef", return "abcabccdcdcdef".

---

题意：要求把加密的字符串解密。加密规则是重复k次的子串str写成k[str]，方括号可能会有嵌套。 所以我们需要解析加密字符串，把方括号中的内容提取出来，然后复制k份，因为有嵌套，面对括号匹配问题，堆栈是最好的解决办法。我们不断把字符串压栈，直到遇到]，从栈中不断弹出，直到遇到[，期间的字符串就是我们要重复的str，然后弹出k，重复k次，把重复的字符串再次压栈。如此不断循环，最后只要把栈中的字符串连接起来就好了。 完整代码如下： [cpp] class Solution { public: string decodeString(string s) { stack<string> stk; for (int i = 0; i < s.size(); ++i) { if (s[i] != ‘]’)stk.push(string(1, s[i])); else { string cur = ""; while (stk.top() != "[") { // stk不可能为空 cur = stk.top() + cur; stk.pop(); } stk.pop(); string cnt = ""; while (!stk.empty() && isdigit(stk.top()[0])) { // 此处stk可能为空 cnt = stk.top() + cnt; stk.pop(); } int n = atoi(cnt.c_str()); string repeated = ""; while (n–)repeated += cur; stk.push(repeated); } } string ans = ""; while (!stk.empty()) { ans = stk.top() + ans; stk.pop(); } return ans; } }; [/cpp] 本代码提交AC，用时3MS。]]>