压缩算法

class Solution {
public:
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     *
     * @param str string字符串
     * @return string字符串
     */
     //返回 str 中一对 '[]' 的左右下标
    pair<int, int> rangeLeftAndRight(string str) {
        int n = str.length();
        pair<int, int> res(string::npos, string::npos);
        bool inBracket = false;
        int bracketCount = 0;
        for (int i = 0; i < n; ++i) {
            if (!inBracket && str[i] == '[') {
                inBracket = true;
                ++bracketCount;
                res.first = i;
            }
            else if (inBracket) {
                if (str[i] == '[')
                    ++bracketCount;
                else if (str[i] == ']') {
                    --bracketCount;
                    if (bracketCount == 0) {
                        res.second = i;
                        return res;
                    }
                }
            }
        }
        return res;
    }
    //返回 [n | AA[m | ...]BB] 压缩字符串的解压串
    string recursion(string str) {
        //去掉两个括号
        int len = str.length();
        str = str.substr(1, len - 2);

        //'|' 的下标位置
        int pos = str.find_first_of('|');
        //获取需要重复的数量
        int strNum = stoi(str.substr(0, pos));
        //str为[] 或 无[] 的字符串
        str = str.substr(pos + 1);            // strNum | AA[]BB[]CC[]DD 的形式剩下 AA[]BB[]CC[]DD
        //获取该字符串中一对 '[]' 的左右下标
        auto lrpos = rangeLeftAndRight(str);
        //如果不存在 '[]' 括号，那么直接把剩下的 str 重复 strNum 次并返回
        if (lrpos.first == string::npos) {
            string temp = "";
            for (int i = 0; i < strNum; ++i)
                temp += str;
            return temp;
        }
        //否则代表还存在 '[]' 括号，需要递归对其解压
        string res = "";
        while (lrpos.first != string::npos) {
            //代表还存在递归重复部分 '[]'
            res += str.substr(0, lrpos.first);            //先把 str 中 '[' 前面的字符加入到 res 中
            res += recursion(str.substr(lrpos.first, lrpos.second - lrpos.first + 1));//需要递归处理 '[]' 部分
            str = str.substr(lrpos.second + 1);          //str 变成 str[pos.second + 1,str.length()-1] 部分的内容，并重复上面的过程
            lrpos = rangeLeftAndRight(str);
        }
        res += str;
        string temp = "";
        for (int i = 0; i < strNum; ++i)
            temp += res;
        return temp;
    }


    string compress(string str) {
        // write code here
        int n = str.length();
        string ans = "";
        int bracketNum = 0;
        bool inBracket = false;
        int left = 0;
        for (int i = 0; i < n; ++i) {
            //刚进入 '[]' 内，记录其下标
            if (!inBracket && str[i] == '[') {
                left = i;
                inBracket = true;
                ++bracketNum;
            }
            else if (inBracket) {
                if (str[i] == '[')
                    ++bracketNum;
                else if (str[i] == ']') {
                    --bracketNum;
                    if (bracketNum == 0) {
                        inBracket = false;
                        ans += recursion(str.substr(left, i - left + 1));
                    }
                }
            }
            else
                ans += str[i];
        }
        return ans;
    }
};

class Solution:
    def compress(self,str):
    # write code here
        astr = str
        t = []
        d = 0
        for i in astr:
            if i == '|':
                t.append(d)
                d += 1
            else:
                d += 1        
        if '|' not in astr&nbs***bsp;not astr:
                return astr
        else:
            index = t.pop()
            for i in range(index + 1, len(astr)):
                if astr[i] == ']':
                    rIndex = i
                    break
            for i in range(index,-1,-1):
                if astr[i] == '[':
                    lIndex = i
                    break
            str1 = astr[:lIndex] + int(astr[lIndex + 1: index]) * astr[index + 1: rIndex] + astr[rIndex + 1:]
            return self.compress(str1)

class Solution {
public:
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     * 
     * @param str string字符串 
     * @return string字符串
     */
	struct Node {
		string str;
		int num;
	};
	stack<Node> st;
    string compress(string str) {
        // write code here
    	int i = 0; 	
    	string t = "";
		int num = 0; 
		while (str[i]) {
			if (str[i] >= '0' && str[i] <= '9') {
				num = num*10 + (str[i] - '0');
			} else if (str[i] == '[') {
				st.push({t, num});
				t = "";
				num = 0;
			} else if (str[i] == ']') {
				string t2 = "";
				if (num == 0) t2 = t;
				for (int i = 0; i < num; i++) {
					t2 += t;
				}
				t = st.top().str + t2;
				num = st.top().num;
				st.pop();
			} else if (str[i] != '|') {
				t += str[i];
			}
			// cout << t << endl;
			i++;
    	}
    	return t;
	}
};

