Je suis un débutant en Python et je suis tombé sur cet exercice de vérification si les crochets simples "(", ")" dans une chaîne donnée sont identiques.

J'ai vu des exemples ici en utilisant la commande stack que je n'ai pas encore rencontrée, j'ai donc essayé une approche différente. Quelqu'un peut-il me dire où je me trompe?

def matched(str):
    ope = []
    clo = []
    for i in range(0,len(str)):
        l = str[i]
        if l == "(":
            ope = ope + ["("]
        else:
            if l == ")":
                clo = clo  + [")"]
            else:
                return(ope, clo)
    if len(ope)==len(clo):
        return True
    else:
        return False

L'idée est de regrouper "(" et ")" en deux listes distinctes, puis de comparer la longueur des listes. J'avais également une autre version où j'avais annexé les listes ope et clo avec le i pertinent qui contenait respectivement (ou).

Merci pour votre temps!

12
Vishesh 8 août 2016 à 19:03

25 réponses

Meilleure réponse

Une manière très légèrement plus élégante de le faire est ci-dessous. Il nettoie la boucle for et remplace les listes par une simple variable de compteur. Il retourne également false si le compteur tombe en dessous de zéro afin que matched(")(") renvoie False.

def matched(str):
    count = 0
    for i in str:
        if i == "(":
            count += 1
        elif i == ")":
            count -= 1
        if count < 0:
            return False
    return count == 0
11
Henry Prickett-Morgan 8 août 2016 à 16:37

Cela vérifie si les parenthèses sont correctement appariées, pas seulement s'il y a un nombre égal de parenthèses ouvrantes et fermantes. Nous utilisons un list comme une pile et nous poussons dessus lorsque nous rencontrons des parenthèses ouvrantes et en sortons lorsque nous rencontrons des parenthèses fermantes.

Le principal problème de votre solution est qu'elle compte seulement le nombre de parenthèses mais ne correspond pas. Une façon de garder une trace de la profondeur d'imbrication actuelle consiste à pousser les parenthèses ouvrantes sur une pile et à les extraire de la pile lorsque nous rencontrons une parenthèse fermante.

def do_parentheses_match(input_string):
    s = []
    balanced = True
    index = 0
    while index < len(input_string) and balanced:
        token = input_string[index]
        if token == "(":
            s.append(token)
        elif token == ")":
            if len(s) == 0:
                balanced = False
            else:
                s.pop()

        index += 1

    return balanced and len(s) == 0
9
kreld 8 août 2016 à 16:42

Voici une autre façon de le résoudre en ayant un compteur qui suit le nombre de parenthèses ouvertes qui sont différentes en ce moment. cela devrait prendre en charge tous les cas.

def matched(str):
    diffCounter = 0
    length = len(str)
    for i in range(length):
        if str[i] == '(':
            diffCounter += 1
        elif str[i] == ')':
            diffCounter -= 1
    if diffCounter == 0:
        return True
    else:
        return False
1
NinjaG 9 juil. 2018 à 18:26

Vous pouvez le faire en quelques lignes en utilisant accumuler (depuis itertools). L'idée est de calculer un niveau de parenthèse cumulé passant par la chaîne avec des parenthèses ouvrantes comptant comme niveau + 1 et des parenthèses fermantes comptant comme niveau-1. Si, à tout moment, le niveau accumulé tombe en dessous de zéro, il y a une parenthèse de fermeture supplémentaire. Si le niveau final n'est pas nul, alors il manque une parenthèse fermante:

from itertools import accumulate
def matched(s):
    levels = list(accumulate((c=="(")-(c==")") for c in s))
    return all( level >= 0 for level in levels) and levels[-1] == 0
1
Alain T. 26 juil. 2019 à 14:15

Vous voudrez peut-être essayer ceci:

