Rekursiv auf symmetrische Zeichenfolge in Python überprüfen

Question

Ich bin seit einer ganzen Weile darauf fest, ich kann nicht mit rekursiven Fällen kommen, insbesondere verstehe ich nicht, wie man eine Liste aufteilen, um zu überprüfen, ob es ausgewogen ist. Wenn jemand mir helfen könnte, würde ich es sehr schätzen.

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

Ein einfacher, iterativer Ansatz könnte darin bestehen, einen winzigen Lexer zu erstellen. Es wird einen Zähler o erhöhen, wenn eine öffnende Klammer ( erscheint, und verringert den Zähler, wenn eine schließende Klammer ) erscheint. Wenn mittlerweile die Zeichenfolge suchen der Zähler o negativ wird, oder durch das Ende der Schleife wird der Zähler o nicht Null ist, schlägt der Test fehl:

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 

Für Ihre Testfälle dieser Ansatz funktioniert:

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

Für einen rekursiven Ansatz können Sie eine kleine Hilfsfunktion erstellen, die mehr Parameter benötigt (dh die Anzahl der Paren, die wir bisher gesehen haben). Unterhalb dieser Ansatz können Sie sehen, wie Sie es ohne eine Hilfsfunktion durch die Verwendung von 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) 

Ohne Helfer tun können:

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

Hier ist meine Kandidatenlösung:

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

Ich habe balanced_str() in balanced() umbenannt, denn wenn es richtig geschrieben ist, sollte es mit Strings oder li umgehen M an Zeichen Iterables):

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

Ich glaube, das auch von anderen vorgeschlagenen Lösungen wahr ist, nicht nur mir.