题目描述与示例

题目描述

现需要实现一种算法，能将一组压缩字符串还原成原始字符串，还原规则如下：

  1. 字符后面加数字 N，表示重复字符 N 次。例如：压缩内容为 A3，表示原始字符串为 AAA。
  2. 花括号中的字符串加数字 N，表示花括号中的字符串重复 N 次。例如：压缩内容为{AB}3，表示原始字符串为 ABABAB。
  3. 字符加 N 和花括号后面加 N，支持任意的嵌套，包括互相嵌套。例如：压缩内容可以{A3B1{C}3}3。

输入描述

输入一行压缩后的字符串

输出描述

输出压缩前的字符串

说明

输入输出的字符串区分大小写。

输入的字符串长度的范围为[1, 10000]，输出的字符串长度的范围为[1, 100000]，数字 N 范围[1, 10000]

示例一

输入

A3

输出

AAA

说明

A3 代表 A 字符重复 3 次

示例二

输入

{A3B1{C}3}3

输出

AAABCCCAAABCCCAAABCCC

说明

{A3B1{C}3}3 代表 A 字符重复 3 次，B 字符重复 1 次，花括号中的 C 字符重复 3 次，最外层花括号中的 AAABCCC 重复 3 次

解题思路

注意，本题和LC394. 字符串解码非常类似。区别在于，本题用花括号表示嵌套而不是中括号，数字出现在花括号之后而不是之前。由于数字出现在括号后，属于一种后缀表达式，而后缀表达式是更加适合栈的计算的，因此本题更加简单。

这题也属于括号配对和表达式求值综合起来的栈题。我们从前往后一次遍历原始字符串s中的字符ch，存在以下几种情况：

  1. 遇到字母，入栈
  2. 遇到左括号"{"，入栈，作为解压标识符
  3. 遇到右括号"}"，说明在此之前肯定存在一个左括号已经入栈，我们需要考虑这对括号之间的所有字符串，并且把这些字符串都合并在一起。所以我们要反复地弹出栈顶元素并记录在一个新的字符串str_in_bracket中，直到遇到左括号"{"，
  4. 遇到数字，说明数字之前的字符串需要被重复，需要记录这个数字。

对于前两种入栈的情况，我们可以合并代码，即

if ch == "{" or ch.isalpha():
    stack.append(ch)

对于遇到右括号"}"的情况，代码如下：

if ch == "}":
    str_in_bracket = str()
    while(stack[-1] != "{"):
        str_in_bracket = stack.pop() + str_in_bracket
    stack.pop()    # 此时栈顶元素是"{"，直接弹出
    stack.append(str_in_bracket)

对于遇到数字的情况，有两个地方需要考虑：

  1. 数字num的位数超过1位，如何储存数字。以下代码能够储存位数超过1的数字。
num = num * 10 + int(ch)
  1. 数字什么时候要使用。当一个数字num已经被完全储存，则应该使栈顶的字符串stack[-1]重复num次。这里的判断逻辑是，ch的下一位已经不是数字，或者ch已经到达s的尾部，说明数字已经储存完毕。
if i == len(s)-1 or not s[i+1].isdigit():
    stack[-1] *= num
    num = 0

另外要注意，数字num使用完毕之后，需要重置为0。

上述代码整理后得到：

if ch.isdigit():
    num = num * 10 + int(ch)
    if i == len(s)-1 or not s[i+1].isdigit():
        stack[-1] *= num
        num = 0

代码

Python

# 题目：2023Q1A-解压缩算法
# 分值：200
# 作者：闭着眼睛学数理化
# 算法：栈
# 代码看不懂的地方，请直接在群上提问

s = input()
stack = list()  # 初始化一个栈，在python中可以用list代替栈
num = 0         # 初始化一个变量num为0，用于栈中数字的记录

