栈----3.字符串解码

394. 字符串解码 - 力扣（LeetCode）

/**

        k[encoded_string] ---> k个连续的s; encoded_string = k[encoded_string](可嵌套)

        解码规则:

                1.将所有字符压入栈中,直到遇到']' ---> 当前层级的encoded_string读取完毕,开始转换

                2.弹出栈,将弹出的元素拼接,直到遇到'[' ---> 当前层级的encoded_string转化完毕

                3.继续弹出直到栈顶元素不为数字,k读取完毕,重复拼接k次重新入栈 ---> 当前k[encoded_string]转码完毕

                4.继续读取字符串,重复上述流程直到转换完毕为止

*/

class Solution {
    /**
        k[encoded_string] ---> k个连续的s; encoded_string = k[encoded_string](可嵌套)
        解码规则:
                1.将所有字符压入栈中,直到遇到']' ---> 当前层级的encoded_string读取完毕,开始转换
                2.弹出栈,将弹出的元素拼接,直到遇到'[' ---> 当前层级的encoded_string转化完毕
                3.继续弹出直到栈顶元素不为数字,k读取完毕,重复拼接k次重新入栈 ---> 当前k[encoded_string]转码完毕
                4.继续读取字符串,重复上述流程直到转换完毕为止
    */
    public String decodeString(String s) {
        //利用栈进行解码
        Deque<String> stack = new ArrayDeque<>();

        //开始解码
        for(char c : s.toCharArray()) {
            //不为']',将字符入栈
            if(c != ']') {
                 stack.push(String.valueOf(c));
            } 
            
            //遇到']',当前层级的encoded_string读取完毕,开始转换
            else {
                //临时保存拼接后的元素
                StringBuilder tempStr = new StringBuilder();

                //将元素弹出栈并拼接,直到遇到'['
                while(!stack.peek().equals("[")) { //代表当前层级的encoded_string转化完毕
                    //弹出元素并进行拼接(新元素拼接到首位)
                    tempStr.insert(0,stack.pop());
                }
                stack.pop(); //弹出'['
                
                //继续弹出元素,直到不为数字 ---> 读取K
                StringBuilder repeatCount = new StringBuilder();
                while(!stack.isEmpty() && Character.isDigit(stack.peek().charAt(0))) { //采用peek,避免弹出不该弹出的元素
                    repeatCount.insert(0,stack.pop());
                }
                
                //得出K,开始重复拼接K次
                int k =  Integer.parseInt(repeatCount.toString());
                StringBuilder repeated = new StringBuilder();
                for(int i = 0; i < k; i++) {
                    repeated.insert(0,tempStr);
                }

                //拼接完毕,重新入栈
                stack.push(repeated.toString());
            }
        }

        //解码完毕,拼接最后结果
        StringBuilder result = new StringBuilder();
        while (!stack.isEmpty()) {
            result.insert(0, stack.pop()); //注意顺序
        }
        return result.toString();
    }
}