有人知道如何编写一个使用递归平衡圆括号的函数吗?
我想计算字符串中每个外括号或内括号弹出的次数,但这样会漏掉像"()())()"或"this"()这样的情况。
我的老师有递归的例子,可以解决阶乘和计算斐波那契序列的数字,但她从来没有真正解决过其他类型的问题。
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
查找关闭parens的递归方法的工作方式类似于以下
def findClose(chars):
while len(chars) != 0:
if chars[0] == ")":
return True
elif chars[0] == "(":
findClose(chars[1:])
return False #base case
如果你看到一个打开的paren,你只需要调用findClose(chars)
。这是不完整的,这是一种可以用来递归查找关闭parens 的方法