OD 算法题 B卷【反转每对括号间的子串】

反转每对括号间的子串

• 给出一个字符串s， 仅含有小写英文字母和英文括号’(’ ‘)’；
• 按照从括号内到外的顺序，逐层反转每对括号中的字符串，并返回最终的结果；
• 结果中不能包含任何括号；

示例1
输入：
(abcd)
输出：
dcba

示例2
输入：
(u(love)i)
输出：
iloveu
说明：先反转内部的love子串，然后反转整个字符串；

示例3
输入：
(ed(et(oc))el)
输出：
leetcode

示例4
输入：
a(bcdefghijkl(mno)p)q
输出：
apmnolkjihgfedcbq

示例5
输入：
a(bcdefghijkl(mno)p)
输出：
apmnolkjihgfedcb

python实现

• 栈数据结构

# 输入数据
s = input().strip()# 看到括号，借助栈结构
# 遍历每个字符，( 和字母入栈
stack = []
total_string = ""
inner_string = ""
for c in s:  # 只反转括号内部的字符串if not stack and c.isalpha():if inner_string:total_string += inner_stringinner_string = ""total_string += ccontinueelif c == "(":stack.append(c)elif stack and c.isalpha():stack.append(c)else:  # ) 出栈inner_string = ''while stack:cur_c = stack.pop()if cur_c != "(":inner_string += cur_celse:break# 反转的内部字符串按照字符一次入栈if stack:for cur_c in inner_string:stack.append(cur_c)if total_string and inner_string:total_string += inner_stringprint(total_string)
elif total_string:print(total_string)
else:print(inner_string)