字符串解码

字符串解码

给定一个经过编码的字符串，返回它解码后的字符串。

编码规则为: k[encoded_string]，表示其中方括号内部的 encoded_string 正好重复 k 次。注意 k 保证为正整数。

你可以认为输入字符串总是有效的；输入字符串中没有额外的空格，且输入的方括号总是符合格式要求的。

此外，你可以认为原始数据不包含数字，所有的数字只表示重复的次数 k ，例如不会出现像 3a 或 2[4] 的输入。

示例 1：

输入：s = "3[a]2[bc]"
输出："aaabcbc"

解题思路：

• 1 看到解码问题和'[‘, ‘]’这种符号就基本上需要使用栈来存储遍历过的信息。
• 2 由于数字和字符都需要进行存储，故需要使用两个栈，数字栈和字符栈。
• 3 输入：处理输入分为四种情况：数字、字符、左括号，右括号。
• 4 输入处理：
  • 4.1 数字：将字符处理成为int
  • 4.2 字符：将字符拼接为字符串
  • 4.3 左括号：将数字和字符分别存入数字栈和字符栈，同时继续开始遍历（数字置0，字符串置空）。
  • 4.4 右括号：将数字和字符取出进行字符串拼接。

class Solution {
public:
    string decodeString(string s) {
        // 四种情况，数字，字符，'['和']'
        string result = "";
        int num = 0;
        stack<int> nums;
        stack<string> strs;
        int m = s.size();
        for(int i=0; i<m; i++){
            if (s[i] >= '0' && s[i] <= '9')
                num = 10 * num + s[i] - '0';
            else if ((s[i] >= 'a' && s[i] <= 'z') || (s[i] > 'A' && s[i] < 'Z'))
                result += s[i];
            else if (s[i] == '['){
                nums.push(num); num=0;
                strs.push(result); result="";
            }
            else if (s[i] == ']'){
                int times = nums.top(); nums.pop();
                string inner_strs = strs.top(); strs.pop();
                for(int j=0; j<times; j++){
                    inner_strs += result;
                }
                result = inner_strs;
            }
        }
        return result;
    }
};