问题描述

给定一个压缩后的字符串，其中包含数字和方括号，要求将其解压缩为原始字符串。压缩规则为 n[str]，表示字符串 str 重复 n 次。例如，3[k]2[mn] 解压缩为 kkkmnmn。如果字符串嵌套如 3[m2[c]]，则表示 m 后跟 cc，总共重复三次，结果为 mccmccmcc。

解题思路

本问题可以通过栈（Stack）结构来有效地处理嵌套和重复的问题。

1. 初始化栈和变量

使用两个栈：

• strStack：用于存放当前的字符串片段，便于在遇到 ] 时能迅速回到最近的字符串状态。
• numStack：用于存放当前的数字（即重复次数），当遇到 [ 时将其保存，方便在 ] 时使用。

同时定义一个变量 currentStr 用于构建当前字符串片段，num 用于累积当前的数字（重复次数）。

2. 遍历字符串

对输入字符串进行逐字符遍历，处理每种字符情况：

• 数字：如果遇到数字，说明它可能是多位数的部分。将其累加到 num 中。

• 左括号 [：当遇到 [ 时，将当前累积的数字 num 和当前的字符串 currentStr 分别压入 numStack 和 strStack，并重置 num 和 currentStr 为初始状态，以便开始处理新的子串。

• 右括号 ]：当遇到 ] 时，需要进行解压缩：

  • 从 numStack 弹出重复次数 repeatTimes。
  • 从 strStack 弹出上一个字符串片段。
  • 将当前的字符串片段 currentStr 重复 repeatTimes 次，并附加到上一个字符串片段上。

• 普通字符：如果是字母，则直接将其添加到 currentStr 中。

3. 结果输出

在遍历完成后，currentStr 就是解压缩后的结果。

4. 问题分析

本问题利用栈结构高效地处理了字符串解压缩中的嵌套结构，类似于计算器在处理括号运算时的操作。栈的后进先出特性使得每当遇到嵌套的[时，可以暂存当前状态（包括字符串片段和重复次数），而当遇到]时，能够从栈中恢复上一个状态，进而逐步构建解压后的字符串。

代码实现

Cpp

#include <bits/stdc++.h>

using namespace std;

string decodeString(const string& s) {
    stack<string> strStack;    // 用于存放字符片段
    stack<int> numStack;       // 用于存放重复次数
    string currentStr = "";    // 当前的字符串片段
    int num = 0;               // 当前的重复次数

    for (char c : s) {
        if (isdigit(c)) {
            // 如果是数字，构建完整的数字（支持多位数）
            num = num * 10 + (c - '0');
        } else if (c == '[') {
            // 遇到 '['，把当前的数字和字符串片段压入栈
            numStack.push(num);
            strStack.push(currentStr);
            // 重置 num 和 currentStr 以准备处理下一个部分
            num = 0;
            currentStr = "";
        } else if (c == ']') {
            // 遇到 ']'，构建当前的解压缩字符串
            int repeatTimes = numStack.top();
            numStack.pop();
            string temp = currentStr;
            currentStr = strStack.top();
            strStack.pop();
            // 重复 temp 并附加到 currentStr
            while (repeatTimes-- > 0) {
                currentStr += temp;
            }
        } else {
            // 如果是普通字符，直接添加到 currentStr
            currentStr += c;
        }
    }

    return currentStr;
}

int main() {
    string compressedStr;
    cout << "输入压缩后的报文: ";
    cin >> compressedStr;

    string result = decodeString(compressedStr);
    cout << "解压后的原始报文: " << result << endl;

    return 0;
}

Python

def decode_string(s: str) -> str:
    str_stack = []  # 用于存放字符片段
    num_stack = []  # 用于存放重复次数
    current_str = ""  # 当前的字符串片段
    num = 0  # 当前的重复次数

    for c in s:
        if c.isdigit():
            # 如果是数字，构建完整的数字（支持多位数）
            num = num * 10 + int(c)
        elif c == '[':
            # 遇到 '['，把当前的数字和字符串片段压入栈
            num_stack.append(num)
            str_stack.append(current_str)
            # 重置 num 和 current_str 以准备处理下一个部分
            num = 0
            current_str = ""
        elif c == ']':
            # 遇到 ']'，构建当前的解压缩字符串
            repeat_times = num_stack.pop()
            temp = current_str
            current_str = str_stack.pop()
            # 重复 temp 并附加到 current_str
            current_str += temp * repeat_times
        else:
            # 如果是普通字符，直接添加到 current_str
            current_str += c

    return current_str


if __name__ == "__main__":
    compressed_str = input("请输入压缩后的报文: ")
    result = decode_string(compressed_str)
    print(result)

Java

import java.util.Stack;

public class DecodeString {

    public static String decodeString(String s) {
        Stack<String> strStack = new Stack<>(); // 用于存放字符片段
        Stack<Integer> numStack = new Stack<>(); // 用于存放重复次数
        StringBuilder currentStr = new StringBuilder(); // 当前的字符串片段
        int num = 0; // 当前的重复次数

        for (char c : s.toCharArray()) {
            if (Character.isDigit(c)) {
                // 如果是数字，构建完整的数字（支持多位数）
                num = num * 10 + (c - '0');
            } else if (c == '[') {
                // 遇到 '['，把当前的数字和字符串片段压入栈
                numStack.push(num);
                strStack.push(currentStr.toString());
                // 重置 num 和 currentStr 以准备处理下一个部分
                num = 0;
                currentStr.setLength(0); // 清空当前字符串片段
            } else if (c == ']') {
                // 遇到 ']'，构建当前的解压缩字符串
                int repeatTimes = numStack.pop();
                String temp = currentStr.toString();
                currentStr.setLength(0); // 清空当前字符串片段
                currentStr.append(strStack.pop()); // 获取上一个字符串片段
                // 重复 temp 并附加到 currentStr
                for (int i = 0; i < repeatTimes; i++) {
                    currentStr.append(temp);
                }
            } else {
                // 如果是普通字符，直接添加到 currentStr
                currentStr.append(c);
            }
        }

        return currentStr.toString();
    }

    public static void main(String[] args) {
        java.util.Scanner scanner = new java.util.Scanner(System.in);
        System.out.print("请输入压缩后的报文: ");
        String compressedStr = scanner.next();
        String result = decodeString(compressedStr);
        System.out.println(result);
        scanner.close();
    }
}

题目内容

为了提升数据传输的效率，会对传输的报文进行压缩处理。

输入一个压缩后的报文，请返回它解压后的原始报文。

压缩规则：$n[str]$，表示方括号内部的 $str$ 正好重复 $n$ 次。

注意 $n$ 为正整数（$0 < n <= 100$），$str$ 只包含小写英文字母，不考虑异常情况。

输入描述

输入压缩后的报文：

1）不考虑无效的输入，报文没有额外的空格，方括号总是符合格式要求的；

2）原始报文不包含数字，所有的数字只表示重复的次数 $n$ ，例如不会出现像 $5b$ 或 $3[8]$ 的输入；

输出描述

解压后的原始报文

注：原始报文长度不会超过$1000$，不考虑异常的情况

样例1

输入

3[k]2[mn]

输出

kkkmnmn

说明

$k$ 重复 $3$ 次，$mn$ 重复 $2$ 次，最终得到 $kkkmnmn$

样例2

输入

3[m2[c]]

输出

mccmccmcc

说明

$m2[c]$ 解压缩后为 $mcc$，重复三次为 $mccmccmcc$