题目：给定一个经过编码的字符串，返回它解码后的字符串。
编码规则为: k[encoded_string]，表示其中方括号内部的 encoded_string 正好重复 k 次。注意 k 保证为正整数。
你可以认为输入字符串总是有效的；输入字符串中没有额外的空格，且输入的方括号总是符合格式要求的。
此外，你可以认为原始数据不包含数字，所有的数字只表示重复的次数 k ，例如不会出现像 3a 或 2[4] 的输入。
解题思路：我们可以把字母、数字和括号看成是独立的TOKEN，并用栈来维护这些TOKEN。具体做法是，遍历这个栈：
如果当前的字符为数位，解析出一个数字（连续的多个数位）并进栈
如果当前的字符为字母或者左括号，直接进栈
如果当前的字符为右括号，开始出栈，一直到左括号出栈，出栈序列反转后拼接成一个字符串，此时取出栈顶的数字（此时栈顶一定是数字，想想为什么？），就是这个字符串应该出现的次数，我们根据这个次数和字符串构造出新的字符串并进栈
class Solution { int ptr; public String decodeString(String s) { LinkedList<String> stk = new LinkedList<String>(); ptr = 0; while (ptr < s.length()) { char cur = s.charAt(ptr); if (Character.isDigit(cur)) { // 获取一个数字并进栈 String digits = getDigits(s); stk.addLast(digits); } else if (Character.isLetter(cur) || cur == '[') { // 获取一个字母并进栈 stk.addLast(String.valueOf(s.charAt(ptr++))); } else { ++ptr; LinkedList<String> sub = new LinkedList<String>(); while (!"[".equals(stk.peekLast())) { sub.addLast(stk.removeLast()); } Collections.reverse(sub); // 左括号出栈 stk.removeLast(); // 此时栈顶为当前 sub 对应的字符串应该出现的次数 int repTime = Integer.parseInt(stk.removeLast()); StringBuffer t = new StringBuffer(); String o = getString(sub); // 构造字符串 while (repTime-- > 0) { t.append(o); } // 将构造好的字符串入栈 stk.addLast(t.toString()); } } return getString(stk); } public String getDigits(String s) { StringBuffer ret = new StringBuffer(); while (Character.isDigit(s.charAt(ptr))) { ret.append(s.charAt(ptr++)); } return ret.toString(); } public String getString(LinkedList<String> v) { StringBuffer ret = new StringBuffer(); for (String s : v) { ret.append(s); } return ret.toString(); } }
