我已经坚持了一段时间,我无法提出递归情况,特别是我不明白如何拆分列表以检查其是否平衡。如果有人能帮助我,我将不胜感激。
def balanced_str(s):
"""
Return whether string s is balanced or not. A balanced string is one where
the string contains no parentheses
>>> balanced_str('a')
True
>>> balanced_str('abbcsi')
True
>>> balanced_str('ak)')
False
>>> balanced_str('hah(dh')
False
>>> balanced_str('()')
True
>>> balanced_str('(hghghgh)')
True
>>> balanced_str('((a))')
True
>>> balanced_str('((hahsh))')
True
>>> balanced_str('(gfjf)h)')
False
>>> balanced_str('(hhg)(hfhg)')
True
"""
if '(' not in s and ')' not in s:
return True
elif '(' in s and ')' not in s or ')' in s and '(' not in s:
return False
else:
if s[0] == '(' and s[len(s) - 1] == ')':
return balanced_str(s[1:len(s) - 2])
一种简单的迭代方法可能是创建一个微小的词法分析器。当出现左括号(
时,它将增加计数器o
,如果出现右括号)
,它将减少计数器。如果同时搜索字符串,计数器o
变为负数,或者在循环结束时计数器o
不为零,则测试失败:
def balanced_str(s):
o = 0
for c in s:
if c == ')':
if o <= 0:
# this only happens if there are more closing
# parentheses then opening parentheses.
return False
o -= 1
elif c == '(':
o += 1
# all parentheses should be closed
return o == 0
对于您的测试用例,此方法有效:
>>> balanced_str('a')
True
>>> balanced_str('abbcsi')
True
>>> balanced_str('ak)')
False
>>> balanced_str('hah(dh')
False
>>> balanced_str('()')
True
>>> balanced_str('(hghghgh)')
True
>>> balanced_str('((a))')
True
>>> balanced_str('((hahsh))')
True
>>> balanced_str('(gfjf)h)')
False
>>> balanced_str('(hug)(hfhg)')
True
对于递归方法,您可以创建一个采用更多参数(即我们目前看到的括号数)的小辅助函数。在这种方法下面,您可以看到如何在没有帮助程序函数的情况下通过使用global
来做到这一点
def balanced_str(s):
"""
Return whether string s is balanced or not. A balanced string is one where
the string contains no parentheses
>>> balanced_str('a')
True
>>> balanced_str('abbcsi')
True
>>> balanced_str('ak)')
False
>>> balanced_str('hah(dh')
False
>>> balanced_str('()')
True
>>> balanced_str('(hghghgh)')
True
>>> balanced_str('((a))')
True
>>> balanced_str('((hahsh))')
True
>>> balanced_str('(gfjf)h)')
False
>>> balanced_str('(hhg)(hfhg)')
True
"""
return helper(s,0)
def helper(s, numP):
if len(s)==0: return numP==0
if numP < 0: return False
if s[0] == "(": return helper(s[1:], numP+1)
elif s[0] == ")": return helper(s[1:], numP-1)
return helper(s[1:], numP)
没有助手:
def balanced_str(s):
"""
Return whether string s is balanced or not. A balanced string is one where
the string contains no parentheses
>>> balanced_str('a')
True
>>> balanced_str('abbcsi')
True
>>> balanced_str('ak)')
False
>>> balanced_str('hah(dh')
False
>>> balanced_str('()')
True
>>> balanced_str('(hghghgh)')
True
>>> balanced_str('((a))')
True
>>> balanced_str('((hahsh))')
True
>>> balanced_str('(gfjf)h)')
False
>>> balanced_str('(hhg)(hfhg)')
True
"""
try:
numP
except NameError:
numP = 0
global numP
if len(s)==0: return numP==0
if numP < 0: return False
if s[0] == "(":
numP += 1
return balanced_str(s[1:])
elif s[0] == ")":
numP -= 1
return balanced_str(s[1:])
return balanced_str(s[1:])
的候选解决方案:
def balanced(iterable, semaphore=0):
if semaphore < 0 or len(iterable) == 0:
return semaphore == 0
first, *rest = iterable
return balanced(rest, semaphore + { "(": 1, ")": -1 }.get(first, 0))
我已将balanced_str()
重命名为 balanced()
,因为如果它编写正确,它应该处理字符串或字符列表(即可迭代对象):
>>> balanced('a')
True
>>> balanced(['a', 'b', 'b', 'c', 's', 'i'])
True
>>> balanced('ak)')
False
>>> balanced(['h', 'a', 'h', '(', 'd', 'h'])
False
>>> balanced('()')
True
>>> balanced(['(', 'h', 'g', 'h', 'g', 'h', 'g', 'h', ')'])
True
>>> balanced('((a))')
True
>>> balanced(['(', '(', 'h', 'a', 'h', 's', 'h', ')', ')'])
True
>>> balanced('(gfjf)h)')
False
>>> balanced(['(', 'h', 'h', 'g', ')', '(', 'h', 'f', 'h', 'g', ')'])
True
我相信其他提出的解决方案也是如此,而不仅仅是我的。
这是一种递归方法。我认为这是非常简洁直观的
def is_balanced(s, c=0):
if len(s) == 0:
if c == 0:
return True
else:
return False
elif s[0] == "(":
c = c + 1
return is_balanced(s[1 : len(s)], c)
elif s[0] == ")":
c = c - 1
return is_balanced(s[1 : len(s)], c)
else:
return is_balanced(s[1 : len(s)], c)