def balance_check_new(s):
 if len(s) %2 !=0:
    return False
 exists = set('([{')
 matches = ([('(',')'),('[',']'),('{','}')])
 stack = []
 for paren in s:
    if paren in exists:
        stack.append(paren)
    else:
        if len(stack) == 0:
            return False
        last_open = stack.pop()
        if (last_open,paren) not in matches:
            return False
 return len(stack) == 0
0
baduker 19 mars 2018 à 12:37
def parenthesis_check(parenthesis):
    chars = []
    matches = {')':'(',']':'[','}':'{'}
    for i in parenthesis:
        if i in matches:
            if chars.pop() != matches[i]:
                return False
        else:
            chars.append(i)
    return chars == []        
0
Nons 20 mars 2018 à 05:09
a = "((a+b)*c)+(b*a))"

li = list(a)
result = []

for i in range(0, len(a)):

    if a[i] == "(":
        result.append(i)
    elif a[i] == ")":
        if len(result) > 0:
            result.pop()
        else:
            li.pop(i)

for i in range(0, len(result)):
    li.pop(result[i])

print("".join(li))
3
Rajiv 14 févr. 2017 à 12:47

Le problème avec votre approche est que vous ne considérez pas la commande. La ligne suivante passerait: ))) (((. Je suggère de garder le nombre de parenthèses ouvertes et fermées:

  • counter commence à partir de 0
  • chaque ( compteur d'incrément de symbole
  • chaque symbole ) décrémente le compteur
  • si à tout moment le compteur est négatif c'est une erreur
  • si à la fin du compteur de ligne est 0 - la chaîne a des parenthèses correspondantes
2
Teivaz 8 août 2016 à 16:22

Si la séquence de parenthèses n'est pas un problème (chaînes comme )(), ce code est plus rapide:

def matched_parenthesis(s):
    return s.count('(') == s.count(')')

Testé avec une chaîne de 15 Ko, il est d'environ 20 μs contre. 1 ms itérant sur toute la chaîne.

Et pour moi, l'ordre n'est pas un problème car le protocole sous-jacent garantit que la chaîne est bien formée.

0
Bruno Thomas 26 juil. 2017 à 11:41

Une alternative pour vérifier les parenthèses imbriquées équilibrées :

def is_balanced(query: str) -> bool:
    # Alternative: re.sub(r"[^()]", "", query)
    query = "".join(i for i in query if i in {"(", ")"})
    while "()" in query:
        query = query.replace("()", "")
    return not query


for stmt in [
    "(()()()())",    # True
    "(((())))",      # True
    "(()((())()))",  # True
    "((((((())",     # False
    "()))",          # False
    "(()()))(()",    # False
    "foo",           # True
    "a or (b and (c or d)",  # False
    "a or (b and (c or d))"  # True
    "a or (b and (c or (d and e)))",  # True
]:
    print(stmt)
    print("Balanced:", is_balanced(stmt))
    print()

Il fonctionne par:

  1. Supprimer tout sauf les parenthèses
  2. Supprimer récursivement les paires de parenthèses les plus internes
  3. Si vous vous retrouvez avec autre chose que la chaîne vide, l'instruction n'est pas équilibrée. Sinon, ça l'est.
0
Brad Solomon 29 août 2019 à 01:24

Un peu différent.

expression = '{(){({)}}'
brackets = '[](){}'
stack  = []
balanced = False
for e in expression:
    if e in brackets and stack: # Popping from the stack if it is closing bracket
        if stack [-1] == brackets[brackets.index(e)-1]:
            stack.pop()
            balanced = True
            continue # it will go to the new iteration skipping the next if below
    if e in brackets: # Push to stack if new bracket in the expression
        stack .append(e)
        balanced = False
balanced = 'Balanced' if balanced and not stack  else 'Unbalanced'
print(balanced, stack)
0
Amit JS 19 déc. 2019 à 17:15

Ce code fonctionne bien

def matched(s):
  p_list=[]
  for i in range(0,len(s)):
    if s[i] =='(':
      p_list.append('(')
    elif s[i] ==')' :
      if not p_list:
        return False
      else:
        p_list.pop()
  if not p_list:
    return True
  else:
    return False
3
Nitheesh MN 20 août 2018 à 12:25
    #function to check if number of closing brackets is equal to the number of opening brackets
    #this function also checks if the closing bracket appears after the opening bracket
    def matched(str1):
        if str1.count(")")== str1.count("("):
            p1=str1.find("(")
            p2=str1.find(")")
            if p2 >= p1:
                str1=str1[p1+1:p2]+ str1[p2+1:]
                if str1.count(")")>0 and str1.count("(")>0:
                    matched(str1)
                return True
            else:
                return False
        else:
            return False

    matched(str1)
0
sub234 9 févr. 2019 à 07:23

L'erreur la plus flagrante que vous avez commise est:

    if l == ")":
        clo = clo  + [")"]
    else:
        return(ope, clo)  # here

En utilisant return, vous quittez la fonction lorsque le premier caractère différent de "(" ou ")" est rencontré. Une certaine indentation est également désactivée.

Un changement minimal qui permet à votre code de s'exécuter (bien qu'il ne donne pas de réponses correctes pour toutes les chaînes d'entrée possibles) est:

def matched(str):
    ope = []
    clo = []
    for i in range(0,len(str)):
        l = str[i]
        if l == "(":
            ope = ope + ["("]
        elif l == ")":
            clo = clo  + [")"]
    if len(ope)==len(clo):
        return True
    else:
        return False
5
Łukasz Rogalski 8 août 2016 à 16:21

Si "(", ")" ces deux caractères ne sont pas présents, alors nous ne voulons pas retourner vrai ou faux, juste ne retourner aucune correspondance trouvée. si la correspondance est trouvée, je vérifie simplement que le nombre de deux caractères est le même, puis retourne vrai, sinon retourne faux

def matched(str):
   count1=0
   count2=1
   for i in str:
       if i =="(":
           count1+=1:
       elif i==")":
           count2+=1:
       else:
           print "no matching found for (,)"
   if count1==count2:
        return True
   else:
        return False
1
Arjun P P 12 janv. 2018 à 13:44

Le plus simple de tous, bien que vous ayez tous fait du bien:

def wellbracketed(s):
    left=[]
    right=[]
    for i in range(0,len(s)):``
        if s[i]=='(':
            left=left+['(']
        elif s[i]==')':
            if len(left)!=0:
                right=right+[')']
        else:
            return False

    return(len(left)==len(right))
1
Leonardo Alves Machado 16 févr. 2018 à 20:40

Dans le cas où vous devez également trouver la position du premier support non compatible à partir de la gauche, vous pouvez utiliser le code ci-dessous qui couvre également certains cas de bord:

def isBalanced(expr):
    opening=set('([{')
    new=set(')]}{[(')
    match=set([ ('(',')'), ('[',']'), ('{','}') ])
    stack=[]
    stackcount=[]
    for i,char in enumerate(expr,1):
        if char not in new:
            continue
        elif char in opening:
            stack.append(char)
            stackcount.append(i)
        else:
            if len(stack)==0:
                print(i)
                return False
            lastOpen=stack.pop()
            lastindex=stackcount.pop()
            if (lastOpen, char) not in match:
                print (i)
                return False
    length=len(stack)
    if length!=0:
      elem=stackcount[0]
      print (elem)
    return length==0
string =input()
ans=isBalanced(string)
if ans==True:
    print("Success")
0
Akshitha Shetty 30 août 2017 à 19:38
foo1="()()())("  

def bracket(foo1):
    count = 0
    for i in foo1:
        if i == "(":
           count += 1
        else:
           if count==0 and i ==")":
               return False
           count -= 1

   if count == 0:
       return True
   else:
       return False

bracket(foo1)
-1
Firdauz Fanani 26 mars 2018 à 03:05

Bien que je ne propose pas de correctif à votre implémentation, je suggère une version plus propre et plus pythonique de la solution @kreld:

def check_parentheses(expr):
    s = []
    for c in expr:
        if c in '(':
            s.append(c)
        elif c in ')':
            if not len(s):
                break
            else:
                s.pop()
    else:
        return not len(s)
    return False

# test -----------------------------------------------------------------
test_expr = [')(', '(()', '())', '(', ')', '((', '))', '(()())', '(())',
             '()', '()(())']
for i, t in enumerate(test_expr, 1):
    print '%i\t%s\t%s' % (i, t, check_parentheses(t))

# output ---------------------------------------------------------------
1       )(      False
2       (()     False
3       ())     False
4       (       False
5       )       False
6       ((      False
7       ))      False
8       (()())  True
9       (())    True
10      ()      True
11      ()(())  True
-1
photonic.bean 16 déc. 2018 à 06:38

Exemple plus avancé dans lequel vous devez également vérifier la correspondance des pars entre crochets '[]' et accolades '{}'.

string = '([]{})'

def group_match(string):

    d = {
    ')':'(',
    ']':'[',
    '}':'{'
    }

    list_ = []

    for index, item in enumerate(string):
        if item in d.values():
            list_.append(item)

        elif (item in d.keys()) and (d.get(item) in list_):
            list_.pop()

    return len(list_) == 0
0
Ravil 10 oct. 2017 à 11:18
parenthesis_String = input("Enter your parenthesis string")
parenthesis_List = []
for p in parenthesis_String:
    parenthesis_List.append(p)
print(parenthesis_List)

if len(parenthesis_List)%2 != 0:
    print("Not Balanced Wrong number of input")

for p1 in parenthesis_List:
    last_parenthesis = parenthesis_List.pop()
    print(last_parenthesis)
    if (p1 == '{' and last_parenthesis == '}' or p1 == '[' and last_parenthesis == ']' or p1 == '(' and last_parenthesis == ')'):
        print("Balanced")
    else:
        print("Not balanced")
0
Ajinkya Vadane 23 mars 2019 à 10:05

Le code le plus simple de tous les temps !!

def checkpar(x):
    while len(''.join([e for e in x if e in "()"]).split('()'))>1: x=''.join(x.split('()'))
    return not x
0
whackamadoodle3000 17 févr. 2018 à 06:38

Ma solution fonctionne ici pour les supports, parenthèses et accolades

openList = ["[","{","("]
closeList = ["]","}",")"]
def balance(myStr):
    stack= []
    for i in myStr:
        if i in openList:
            stack.append(i)
        elif i in closeList:
            pos = closeList.index(i)
            if ((len(stack) > 0) and (openList[pos] == stack[len(stack)-1])):
                stack.pop()
            else:
                return "Unbalanced"
    if len(stack) == 0:
        return "Balanced"
print balance("{[()](){}}") 
4
Kavitha Madhavaraj 12 oct. 2017 à 11:34
input_str = "{[()](){}}"
strblance=""

for i in input_str:

    if not strblance:
        strblance = strblance+i
    elif (i is '}' and strblance[len(strblance)-1] is '{') \
        or ( i is']'and strblance[len(strblance)-1] is '[') \
        or ( i is ')'and strblance[len(strblance)-1] is '('):
            strblance = strblance[:len(strblance)-1]
    else:
        strblance = strblance+i

if not strblance:

    print ("balanced")

else:

    print ("Not balanced")
0
moggi 19 sept. 2017 à 11:37

Vous pouvez vérifier ce code.
Ce code n'utilise pas les opérations de pile.

def matched(s):
  count = 0
  for i in s:
    if i is "(":
      count += 1
    elif i is ")":
      if count != 0:
        count -= 1
      else:
        return (False)

  if count == 0:
    return (True)
  else:
    return (False)
0
Abhishek Kumar 18 août 2018 à 12:47