解壓縮字元串

題目描述

　　猿輔導APP需要下發一些宣傳文本給學生，工程師們使用了一種字元壓縮算法，為了簡單起見，假設被壓縮的字元全部為大寫字母序列，A,B,C,D,E……Z,壓縮規則如下：

1. AAAB 可以壓縮為 A3B(單字元壓縮不加括号)

2. ABABA 可以壓縮為 (AB)2A （多字元串壓縮才加括号）

輸入資料保證不會出現備援括号，且表示重複的數字一定合法且大于1，即不會出現：

(A)2B ---------(應為：A2B)

((AB))2C ---------(應為：(AB)2C)

(A)B ---------(應為：AB)

A1B ---------(應為：AB)

　　注意：數字可能出現多位數即 A11B 或者 (AB)10C 或者 A02這種情況

A11B = AAAAAAAAAAAB

(AB)10C = ABABABABABABABABABABC

A02 = AA

資料分布：

對于60%的資料，括号不會出現嵌套，即不會有((AB)2C)2 這種結構。

對于80%的資料，括号最多嵌套1層-，不會有(((AB)2C)2D)99這種結構。

對于100%的資料，括号可以嵌套任意層

輸入描述：

第一行是正整數C（C<=100）,表示下面有C組資料。

之後C行，每一行為一組資料，每組資料為一個字元串。

每個字元串由A-Z,0-9,(,),組成表示一個壓縮後的串，保證輸入資料一定合法且字元串長度小于50

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

輸出描述：

輸出C行，每行讀音一個資料的輸出結果，表示壓縮前的字元串，保證每個字元串展開的長度不超過10^6.

AAAAAAAAAAAB
AAAAA
AABAABAABAABG
YUANFUDAOYUANFUDAOJIAYOU
AABCCCCDD
           

public class Main {
	
	public static void main(String [] str){
		System.out.println(parse("((A2B)2)2G"));
	}	
	
	 public static String parse(String str){
	        StringBuilder sb = new StringBuilder();
	        LinkedList<Integer> len = new LinkedList<>();
	        String temp = ""; // 記錄括号内的字元串
	 
	        // 針對字元串，處理順序依次為：去括号，統計出現次數，拼接結果
	        for(int i=0;i<str.length();i++){
	            char c = str.charAt(i);
	            if(c == '('){
	                len.add(sb.length());
	                continue;
	            }
	            if(c == ')'){
	                // 移除上一個括号開始時的下标
	                int newLeftIndex = len.remove(len.size()-1);
	                temp = sb.substring(newLeftIndex);
	                i++;
	            }
	            // 處理數字
	            int start = i;
	            while (i<str.length() && str.charAt(i)>='0' && str.charAt(i)<='9'){
	                i++;
	            }
	            // 擷取字元後面的數字
	            if(i-start>=1){
	                int count = Integer.valueOf(str.substring(start,i));
	                for(int k=0;k<count-1;k++){
	                    if (temp==""){
	                        sb.append(str.charAt(start-1));
	                    }else {
	                        sb.append(temp);
	                    }
	                }
	                temp = "";
	                i--;//若存在數字，此時i指向的字元并沒有經過上述判斷，是以需要減去1.
	            }else {
	                sb.append(str.charAt(i));
	            }
	        }
	        return sb.toString();
	    }


}