class Solution:
    def compress(self , str):
        stack = []
        letter = ''
 
        for ch in str:
            if ch == ']':
                array_str = ''
                letter = ''
                while letter != '[':
                    array_str += letter
                    letter = stack.pop()
                array_str = array_str[::-1].split('|')
                decompress_str = int(array_str[0]) * array_str[1]
 
                stack.extend(list(decompress_str))
             
            else:
                stack.append(ch)
            print(stack)
        return ''.join(stack)

import java.util.*;


public class Solution {
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     * 
     * @param str string字符串 
     * @return string字符串
     */
    public static String compress (String str) {
        if(!str.contains("[")){
            return str;
        }
        StringBuilder sb=new StringBuilder(str);
        int len=str.length();
        char[] ch=str.toCharArray();
        Deque<Integer> stack=new LinkedList<>();
        for(int i=0;i<len;i++){
            if(ch[i]=='['){
                stack.push(i);
            }else if(ch[i]==']'){
                int l=stack.pop();
                int r=i;
                String s=str.substring(l+1,r);
                String res=helper(s);
                sb.delete(l,r+1);
                sb.insert(l,res);
                break;
            }
        }
        return compress(sb.toString());
    }

    //拆分括号中的
    public static String helper(String str){
        StringBuilder sb=new StringBuilder();
        String[] d=str.split("\\|");
        int num=Integer.parseInt(d[0]);
        String s=d[1];
        for(int i=0;i<num;i++){
            sb.append(s);
        }
        return sb.toString();
    }
}

import re
class Solution:
    def compress(self , s ):
        # write code here
        while re.findall(r'\[(\d+)\|([a-zA-Z]+)\]',s):
            s = re.sub(r'\[(\d+)\|([a-zA-Z]+)\]',lambda match:match.group(2)*int(match.group(1)),s)
        return s

  public String compress (String str) {
    //用一个StringBuilder来存储数据
    StringBuilder  sb = new StringBuilder();
    for(int i = 0 ; i < str.length();i++){
      //当遇到一个[符号时,进行迭代,求出[]的内容
      if(str.charAt(i) == '['){
        //temp 时[]的内容 其中[0]时数据部分,[1]是]对应的位置，因为有for循环，所以下次是从]的后一位添加
        String[] temp = getValue(i+1,str);
        sb.append(temp[0]);
        i = Integer.parseInt(temp[1]);
      }else{
        //不是[符号，就直接添加StringBuilder
        sb.append(str.charAt(i));
      }
    }
    return sb.toString();
  }
  public String[] getValue(int index,String str){
    String[] test = new String[2];
    int right = -1;
    int sum = 0;
    //记录要重复的次数
    for(int i = index;i<str.length();i++){
      //判断|的位置
      if(str.charAt(i)!='|'){
        sum = sum*10+Integer.parseInt(str.substring(i,i+1));
      }else {
        right = i;
        break;
      }
    }
    StringBuilder  sb = new StringBuilder();
    //计算[]的内容，如果再出现[，则继续迭代，出现]，则说明内容已经读完了
    for(int i = right+1;i < str.length();i++){
      if(str.charAt(i)=='['){
        String[] temp = getValue(i+1,str);
        i = Integer.parseInt(temp[1]);
        sb.append(temp[0]);
      }else if(str.charAt(i)==']'){
        right = i;
        break;
      }else{
        sb.append(str.charAt(i));
      }
    }
    StringBuilder  sk = new StringBuilder();
    //将压缩的文字内容继续解压，即不断复制
    for(int i = 0 ; i < sum;i++){
      sk.append(sb.toString());
    }
    test[0] = sk.toString();
    test[1] = String.valueOf(right);
    return test;
  }

    这是一道看起来很简单，但是做起来需要注意细节的问题；
    首先从题目描述中，会觉得这跟表达式求值比较类似，可以用栈，也可以用递归的方式进行解决，使用栈的话，可能需要考虑的细节更多，于是我就采用了递归的做法。

• 首先需要明确递归函数需要做什么，这道题中括号内可能会内嵌括号，我们可以根据这个思路定义我们递归函数的功能：计算和一个 左括号'[' ，匹配的右括号']' 之间的内容解析后的值；
• 对于括号内的内容一定是 " [数字 | 字符串] " 的结构，所以我们可以把数字还原，而之后的字符串部分则又是一个完整的解码过程，一直处处理到和左括号匹配的右括号，然后再将 字符串 解析的结果重复一定的次数