# 遍历整个字符串s
for i, ch in enumerate(s):
    # 遇到数字，进行数字的计算
    if ch.isdigit():
        # num乘10后加上int(ch)
        num = num * 10 + int(ch)
        # 如果i是s的最后一位索引，或者i的下一个位置i+1不是数字
        if i == len(s)-1 or not s[i+1].isdigit():
            # 那么需要令栈顶字符串重复num次
            stack[-1] *= num
            # 由于num已经使用完毕，需要重置num为0
            num = 0
    # 遇到左括号"{"或者字母，入栈
    elif ch == "{" or ch.isalpha():
        stack.append(ch)
    # 遇到右括号"}"，说明前面必然存在一个左括号与其闭合
    # 将栈顶元素不断弹出，弹出的内容构建成一个新的字符串str_in_bracket
    # 直到遇到与其闭合的左括号，将str_in_bracket重新加入栈顶
    elif ch == "}":
        # 初始化该对闭合括号内的字符串str_in_bracket
        str_in_bracket = str()
        # 不断弹出栈顶元素，直到栈顶元素为一个左括号"{"
        while(stack[-1] != "{"):
            # 将弹出的元素加在str_in_bracket的前面
            str_in_bracket = stack.pop() + str_in_bracket
        # 把左括号弹出
        stack.pop()
        # 把str_in_bracket重新加入栈顶
        stack.append(str_in_bracket)

# 最后需要将栈中的所有字符串再用join()方法合并在一起并输出
print("".join(stack))

Java

import java.util.*;

public class Main {
    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);
        String s = scanner.next();

        Stack<String> stack = new Stack<>();
        int num = 0;

        for (int i = 0; i < s.length(); i++) {
            char ch = s.charAt(i);

            if (Character.isDigit(ch)) {
                num = num * 10 + (ch - '0');
                if (i == s.length() - 1 || !Character.isDigit(s.charAt(i + 1))) {
                    int repeat = num;
                    num = 0;
                    String top = stack.pop();
                    StringBuilder repeated = new StringBuilder();
                    while (repeat-- > 0) {
                        repeated.append(top);
                    }
                    stack.push(repeated.toString());
                }
            } else if (ch == '{' || Character.isLetter(ch)) {
                stack.push(String.valueOf(ch));
            } else if (ch == '}') {
                StringBuilder strInBracket = new StringBuilder();
                while (!stack.isEmpty() && !stack.peek().equals("{")) {
                    strInBracket.insert(0, stack.pop());
                }
                stack.pop();
                stack.push(strInBracket.toString());
            }
        }

        StringBuilder result = new StringBuilder();
        while (!stack.isEmpty()) {
            result.insert(0, stack.pop());
        }

        System.out.println(result.toString());
    }
}

C++

#include <iostream>
#include <vector>
#include <stack>
#include <string>

using namespace std;

int main() {
    string s;
    cin >> s;

    stack<string> stack;
    int num = 0;

    for (size_t i = 0; i < s.length(); ++i) {
        char ch = s[i];

        if (isdigit(ch)) {
            num = num * 10 + (ch - '0');
            if (i == s.length() - 1 || !isdigit(s[i + 1])) {
                int repeat = num;
                num = 0;
                string top = stack.top();
                stack.pop();
                string repeated;
                while (repeat-- > 0) {
                    repeated += top;
                }
                stack.push(repeated);
            }
        } else if (ch == '{' || isalpha(ch)) {
            stack.push(string(1, ch));
        } else if (ch == '}') {
            string str_in_bracket;
            while (stack.top() != "{") {
                str_in_bracket = stack.top() + str_in_bracket;
                stack.pop();
            }
            stack.pop();
            stack.push(str_in_bracket);
        }
    }

    string result;
    while (!stack.empty()) {
        result = stack.top() + result;
        stack.pop();
    }

    cout << result << endl;

    return 0;
}

时空复杂度

时间复杂度：O(N)。仅需一次遍历数组，每一个字符最多出入栈各一次。

空间复杂度：O(N)。栈所占用的额外空间。

说明

华为OD机试有三道题⽬，第⼀道和第⼆道属于简单或中等题，分值为 100 分，第三道为中等或困难题，分值为 200分，总分为 400 分。

机试分数越⾼评级越⾼，⼯资也就越⾼。

关于华为 OD 机试更加详细的介绍可以查看这篇⽂章：华为OD机考须知

关于机考题目汇总可以看这篇文章：华为OD机试真题 2023 A+B+C+D卷 + 2024新卷（Python&Java&C++）⽬录汇总（每⽇更新）

上一篇 【栈】2023C-密码输入检测
下一篇 【栈】2023B-荒岛求生

相关文章