394. 字符串解码

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

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

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

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

示例 1：

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

输出："aaabcbc"

示例 2：

输入：s = "3[a2[c]]"

输出："accaccacc"

示例 3：

输入：s = "2[abc]3[cd]ef"

输出："abcabccdcdcdef"

示例 4：

输入：s = "abc3[cd]xyz"

输出："abccdcdcdxyz"

思路：因为可能会有这种类似的格式3[a2[c]]，所以我们可以先对最里面的进行解码3[acc]，最后在往外解码得到accaccacc。所以可以利用栈来解决，遍历字符串如果碰到数字，push进栈，碰到字母或者'['push进栈。在碰到']'时，进行pop操作弹出栈元素，直到碰到'['停止。因为弹出栈的顺序是逆序的，要进行一个反转。现在栈顶元素就是要循环的次数了，进行一个循环然后将结果压入栈中。

这里使用LinkedList来模拟栈，方便反转和最后的一个遍历。

class Solution {
		 int ptr;
    public String decodeString(String s) {
		LinkedList<String> stack = new LinkedList<>();
		ptr = 0;
		while (ptr < s.length()){
			char c = s.charAt(ptr);
			if(Character.isDigit(c)){
				// 获取一个数字并进栈
				String digit = getDigits(s);
				stack.addLast(digit);
			}else if(Character.isLetter(c) || c == '['){
				// 获取一个字母并进栈
				stack.addLast(String.valueOf(s.charAt(ptr++)));
			}else {
				++ptr;
				LinkedList<String> sub = new LinkedList<>();
				while (!"[".equals(stack.peekLast())){
					sub.addLast(stack.removeLast());
				}
				// 左括号出栈
				stack.removeLast();
				Collections.reverse(sub);
				// 此时栈顶为当前 sub 对应的字符串应该出现的次数
				int replTime = Integer.parseInt(stack.removeLast());
				StringBuffer o = new StringBuffer();
				String t = getString(sub);
				// 构造字符串
				while (replTime-- > 0){
					o.append(t);
				}
				// 将构造好的字符串入栈
				stack.addLast(o.toString());
			}
		}
		return getString(stack);
	}

	private String getString(LinkedList<String> sub) {
		StringBuffer stringBuffer = new StringBuffer();
		for(String s : sub){
			stringBuffer.append(s);
		}
		return stringBuffer.toString();
	}

	private String getDigits(String s) {
		StringBuffer buffer = new StringBuffer();
		while (Character.isDigit(s.charAt(ptr))){
			buffer.append(s.charAt(ptr++));
		}
		return buffer.toString();
	}
}