class Solution {
public:
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     *
     * @param str string字符串
     * @return string字符串
     */
    //
    string compresswith(string &str, int &ptr) {
        ptr++;
        int nums = 0;
        // tmp记录需要重复的字符串
        string tmp = "";
        // 将数字还原
        while(str[ptr] >= '0' && str[ptr] <= '9') {
            nums = nums * 10 + str[ptr] - '0';
            ptr++;
        }
        ptr++;
        while(str[ptr] != ']') {
            if(str[ptr] != '[')
                tmp += str[ptr];
            // 当需要重复的字符串中还有嵌套 "[]" 时，递归调用
            else
                tmp += compresswith(str, ptr);
            ptr++;
        }
        // 将字符串重复一定的次数；
        string res = "";
        while(nums > 0) {
            res += tmp;
            nums--;
        }
        return res;
    }

    string compress(string str) {
        // write code here
        string res = "";
        int ptr = 0;
        while(ptr < str.size()) {
            // 如果括号内的内容，则直接加到结果中
            if(str[ptr] != '[') {
                res += str[ptr];
            } else {
                //return compresswith(str, ptr);
                // 当遇到一个左括号时，需要调用递归函数计算出该括号内的表达式解析结果
                res += compresswith(str, ptr);
            }
            ptr++;
        }
        return res;
    }
};

C++ dfs

class Solution {
   public:
    string compress(string str) {
        int n = str.size(), i = 0;
        vector<string> stk;

        function<string()> dfs = [&]() -> string {
            string res;
            int cnt = 0;
            for (++i; isdigit(str[i]); i++) {
                cnt = cnt * 10 + (str[i] - '0');
            }
            for (++i; str[i] != ']'; ++i) {
                if (isalpha(str[i])) res.push_back(str[i]);
                else res += dfs();
            }

            string s;
            while (cnt--) s += res;
            return s;
        };
        string ans;
        while (i < n) {
            if (isalpha(str[i])) ans.push_back(str[i]);
            else ans += dfs();
            ++i;
        }
        return ans;
    }
};

//java 25ms
import java.util.*;


public class Solution {

    public String compress(String str) {

        char[] chars=str.toCharArray();
        return helper(chars,0,chars.length-1);
    }

    private String helper(char[] chars, int i, int j) {
        StringBuilder sb = new StringBuilder();
        while (i<=j){
            if(chars[i]!='['){
                sb.append(chars[i]);
                i++;
            }else if(chars[i]=='['){
                i++;
               //数字
                int tmp=i+1;
                int n=chars[i]-'0';
                while (chars[i]!='|'){
                    i++;
                }
                for (int k =tmp ; k < i; k++) {
                    n=n*10+chars[k]-'0';
                }
                //寻找匹配的窗口
                int p=i+1;
                int cnt=1;
                while (p<=j&&cnt!=0){
                    if(chars[p]=='['){
                        cnt++;
                    }else if(chars[p]==']'){
                        cnt--;
                    }
                    p++;
                }
                //递归
                String s=helper(chars,i+1,p-2);
               //添加【】内的字符串
                for (int k = 0; k < n; k++) {
                    sb.append(s);
                }
                i=p;
            }
        }
        return sb.toString();
    }
}

#include<stack>
#include<cmath>
class Solution {
public:
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     *
     * @param str string字符串
     * @return string字符串
          * 使用编译原理中的思想，使用栈进行遍历，遇到特定字符进行出栈后再入栈
     */
    stack<char> input;
    stack<char> output;
    stack<char> num;
    string compress(string str) {
        // write code here
        for (int i = 0; i < str.length(); i++) {
            if (str[i] == ']') {
                while (input.top() != '|') {
                    output.push(input.top());
                    input.pop();
                }
                input.pop();
                while (input.top() != '[') {
                    num.push(input.top());
                    input.pop();
                }
                input.pop();
                int number = 0;
                while (!num.empty()) {
                    number += int(num.top()-'0') * int(pow(10, num.size()-1));
                    num.pop();
                }
                string sItem;
                while(!output.empty()){
                    sItem += output.top();
                    output.pop();
                }
                for (int j = 0; j < number; j++) {
                    for (int k = 0; k < sItem.length(); k++) {
                        input.push(sItem[k]);
                    }
                }
            }
            else {
                input.push(str[i]);
            }
        }
        string reverseArr;
        while (!input.empty())
        {
            reverseArr += input.top();
            input.pop();
        }
        int size = reverseArr.length();
        char temp;
        for (int i = 0; i < size/2; i++) {
            temp = reverseArr[i];
            reverseArr[i] = reverseArr[size - 1 - i];
            reverseArr[size - 1 - i] = temp;
        }
        return reverseArr;
    }
};

