压缩算法

#include <bits/stdc++.h>
using namespace std;
//LeetCode解法 双栈
int main()
{
    string s;
    cin >> s;
    stack<int> numStk;
    stack<string> strStk;
    int cnt = 0;
    string ans;
    for(int i = 0; i < s.size(); ++i) {
        if(s[i] >= '0' && s[i] <= '9') {
            cnt = cnt * 10 + s[i] - '0';
        }
        else if(s[i] == '|') {
            numStk.push(cnt);
            cnt = 0;
        }
        else if(s[i] == '[') {
            strStk.push(ans);
            ans.clear();
        }
        else if(s[i] == ']') {
            int k = numStk.top();
            numStk.pop();
            while(k--) strStk.top() += ans;
            ans = strStk.top();
            strStk.pop();
        }
        else ans += s[i];
    }
    cout << ans << endl;
    return 0;
}

import java.util.*;
public class Main{
    public static void main(String args[]) {
        Scanner scan = new Scanner(System.in);
        String str = scan.next();
            while(str.contains("]")) {
                int right = str.indexOf("]");
                int left = str.lastIndexOf("[",right);
                String tmp = str.substring(left+1,right); // 2|CA
                String[] splits = tmp.split("\\|");
                int n = Integer.parseInt(splits[0]);
                String str2 = ""; 
                for(int i = 0; i < n;i++) {
                    str2 += splits[1];
                }
                str  = str.replace("[" + tmp + "]", str2);//HG[3|BCACA]F]

            }
            System.out.println(str);
        }
}

//递归解决，C++

#include<bits/stdc++.h>
using namespace std;
string decode(string str)
{
    int x=-1,y=-1,z=-1;
    int i=0;
    while(i<str.size())
    {
        if(str[i]=='[')
        {
            x=i;
        }
        if(str[i]=='|')
        {
            y=i;
        }
        if(str[i]==']')
        {
            z=i;
            break;
        }
        i++;
    }
    if (x!=-1&&y!=-1&&z!=-1)

    {
    int num=0;
    string num_s=str.substr(x+1,y-x-1);
    //cout<<num_s<<endl;
    for(int j=0;j<num_s.size();j++)
    {
        num=num*10+(num_s[j]-'0');
    }
    //cout<<num<<endl;

    string sstr=str.substr(y+1,z-y-1);
    //cout<<sstr<<endl;
    string ssstr="";
    while(num--)
    {
        ssstr=ssstr+sstr;
    }
    //cout<<ssstr<<endl;
    str=str.substr(0,x)+ssstr+str.substr(z+1);
    //cout<<str<<endl;
    return decode(str);
    }
    return str;
}
int main()
{
    string str;
    cin>>str;
    cout<<decode(str);
    //cout<<str;
    return 0;

}

这题考的应该是“栈”这个知识点，碰到过原题，这里给出迭代的写法，栈用LinkedList实现

1. stack_res用于暂时保存在 ' ] ' 之前记录的结果，保存的形式如[HG],[B],[CA]

2. mutil_stack保存的是数字，如[3],[2]

3. 在遇到 ' ] ' 时， 从mutil_stack 队尾取出数字N，对当前字符串[CA] 复制N次。并从stack_res取出上一轮暂存的结果[B]拼接[CA CA]-->[B CACA]

   import java.util.LinkedList;
   import java.util.Scanner;
   public class Main{
     public static void main(String[] args) {
         Scanner in =new Scanner(System.in);
         String str=in.nextLine();
         int mutil=0;//乘数
         LinkedList stack_res=new LinkedList();//结果暂存
         LinkedList mutil_stack=new LinkedList();
         StringBuilder temp=new StringBuilder();
         for(int i=0;i<str.length();i++) { //toCharArray() 需要O(n)的空间复杂度,不打算使用
             if(str.charAt(i)=='[') {
                 stack_res.addLast(temp.toString());//保存上一次的结果 [HG]            
                 temp=new StringBuilder();//用于接收新的字母[B]
             }else if(str.charAt(i)==']') {
                 StringBuilder temp2=new StringBuilder();
                 //取出乘数             
                 int num= mutil_stack.removeLast();
                 for(int j=0;j<num;j++) {
                     temp2.append(temp);
                 }
                 temp=new StringBuilder(stack_res.removeLast()+temp2);
             }else if(str.charAt(i)=='|') {//乘数[3]入栈
                 mutil_stack.addLast(mutil);
                 mutil=0;//寻找新的乘数比如[2]
             }
             else if(str.charAt(i)>='0'&&str.charAt(i)<='9') {
                 //预防数字出现 [ 19  |a]
                 mutil=mutil*10+Integer.parseInt(str.charAt(i)+"");
             }else {
                 //正常字母
                 temp.append(str.charAt(i));
             }
         }
         System.out.print(temp.toString());
     }
   }

让我来个go语言
package main

import (
    "fmt"
    "strings"
)

func find(s string) (int, int) {
    j := 0
    for j < len(s) && s[j] != ']' {
        j++
    }
    i := j - 1
    for i >= 0 && s[i] != '[' {
        i--
    }
    return i, j
}

func main() {
    var s string
    fmt.Scanln(&s)
    ans := ""
    for  {
        x, y := find(s)   // 找到匹配的[]的位置
        if x == -1 && y == len(s) {
            break
        }
        num := 0
        k := x + 1
        for s[k] != '|' {
            num *= 10
            num += int(s[k] - '0')
            k++
        }   //计算重复数字
        ans = s[:x] + strings.Repeat(s[k + 1:y], num) + s[y + 1:]
        s = ans  //更新s
    }

    fmt.Println(s)
}

