【算法】解压字符串（猿辅导笔试题）

猿辅导APP需要下发一些宣传文本给学生，工程师们使用了一种字符压缩算法，为简单起见，假设被压缩的字符全部为大写字母序列，A,B,C,D…Z,压缩规则如下：
1.AAAB可以压缩为A3B (单字符压缩不加括号)
2.ABABA可以压缩为(AB)2A （多字符串压缩才加括号）

输入数据保证不会出现冗余括号，且表示重复的数字一定合法且大于1，即不会出现：
1.（A)2B ------- （应为：A2B）
2. ((AB))2C,-----(应为：（AB)2C )
3. （A)B ----- （应为：AB）
4. A1B，（AB)1C，（应为 AB，ABC）

输入描述

第一行是正整数C(C <= 100)，表示下面有C组数据。之后C行，每行为一组数据，每组数据为一个字符串。

每个字符串由A-Z,数字0-9和(,)组成表示一个压缩后的串，保证输入数据一定合法且字符串长度小于50。

输出描述

输出C行，每行对应一个数据的输出结果，表示压缩前的字符串，保证每个字符串展开后的长度不超过10^6。

输入示例

5
A11B
(AA)2A
((A2B)2)2G
(YUANFUDAO)2JIAYOU
A2BC4D2

输出示例

AAAAAAAAAAAB
AAAAA
AABAABAABAABG
YUANFUDAOYUANFUDAOJIAYOU
AABCCCCDD

解法思路
对于有数字的位，其操作依赖于紧邻的前项，比较容易想到用栈来解决，针对栈中出现括号和非括号来进行判断分类求解，然后将解压后的字符串重新压入栈中，因为有嵌套的括号情况。
由于题中已说明输入数据均为合法的，不会出现冗余括号，实现上更加简单，但仍需要注意栈的逆序特点。

Java实现
注：这里简化了一下，没有写输入输出语句，实际牛客考试中需要自己写输入和输出。

import java.util.ArrayDeque;
import java.util.ArrayList;
import java.util.Deque;
import java.util.List;

class Solution{

    public String solve(String source){
        StringBuilder sb = new StringBuilder();
        Deque<Character> stack = new ArrayDeque<>();
        for(int i=0;i<source.length();i++){
            char c = source.charAt(i);
            if(c>='0' && c<='9'){
                if(stack.peek() == ')'){
                    stack.pop();
                    List<Character> list = new ArrayList<>();
                    while(stack.peek()!='('){
                        list.add(stack.pop());   // 逆序
                    }
                    stack.pop();
                    for(int j=0;j<c-'0';j++){
                        for(int k=list.size()-1;k>=0;k--){
                            stack.push(list.get(k));
                        }
                    }
                }else{
                    char repeatChar = stack.pop();
                    for(int j=0;j<c-'0';j++){
                        stack.push(repeatChar);
                    }
                }
            }else stack.push(c);
        }
        while(!stack.isEmpty()){
            sb.append(stack.pop());
        }
        return sb.reverse().toString();
    }
    
	// 以下是测试代码，可忽略
    public static void main(String[] args) {
    	System.out.println(new Solution().solve("A3B2C6"));
    	System.out.println(new Solution().solve("(A3B2)3A"));
        System.out.println(new Solution().solve("((AC)2B2)3D"));
    }
}

本文地址：https://blog.csdn.net/Steven_L_/article/details/107660617