• 栈

  import java.util.*;
  public class Solution {
    private static int id;
    public String compress (String str) {
        if (null == str) {
            return "";
        }
  
        LinkedList<String> strStack = new LinkedList<>();
        id = 0;
  
        while (id < str.length()) {
            char c = str.charAt(id);
            if (Character.isDigit(c)) {
                String digit = getDigit(str);
                strStack.push(digit);
            } else if (Character.isLetter(c) || c == '[' || c == '|') {
                strStack.push(c + "");
                id++;
            } else {
                id++;
  
                LinkedList<String> stk = new LinkedList<>();
                while (! strStack.isEmpty() && ! "|".equals(strStack.peek())) {
                    stk.push(strStack.pop());
                }
  
                strStack.pop();
                String s = getStr(stk);
                int num = Integer.parseInt(strStack.pop());
                StringBuilder sb = new StringBuilder();
                while (num-- > 0) {
                    sb.append(s);
                }
                strStack.pop();
                strStack.push(sb.toString());
            }
        }
  
        Collections.reverse(strStack);
        return getStr(strStack);
    }
  
    private String getDigit(String s) {
        StringBuilder sb = new StringBuilder();
  
        while (Character.isDigit(s.charAt(id))) {
            sb.append(s.charAt(id++));
        }
        return sb.toString();
    }
  
    private String getStr(LinkedList<String> stack) {
        StringBuilder sb = new StringBuilder();
        while (! stack.isEmpty()) {
            sb.append(stack.pop());
        }
        return sb.toString();
    }
  }

import java.util.*;
 
 
public class Solution {
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     *
     * @param str string字符串
     * @return string字符串
     */
    public String compress (String str) {
        // write code here
         StringBuilder s = new StringBuilder();
        int l = 0,index = 0;
        for (int i = 0; i < str.length(); i++) {
            if(l==0){
                if(str.charAt(i)!='[')
                    s.append(str.charAt(i));
                else {
                    l++;
                    index = i+1;
                }
            }else {
                if(str.charAt(i)=='[')
                    l++;
                if(str.charAt(i)==']')
                    l--;
                if(l==0){
                    s.append(getstr(str.substring(index,i)));
                }
            }
        }
        return s.toString();
    }
    private String getstr(String s) {
        int k = 0;
        StringBuilder w = new StringBuilder();
        while (s.charAt(k)>='0'&&s.charAt(k)<='9'){
            w.append(s.charAt(k));k++;
        }
        int a = Integer.parseInt(w.toString());
        int l = 0,index = 0;
        StringBuilder str = new StringBuilder();
        for (int j = k+1; j < s.length(); j++) {
            if (l == 0)
                if (s.charAt(j) != '[')
                    str.append(s.charAt(j));
                else {
                    l++;
                    index = j + 1;
                }
            else {
                if (s.charAt(j) == '[') l++;
                if (s.charAt(j) == ']') l--;
                if (l == 0)
                    str.append(getstr(s.substring(index, j)));
            }
        }
        String q = String.valueOf(str);
        for (int i = 1; i < a; i++) {
            str.append(q);
        }
        return str.toString();
    }
}

class Solution {
public:
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     *
     * @param str string字符串
     * @return string字符串
     */
    string helper(const string& s) {
        int cnt = 0;
        int n = s.size();
        string ret;
        if (n == 0) {
            return ret;
        }
        int i = 0;
        while (isdigit(s[i])) {
            cnt = cnt * 10 + s[i] - '0';
            ++i;
        }
        ++i;
        while (i < n) {
            if (s[i] != '[') {
                ret.push_back(s[i]);
                ++i;
            } else {
                // s[i] == '['
                // [31|mn]abcd...
                // i      j
                // 01234567
                int j = i + 1;
                int count = 1;
                while (count) {
                    if (s[j] == '[') {
                        ++count;
                    } else if (s[j] == ']'){
                        --count;
                    }
                    ++j;
                }
                string cur = s.substr(i + 1, j - i - 2);
                string tmp = helper(cur);
                ret.append(tmp);
                i = j;
            }
        }
        string res;
        while (cnt) {
            if (cnt & 1) {
                res.append(ret);
            }
            cnt >>= 1;
            ret.append(ret);
            // ret += ret;
        }
        return res;
    }
    string compress(string str) {
        // write code here
        int n = str.size();
        string ret;
        int i = 0;
        while (i < n) {
            if (str[i] != '[') {
                ret.push_back(str[i]);
                ++i;
            } else {
                int j = i + 1;
                int count = 1;
                while (count) {
                    if (str[j] == '[') {
                        ++count;
                    } else if (str[j] == ']') {
                        --count;
                    }
                    ++j;
                }
                // cout << str.substr(i + 1, j - i - 1) << endl;
                string cur = str.substr(i + 1, j - i - 2);
                ret.append(helper(cur));
                i = j;
            }
        }
        return ret;
    }
};