递归分割函数

Question

我正在尝试编写一个函数，将字符串分成两个字符串。第一个字符串应只包含小写字母，而第二个字符串则应只包含大写字母。

我已经提出了一种可行的解决方案，但我希望能够有一个函数只需一次遍历字符串即可完成。我已经尝试了整整一天，但还没有想出解决方案，因此我需要一些帮助。

棘手的部分是我必须使用递归来完成这个任务。我已经想出了一种迭代的解决方案，这很容易，但是如前所述，我必须以递归方式完成。

这是我编写的结合了两个函数的代码：

    def split_rec1(str):
        if str == "":
            return str
        elif str[0].islower():
            return str[0] + split_rec1(str[1:]) 
        else:
        return split_rec1(str[1:])

    def split_rec2(str):
        if str == "":
            return str
        elif str[0].isupper():
            return str[0] + split_rec2(str[1:])
        else:
            return split_rec2(str[1:])

    def split_rec(str):
        return (split_rec1(str), split_rec2(str))

- user2831306

---

这实际上是一个相当不错的作业问题。 - poolie

Answer 1

提醒您可以使用for循环遍历字符串中的字符，例如：

for c in s: print(c)

这将打印每个字符。此外，您可以像这样连接字符串：

'c' + 'b' == 'cb'

考虑到这一点：

>>> def split_case(s):
    uppers = ''
    lowers = ''
    for c in s:
        if c.isupper(): uppers += c
        else: lowers += c
    return(uppers,lowers)

会按照您的要求进行操作：

>>> split_case("ThisIStheSTRiNg")
('TISSTRN', 'histheig')

这不是递归的。由于这是作业，我会把剩下的留给你 ;)

- R Nar

---

这不是递归的。 - Reut Sharabani

检查一下编辑，哈哈，我忘记在那个注释里添加了。 - R Nar

Answer 2

你需要让函数返回两个值（可能是元组形式），以便在递归过程中使用。

如果你不想得到完整的答案，那么只需要考虑“终止”情况即可。

def split_rec(str):
    if str == "":
        return ("","")

编辑 - 现在已经发布了完整的答案，这是我没有使用ROT13编码的完整答案。

def split_rec(str):
    if str == "":
        return ("","")
    up, low = split_rec(str[1:])
    if str[0].isupper():
        return (str[0]+up,low)
    if str[0].islower():
        return (up,str[0]+low)
    else:
        return (up,low)

- Harry Harrison

---

非常感谢！ - user2831306

Answer 3

你可以使用一个辅助函数来创建一个包含大写和小写字符串的元组（缩短主函数）：

def addtuple(t1, t2):
    return tuple(x[0] + x[1] for x in zip(t1, t2))

这是主要的递归函数（返回一个元组 (upper, lower)）：

def split_lower_upper(s):

    # base case - empty string has no upper/lower case letters
    if not s:
        return ("", "")

    # current character is the first character
    c = s[0]

    # if it is an uppercase we add it to upper-cased letters
    if c.isupper():
        return addtuple((c, ""), split_lower_upper(s[1:]))

    # if it is an uppercase we add it to lower-cased letters
    if c.islower():
        return addtuple(("", c), split_lower_upper(s[1:]))

    # if it's ont upper/lower case we filter it by ignoring it
    return split_lower_upper(s[1:])

提示: 不要shadow str。这可能会导致最烦人的错误（并且只是一种不好的做法）。

- Reut Sharabani

---

您不需要使用辅助函数来使用元组（请参见我的答案中的完整示例）。 - Harry Harrison

Answer 4

我倾向于喜欢递归解决方案，每个阶段将问题减半，而不是线性地逐步消减它。

def split_lower_upper(s):
    if len(s) > 1:
        mid = int(len(s) / 2)
        lower_1, upper_1 = split_lower_upper(s[:mid])
        lower_2, upper_2 = split_lower_upper(s[mid:])
        return (lower_1 + lower_2, upper_1 + upper_2)
    if s.isupper():
        return ("", s)
    else:
        return (s, "")

print(split_lower_upper("tNhIaCtEs"))   # => ('thats', 'NICE')

- pjs