今天刷到了一题腾讯的算法真题，觉得比较有趣，所以在这里和大家分享一下。本题的链接是：压缩算法

题目

小Q想要给他的朋友发送一个神秘字符串，但是他发现字符串的过于长了，于是小Q发明了一种压缩算法对字符串中重复的部分进行了压缩，对于字符串中连续的m个相同字符串S将会压缩为[m|S](m为一个整数且1<=m<=100)，例如字符串ABCABCABC将会被压缩为[3|ABC]，现在小Q的同学收到了小Q发送过来的字符串，你能帮助他进行解压缩么？

输入

输入第一行包含一个字符串s，代表压缩后的字符串。
S的长度<=1000;
S仅包含大写字母、[、]、|;
解压后的字符串长度不超过100000;
压缩递归层数不超过10层;

输出

输出一个字符串，代表解压后的字符串。

输入例子

HG[3|B[2|CA]]F

输出例子

HGBCACABCACABCACAF

例子说明

HG[3|B[2|CA]]F−>HG[3|BCACA]F−>HGBCACABCACABCACAF

题目分析

这题是一个字符串操作类型的题目，问题的难点在于中括号的范围不确定，中括号也能放其他的中括号，所以我们要从最里面的中括号开始，一层一层剥开，举例说明：上面的例子[3|B[2|CA]]，我们很难将[3|*]直接展开，这样会导致有更多的中括号[B[2|CA]B[2|CA]B[2|CA]]，从而使问题更加复杂，就像例子说明1里面讲到的，要先从[2|CA]开始展开，这样才能使得中括号个数越来越少从而解决问题。

解题思路

思路是在遍历字符串的过程中，利用一个堆栈，存储"["和"|"的位置，当遇到"]"时，他必定与堆栈最上面的"["和"|"匹配，可以将他们出栈，然后用到"["和"]"中间的值去替换待返回的字符串

代码

public static void main(String args[]){
//        用户输入
        Scanner scanner = new Scanner(System.in);
        String s = scanner.next();
//        用StringBuilder存储结果，一般字符串的拼接都用它，而不是String
        StringBuilder result = new StringBuilder();
//        用堆栈存储[和|的下标
        Stack<Integer> stack = new Stack<>();
        int right = 0;
        for(char ch:s.toCharArray()){
            result.append(ch);
            if(ch == '[' || ch == '|')
                stack.push(right);
//            当前的字符是]，就可以将堆栈里面的[和|弹出来了
            if(ch == ']'){
                if(stack.size() >= 2){
                    int shuhao = stack.pop();
                    int zuokuohao = stack.pop();

//                    将[geshu|st]转变成字符串的形式
                    String st = result.substring(shuhao+1, right);
                    int geshu = Integer.parseInt(result.substring(zuokuohao+1,shuhao));
                    StringBuilder dangqian = new StringBuilder();
                    while(geshu-->0){
                        dangqian.append(st);
                    }
//                    将转换后的字符串变为结果的一部分
                    result.replace(zuokuohao,right+1,dangqian.toString());
//                    right下标指向当前result的最后一个字符
                    right = zuokuohao + dangqian.length() - 1;
                }else{
                    System.out.println("您的输入错误！！！");
                }
            }
            right++;

        }
        if(!stack.isEmpty())
            System.out.println("不是对的哦！！！");
        System.out.println(result.toString());
    }