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

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

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)

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

数字num的位数超过1位，如何储存数字。以下代码能够储存位数超过1的数字。

num = num * 10 + int(ch)

数字什么时候要使用。当一个数字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)。栈所占用的额外空间。