题目描述
输入数据保证不会出现冗余括号，且表示重复的数字一定合法且大于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()
网友评论