#include <string>
#include <iostream>

// c++ 5 ms python 135ms 
// 思路参考大神
using namespace std;
string decode(const string& str)
{
    int i = 0;
    int x = -1, y = -1, z = -1;
    while (i < str.size())
    {
        if (str[i] == '[')
            x = i;
        else if (str[i] == '|')
            y = i;
        else if (str[i] == ']')
        {
            z = i;
            break;
        }
        i += 1;
    }
    if (x != -1 && y != -1 && z != -1)
    {
        int times = atoi(str.substr(x+1, y-x-1).c_str());
        string sub = str.substr(y+1, z-y-1);
        auto subs = [=]() {string tmp; for (int i = 0; i < times; i++) {tmp += sub;} return tmp;};
        string decode_str = str.substr(0, x) + subs() + str.substr(z+1);
        return decode(decode_str);
    }
    return str; // 如果一个中括号都没有，说明没有需要解码的部分
}

int main()
{
    string str;
    while (cin >> str)
        cout << decode(str) << endl;
    return 0;
}

//用正则
var  a = readline();
fn(a);
function fn(str) {
            var reg = new RegExp(/\[[^\[\]]*?\]/g);
            var arr = reg.exec(str);
            while (arr != null) {
                let tmp = arr[0];
                let record = arr[0];
                tmp = tmp.split('');
                tmp.pop();
                tmp.shift();
                tmp = tmp.join('')
                tmp = tmp.split('|');
                let temp = tmp[1].repeat(Number(tmp[0]));
                str = str.replace(record, temp);
                var reg = new RegExp(/\[[^\[\]]*?\]/g);
                var arr = reg.exec(str);
                 
            }
            console.log(str)
        }

import sys
while True:
    line = sys.stdin.readline().strip()
    if line == "":
        break
    stack = []
    for s in line:
        if s != ']':
            stack.append(s)
        else:
            temp = ''
            while stack and stack[-1] != '|':
                temp = stack.pop() + temp
            stack.pop()
            times = ''
            while stack and stack[-1].isdigit() and stack[-1] != '[':
                times = stack.pop() + times
            stack.pop()
            stack.append(int(times) * temp)
    print("".join(stack))

import java.util.Scanner;

public class Main{
	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);
		String s = sc.nextLine();
		System.out.println(tar(s));
	}

	// 递归方法
	public static String tar(String s) {
		// 递归结束的判断，说明全部解压完毕
		if (!s.contains("[") && !s.contains("|")) {
			return s;
		}
		// 形如2|cd的变成cdcd
		if (!s.contains("[") && s.contains("|")) {
			String x[] = s.split("\\|");
			int num = Integer.parseInt(x[0]);
			StringBuffer sb = new StringBuffer();
			for (int i = 0; i < num; i++)
				sb.append(x[1]);
			return sb.toString();
		}
		// 上面if都不执行，说明既有[又有|，说明没有递归到最里层
		char a[] = s.toCharArray();
		// 用来存储完全解压后的字符串
		StringBuffer sb = new StringBuffer();
		for (int i = 0; i < a.length; i++) {
			// 设置栅栏，使得"["与"]"的个数相同，比如HG[3|B[2|CA]]F,会取得[3|B[2|CA]]
			int latch = 0;
			if (a[i] == '[') {
				latch++;
				// 指针往前进一位，形如[3|B[2|CA]]，需要得到3|B[2|CA],为了去掉最外面的括号
				i++;
				if (a[i] == ']') {
					latch--;
				}
				// 用来存储部分解压的字符串，比如有字符串HG[3|B[2|CA]]F中的,这次while循环结束 s1会变成3|B[2|CA]
				// 这里再次进行'['的判断是存在[[]]的情况
				StringBuffer s1 = new StringBuffer();
				while (!(a[i] == ']' && latch == 0)) {
					if (a[i] == '[') {
						latch++;
					}
					if (a[i] == ']') {
						latch--;
						if (latch == 0) {
							// 说明到了最外层的]了，不进行下面的appen，为了取出最外层的[]
							continue;
						}

					}
					s1.append(a[i]);
					// 指针后移，再次进入while循环
					i++;

				}
				// 如果有初始字符串HG[3|B[2|CA]]F，此时s1为3|B[2|CA]，去除了一层括号，
				String s2 = tar(s1.toString());
				// 判断里面还有没有未解压的字符串，有就继续解压，会递归到最里面的2|CA，得到CACA，返回到s2=3|BCACA,再次进行解压
				while (s2.contains("|")) {
					s2 = tar(s2);
				}
				// 将解压完毕的字符串字符串加到sb后面
				sb.append(s2);
			} else {
				// 如果没有进行压缩的字符串，直接加到末尾就行
				sb.append(a[i]);

			}

		}
		return sb.toString();

	}
}

    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);
        String next = scanner.next();
        scanner.close();
        System.out.println(decode(next));
    }
 
    public static String decode(String words){
        while (words.contains("]")){
            int right = words.indexOf("]");
            int left = words.lastIndexOf("[", right);
            String repeatStr = words.substring(left+1, right);
            String[] split = repeatStr.split("\\|");
            words = words.replace("["+repeatStr+"]",
                    String.join("", Collections.nCopies(Integer.parseInt(split[0]), split[1])));
        }
        return words;
    }