题目链接：
https://www.lintcode.com/problem/282/description?_from=collection&fromId=208

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

数据范围：
1、S的长度<=1000;
2、S仅包含大写字母、[、]、|;
3、解压后的字符串长度不超过100000;
4、压缩递归层数不超过10层;

样例：
输入 : "HG[3|B[2|CA]]F"
输出 : "HGBCACABCACABCACAF"
解释 : HG[3|B[2|CA]]F  −−>  HG[3|BCACA]F  −−>  HGBCACABCACABCACAF

解题思路：
首先先将最内层的方括号打开，如果我们找左括号想要找到最内层不太容易，所以我们应该先找右括号，第一个右括号肯定是最内层的压缩字符串，然后再在循环里从该右括号往前找'|'和左括号，然后将其解压，我的思路是将原字符串分成两部分s1和s2，然后将括号内压缩的字符串解压后构造成s3，最后将其拼接，一直这样遍历到原字符串结束。

具体代码如下：

class Solution {
public:
/**
* @param Message: the string xiao Q sent to xiao A.
* @return: the string after decompress
*/

string DecompressString(string &Message) {  
    string s1, s2;  　　　　//s1:前半串 s2：后半串  
    string s3 = "";　　　　 //部分解压后的字符串  
    int index = 0;　　　　  //'|'的位置  
    code:  
        for (int i = 0; i < Message.length(); i++)　　　//遍历右括号  
        {  
            if (Message\[i\] == '\]')  
            {  
                s2 = Message.substr(i + 1, Message.length() - i - 1);　　　//截取后半段字符串  
                for (int j = i; ; j--)　　　　　　　　　　　　　　　　　　　　　 //往前找'|'和'\['  
                {  
                    string ts = "", tss = "";　　　　　　　　　　　　　　　　　 //ts：压缩字符串的个数,压缩的字符串  
                    if (Message\[j\] == '|')index = j;  
                    if (Message\[j\] == '\[')  
                    {  
                        s1 = Message.substr(0, j);　　　　　　　　　　　　　　 //截取前半段字符串  
                        for (int k = j + 1; k < index; k++)ts += Message\[k\];  
                        int t = stoi(ts, 0, 10);　　　　　　　　　　　　　　　　//将string型转为int型  
                        for (int l = index + 1; l < i; l++)tss += Message\[l\];  
                        for (int p = 0; p < t; p++)s3 += tss;　　　　　　　　//构造s3  
                        Message = s1 + s3 + s2;　　　　　　　　　　　　　　　　 //拼接部分解压后的字符串  
                        j += s3.length() - (j - i);　　　　　　　　　　　　　  //将j、i的位置放到新串上  
                        i = j;  
                        s3 = "";　　　　　　　　　　　　　　　　　　　　　　　　　 //清空s3  
                        goto code;　　　　　　　　　　　　　　　　　　　　　　　　 //退出第一轮解压  
                    }  
                }  
            }  
        }  
    return Message;  
}  

};