括号平衡的递归方法[python] [英] Recursive method for parentheses balancing [python]

问题描述

任何人有任何想法如何编写一个函数来平衡使用递归括号？

我想要计算每个外部或内部圆括号弹出的次数一个字符串，但然后它会错过这样的情况（）（））（）（或this）（。

我的教师有递归的例子，解决了因子分析和Fibonacci序列的计算数，但她从未真正解决过其他类型的问题。

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 [in（），（（），（（）） ，（）（），）（]：
print{}：{}。格式（s，balanced（s））

（）：True
（（）：False
（（））：True
（）（）：True
）（：False


Anyone have any idea how to write a function that balances parentheses using recursion?

I was thinking of counting the number of times each outer or inner parenthesis pops up in a string, but then it would miss cases like this "()())()(" or this ")(".

My instructor had examples of recursion that solved factorials and calculated numbers of the fibonacci sequence, but she never really went over solving other types of problems.

解决方案

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

这篇关于括号平衡的递归方法[python]的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！