压缩算法
题目描述
小 Q 想要给他的朋友发送一个神秘字符串，但是他发现字符串过于长了，于是小 Q 发明了一种压缩算法对字符串中重复的部分进行了压缩，对于字符串中连续的m个相同字符串S将会压缩为m|S，例如字符串ABCABCABC将会被压缩为[3|ABC]，现在小 Q 的同学收到了小 Q 发送过来的字符串，你能帮助他进行解压缩么？
输入描述
输入只有一行，为压缩过的字符串。
输出描述
输出解压后的字符串。
示例一
输入
HG[3|B[2|CA]]F
输出
HGBCACABCACABCACAF
说明
HG[3|B[2|CA]]F` -> `HG[3|BCACA]F` -> `HGBCACABCACABCACAF
解题思路
注意，本题和LC394. 字符串解码非常类似，都属于解压缩类的题目。
遇到这种题目很容易想到用栈来解决，其主要问题在于遇到不同的符号应该如何进行处理。可以注意到以下几点
数字的长度不一定是1，所以遇到数字不能够马上入栈，需要维护一个变量num来记录每一次。若
num是str类型变量，则遇到数字应该操作num += chnum是int类型变量，则遇到数字应该操作num = num * 10 + int(ch)
完整的数字一定出现在符号"|"前面，故只有当遇到"|"时，才能够把数字加入栈中，且重置数字
当遇到左括号"["的时候，说明一段压缩字符串出现了，若
- 用单栈维护解压过程（字符和数字都放在同一个栈中），则该左括号可入栈也可以不入栈，因为后面待解压的字符串的前面，一定会包含一个数字，此时可以不用
"["作为解压标识符，因为数字可以起到解压停止标识符的作用。 - 用双栈维护解压过程（一个字符栈、一个数字栈），则必须将
"["压入字符栈中来作为解压停止标识符。
当遇到右括号"]"的时候，说明需要进行一次解压缩操作，此时栈顶元素为若干字符串和一个数字num_repeat，需要将栈顶的若干字符串弹出并进行合并，再重复num_repeat次，重新压回栈中。
代码
# 作者：闭着眼睛学数理化
# 算法训练营：278166530
s = input()
stack = list()
num = 0
# 遍历s中的每一个字符ch
for ch in s:
# 若遇到左括号"["，直接入栈
if ch == "[":
stack.append(ch)
# 若遇到"|"，说明数字的计算已经结束
# 把num加入栈中，同时重置num为0
elif ch == "|":
stack.append(num)
num = 0
# 如果遇到数字，则更新num
elif ch.isdigit():
num = num * 10 + int(ch)
# 如果遇到右括号"]"，说明需要进行一次解压缩处理
elif ch == "]":
# 首先构建需要重复的字符串sub_str为空串
sub_str = ""
# 反复弹出栈顶元素字符串，直到遇到数字
# 对于栈顶弹出的字符串，都是需要重复的
# 因此将stack.pop()加到sub_str的前面
while stack and type(stack[-1]) == str:
sub_str = stack.pop() + sub_str
# 再次弹出栈顶元素，得到解压缩需要重复的数字num_repeat
num_repeat = stack.pop()
# 将之前存入的左括号弹出
stack.pop()
# sub_str重复了num_repeat的结果是num_repeat * sub_str
# 将该结果压入栈顶
stack.append(num_repeat * sub_str)
# 如果遇到字母，则直接加入栈顶
else:
stack.append(ch)
# 退出循环后，将栈中所有的字符串合并，得到最终的答案
print("".join(stack))
时空复杂度
时间复杂度：O(N)。每一个元素仅需进出栈一次。
空间复杂度：O(N)。栈所占空间。
