圆括号平衡的递归方法[python]

2024-03-28 12:06:53 发布

您现在位置:Python中文网/ 问答频道 /正文

有谁知道如何编写一个使用递归平衡圆括号的函数吗?

我在想计算一个字符串中每个外圆括号或内圆括号弹出的次数,但这样会漏掉像这样的情况。

我的老师有递归的例子,可以解阶乘,计算斐波那契数列的个数,但她从来没有真正解决过其他类型的问题。


Tags: 函数字符串类型情况老师次数例子个数
2条回答

一个递归的方法来寻找结束的paren的工作方式是这样的

def findClose(chars):
    while len(chars) != 0:
        if chars[0] == ")":
            return True
        elif chars[0] == "(":
            findClose(chars[1:])

    return False       #base case

如果您看到一个打开的paren This is not complete,这是一个可以递归地查找关闭paren的方法

def balanced(s, i=0, cnt=0):
    if i == len(s): return cnt == 0
    if cnt < 0: return False
    if s[i] == "(": return  balanced(s, i + 1, cnt + 1)
    elif s[i] == ")": return  balanced(s, i + 1, cnt - 1)
    return balanced(s, i + 1, cnt)

for s in ["()", "(()", "(())", "()()", ")("]:
    print "{}: {}".format(s, balanced(s))

(): True
((): False
(()): True
()(): True
)(: False

相关问题 更多 >