如何改变获得正确答案的周期？

Question

我的任务是创建一个函数，从最里面的对开始，反转常规括号序列中的任何字符串字符。字符串序列可以包含空格、标点符号、字母和括号。所以结果应该是刺痛。

例子

对于字符串

s = "a(bc)de"

输出应该是

reverseParentheses(s) = "acbde".

我写了下面的代码来解决这个问题：

s_i = s   
for i in range(s.count('(')):
    # reverse letters inside parenthesis
    s_i = s_i.replace(s_i[s_i.rindex('(')+1:s_i.index(')')], s_i[s_i.rindex('(')+1:s_i.index(')')][::-1])
    # delete outward parenthesis
    s_i =s_i[:s_i.rindex('(')] + s_i[s_i.rindex('(')+1:]
    # delete inward parenthesis
    s_i =s_i[:s_i.index(')')] + s_i[s_i.index(')')+1:]
    i += 1
print(s_i)

但是，对于以下字符串，我变成了错误结果：

s = "abc(cba)ab(bac)c"

应该是

abcabcabcabc

我明白了

abccabbaabcc

和

s = "The ((quick (brown) (fox) jumps over the lazy) dog)"

应该是这样的：

The god quick nworb xof jumps over the lazy

但我只得到：

The god quick xof nworb jumps over the lazy

我应该如何更正或调整我的代码以使最后两个示例的结果正确？

代码调整

我试图考虑答案和提示，但我无法使用递归。当其中只有两个位于："..(...) (...).., .."

时，我解决了 parantacies 的问题

所以我做了如下代码：

def reverse(s):
#ensure parens are in pairs
if '(' not in s and ')' not in s:
    while '(' in s:
            s = s.replace(s[s.rindex('(')+1:s.index(')')], s[s.rindex('(')+1:s.index(')')][::-1])
            s = s[:s.rindex('(')] + s[s.rindex('(')+1:]
            s = s[:s.index(')')] + s[s.index(')')+1:]
    return s
else:
    if (s[s.index(')'):s.rindex('(')+1] == ''):
        while '(' in s:
                s = s.replace(s[s.rindex('(')+1:s.index(')')], s[s.rindex('(')+1:s.index(')')][::-1])
                s = s[:s.rindex('(')] + s[s.rindex('(')+1:]
                s = s[:s.index(')')] + s[s.index(')')+1:]
        return s
    elif (s[s.index(')'):s.rindex('(')+1] != ''):
        betw = s[s.index(')')+1:s.rindex('(')]
        part1 = s[:s.index(')')+1]
        part2 = s[s.rindex('('):]
        part1 = part1.replace(part1[part1.rindex('(')+1:part1.index(')')], part1[part1.rindex('(')+1:part1.index(')')][::-1])
        part1 = part1[:part1.rindex(')')]
        part2 = part2.replace(part2[part2.rindex('(')+1:part2.index(')')], part2[part2.rindex('(')+1:part2.index(')')][::-1])
        part2 = part2[part2.rindex('(')+1:]
        s = part1+betw+part2
        s = s[:s.rindex('(')] + s[s.rindex('(')+1:]
        s = s[:s.index(')')] + s[s.index(')')+1:]
        while '(' in s:
            s = s.replace(s[s.rindex('(')+1:s.index(')')], s[s.rindex('(')+1:s.index(')')][::-1])
            s = s[:s.rindex('(')] + s[s.rindex('(')+1:]
            s = s[:s.index(')')] + s[s.index(')')+1:]
        return s
    else:
        while '(' in s:
            s = s.replace(s[s.rindex('(')+1:s.index(')')], s[s.rindex('(')+1:s.index(')')][::-1])
            s = s[:s.rindex('(')] + s[s.rindex('(')+1:]
            s = s[:s.index(')')] + s[s.index(')')+1:]
        return s

但是，我认为它不能很好地执行以下示例：

s = "abc(147)ab(123)c(12)asd"

答案应该是："abc741ab321c21asd" 但我得到 "abc12c321ba147asd"

为了得到正确的答案应该改变什么？

Answer 1

您的解决方案不起作用的原因是括号不匹配：

"abc(cba)ab(bac)c"
"   (cba)ab(bac) "
"       )ab(     "

你的方法最终不会奏效：相反，我建议你想出一个更好的方法来确定哪个括号匹配：

def find_paren_set(str):
    # magic
    return left, right

一旦你具备了这种能力，你就可以 while has_parens(str): 直到完成。

补充说明：每次反转一个部分时，内部括号将交换，((ob)) 将变为 )bo(。

Answer 2

由于似乎可以出现任意数量的 () 对，我建议实现一个递归函数，只要括号对仍然存在于第一个级别之外的级别，就可以调用该函数：

def reverseParentheses(s):
    # ensure parens are in pairs
    assert '(' in s and ')' in s

    while '(' in s:
        # Go through and swap strings/letters in the innermost parens only.
        # Then reassign `s` to that newly formatted string 
        #  (after taking out those parens)
        # Call the function again until it purges the string of all parens
        reverseParentheses(s)
    return s

Answer 3

与其手动执行此操作，不如使用专门处理字符串操作的 regular expression module re

import re

def reverseParentheses(s):
    def reverse_interior(m):
        s = m.group()
        return s[-2:0:-1]
    old = ""
    while old != s:
        old = s
        s = re.sub(r'(\([^\(\)]*\))',reverse_interior,s)
    return s

assert reverseParentheses("a(bc)de") == "acbde"
assert reverseParentheses("abc(cba)ab(bac)c") == "abcabcabcabc"
assert reverseParentheses("The ((quick (brown) (fox) jumps over the lazy) dog)") == "The god quick nworb xof jumps over the lazy"
assert reverseParentheses("((ob))") == "ob"

这里的表达式 '(\([^\(\)]*\))' 将搜索 ( 和 ) 之间的任何内容，这些内容是 [^\(\)]* 中定义的字符之一，这反过来意味着任何数字字符那不是 ( 或 )，这样它将搜索匹配的最里面的组，然后我使用函数 re.sub 将字符串中的那些替换为该辅助函数，即"(xyz)" 和 return "zyx" 形式的字符串。由于这仅适用于最内层的组，因此在进行更改时应重复该过程，因此循环。

如何改变获得正确答案的周期？

How change the cycle for getting correct answers?

python

string

python-3.x

cycle