Pythonの平衡文字列を再帰的にチェックする

Question

私はかなり長い間、この問題に悩まされていました。再帰的なケースを思いつくことはできません。特にバランスのとれた場合にリストを分割する方法を理解できません。 誰かが私を助けることができたら、私は本当にそれを感謝します。

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]) 

Answer 1

単純な反復的なアプローチでは、小さなレクサーを作成することができます。開始括弧(が表示されるとカウンタ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 

Answer 2

再帰的なアプローチでは、より多くのパラメータ（これまでに見てきた括弧の数）を必要とする小さなヘルパー関数を作成することができます。このアプローチの下に、あなたはヘルパーなし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:]) 

Answer 3

ここに私の候補ソリューションです：

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()に変更しました。正しく書かれていれば、文字列またはli文字（すなわち、 反復可能オブジェクト）：

>>> 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 

私だけではなく、鉱山、これは、他のソリューション提案の真実であると信じています。