解压字符串（带括号的匹配）

题目描述

输入数据保证不会出现冗余括号，且表示重复的数字一定合法且大于1，即不会出现：
(A)2B ------- （应为：A2B)
((AB))2C -----(应为：（AB)2C)
(A)B ----- （应为：AB）
A1B，（AB)1C，（应为 AB，ABC）
注意：数字可能出现多位数即A11B或者(AB)10C或者A02这种情况。

A11B = AAAAAAAAAAAB

(AB)10C = ABABABABABABABABABABC

A02 = AA

数据分布：

对于60%的数据，括号不会出现嵌套，即不会有 ((AB)2C)2这种结构。

对于80%的数据，括号最多只嵌套一层，即不会有 (((AB)2C)2D)99 这种结构。

对于100%的数据，括号可以嵌套任意层。

输入描述

第一行是正整数C(C <= 100)，表示下面有C组数据。之后C行，每行为一组数据，每组数据为一个字符串。

每个字符串由A-Z,数字0-9和(,)组成表示一个压缩后的串，保证输入数据一定合法且字符串长度小于50。

输出描述

输出C行，每行对应一个数据的输出结果，表示压缩前的字符串，保证每个字符串展开后的长度不超过10^6。

示例1

输入

A11B
(AA)2A
((A2B)2)2G
(YUANFUDAO)2JIAYOU
A2BC4D2

输出

AAAAAAAAAAAB
AAAAA
AABAABAABAABG
YUANFUDAOYUANFUDAOJIAYOU
AABCCCCDD

练习地址

https://www.nowcoder.com/questionTerminal/8bd5e502931a4b8d84bfd485258c16e5?commentTags=Python

算法思路

• 首先检查输入是否合格，即括号是否匹配成功 见方法

• 先定一个二维数组result[][]来存放当前括号内的字符串

• 从左到右扫描字符串，每遇到一个'('，就给result多加一行来存放新出现括号内的字符

• 每遇到一个')'

  • 先提取右括号后面的数字count--字符串或字符重复的次数，注意考虑多位数数字

  • pop出栈result最后的字符串，并乘以count次，加到上一个元素上，也就是pop后的t的最后一个元素中（就是与上一层括号合并的意思）

• 遇到一个落单数字是（比如A2B的2，没有和右括号在一起的）

  • 找到完整的数字count找到后，乘以result[-1][-1]，即最有一个字符，乘以（count-1），再加入原来的result[-1]中

• 遇到一个普通字幕是，只需要将其直接并入result[-1]

• 经过层层合并，最后的结果就在result[0]中

python代码

def is_encode(str):
 # 放左右括号的栈
 bracket = '()'
 open_brackets = []
 close_brackets = [')']
 # 见一个右括号就出一个左括号
 for i in range(len(str)):
 si = str[i]
 # 如果不是括号，下一个
 if bracket.find(si) == -1:
 continue
#       如果是左括号就入栈
 if si == '(':
 open_brackets.append(si)
 continue
 # 走下下面说明就是右括号了，因为上面已经排除了不是字母和左括号了
 if len(open_brackets) == 0:
 # 现在来了个右括号，但是没有匹配的了
 return False
 #上面排除了各种情况，现在开始正常匹配了
 p = open_brackets.pop()
 if p =='(' and si ==')':
 continue
 else:
 return False

 #判断是否还有多余的左括号呀
def is_encode(str):
    # 放左右括号的栈
    bracket = '()'
    open_brackets = []
    close_brackets = [')']
    # 见一个右括号就出一个左括号
    for i in range(len(str)):
        si = str[i]
        # 如果不是括号，下一个
        if bracket.find(si) == -1:
            continue
#       如果是左括号就入栈
        if si == '(':
            open_brackets.append(si)
            continue
        # 走下下面说明就是右括号了，因为上面已经排除了不是字母和左括号了
        if len(open_brackets) == 0:
            # 现在来了个右括号，但是没有匹配的了
            return False
        #上面排除了各种情况，现在开始正常匹配了
        p = open_brackets.pop()
        if p =='(' and si ==')':
            continue
        else:
            return False

    #判断是否还有多余的左括号呀
    if len(open_brackets) > 0:
        return False
    return True

def decode(str):
    if is_encode(str) == False:
        return False
    # 保存字符串
    result = ['']
    j = 0 #记录遍历位置
    while j < len(str):
        # 遇到了新的左括号，开启新的一层
        if str[j] == '(':
            result.append('')
            j += 1
        # 遇到一个右括号，先去找它后面的数字
        elif str[j] == ')':
            k = j + 1 # 记录数字的开头
            j += 1
            while j < len(str) and ord(str[j])>=ord('0') and ord(str[j])<=ord('9'):
                j += 1 #j跳到字符串的结尾
            count = int(str[k:j]) #右括号后面的数字
            current = result.pop() #取出当前成的字符串
            result[-1] += current*count # 乘以对应的次数，与上一层的合并
        # 遇到单独出现的数字，就是没有和右括号在一起的
        elif ord(str[j]) >= ord('0') and ord(str[j]) <= ord('9'):
            k = j
            j += 1
            while j < len(str) and ord(str[j]) >= ord('0') and ord(str[j]) <= ord('9'):
                j += 1
            count = int(str[k:j])
            # 当前的最后字符加上count-1个，因为原来已经有一个了
            result[-1] += result[-1][-1]*(count-1)
        # 单独出现的字符
        else:
            result[-1] += str[j]
            j+= 1
    return result[0]
def main():
    # 输入字符串的个数
    n = int(input())
    # 存放输入的字符串数组
    str_list = []
    for i in range(n):
        str_list.append(input())
    # 循环判断
    for i in str_list:
        print(decode(i))
if __name__ == '__main__':
    main()