Progtwig Python para verificar la coincidencia de paréntesis simples

Soy un novato de Python y me encontré con este ejercicio de verificar si los corchetes simples “(“, “)” en una cadena dada coinciden o no.

He visto ejemplos aquí utilizando el comando de stack que no he encontrado todavía. Así que intenté un enfoque diferente. ¿Alguien puede decirme a dónde me voy mal?

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 

La idea es acumular “(” y “)” en dos listas separadas y luego comparar la longitud de las listas. También tuve otra versión donde adjunté las listas ope y clo con la i relevante que contenía (o) respectivamente.

¡Gracias por tu tiempo!

A continuación se muestra una forma muy elegante de hacerlo. Limpia el bucle for y reemplaza las listas con una simple variable de contador. También devuelve falso si el contador cae por debajo de cero para que matched(")(") devuelva 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 

Esto verifica si los paréntesis se corresponden correctamente, no solo si hay un número igual de paréntesis de apertura y cierre. Usamos una list como una stack y presionamos sobre ella cuando encontramos paréntesis de apertura y salimos de ella cuando encontramos paréntesis de cierre.

El principal problema con su solución es que solo cuenta el número de paréntesis pero no los corresponde . Una forma de mantener un registro de la profundidad actual del anidamiento es empujando los paréntesis de apertura en una stack y sacándolos de la stack cuando nos encontramos con un paréntesis de cierre.

 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 

El error más flagrante hecho por usted es:

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

Al utilizar return, se sale de la función cuando se encuentra el primer carácter que no es igual a “(” o “)”. También alguna sangría está desactivada.

El cambio mínimo que permite que su código se ejecute (aunque no dará las respuestas correctas para todas las cadenas de entrada posibles) es:

 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 

Mi solución aquí funciona para paréntesis, paréntesis y llaves

 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("{[()](){}}") 

este código funciona 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 

El problema con su enfoque es que no considera el orden. La siguiente línea pasaría:) ))) ((( sugeriría mantener el recuento de paréntesis abierto y cerrado:

  • counter comienza desde 0
  • cada ( contador de incremento de símbolo
  • cada ) símbolo disminuye el contador
  • Si en cualquier momento el contador es negativo es un error.
  • si al final de la línea el contador es 0 – la cadena tiene paréntesis coincidente
 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)) 

Si “(“, “)” estos dos caracteres no están presentes, entonces no queremos devolver verdadero o falso, solo devolvemos ninguna coincidencia encontrada. si se encuentra una coincidencia, solo compruebo que el recuento de los dos caracteres es el mismo, luego devuelve verdadero, de lo contrario, devuelve falso

 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 

Lo más simple de todo, aunque todos ustedes lo han hecho 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)) 

Aquí hay otra forma de resolverlo con un contador que rastrea cuántos paréntesis abiertos son la diferencia en este momento. Esto debería hacerse cargo de todos los casos.

 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 

si la secuencia de paréntesis no es un problema (cadenas como )( ) este código es más rápido:

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

Probado con una cadena de 15 KB, es de ~ 20μs frente a 1 ms en iteración sobre toda la cadena.

Y para mí, el orden no es un problema, ya que el protocolo subyacente garantiza que la cadena está bien formada.

En caso de que también necesite encontrar la posición del primer soporte que no coincida con la izquierda, puede usar el siguiente código que también cubre ciertos casos de borde:

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

Un ejemplo más avanzado en el que adicionalmente necesita verificar la coincidencia de los corchetes ‘[]’ y los paréntesis ‘{}’.

 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 

El código más simple de todos!

 def checkpar(x): while len(''.join([e for e in x if e in "()"]).split('()'))>1: x=''.join(x.split('()')) return not x 

Es posible que desee probar esto:

 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 
 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 == [] 

Puedes consultar este código.
Este código no utiliza operaciones de stack.

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

Puede hacer esto en una línea usando acumular (de itertools). La idea es calcular un nivel de paréntesis acumulativo pasando por la cadena con paréntesis de apertura contando como nivel + 1 y paréntesis de cierre como nivel-1. Si, en cualquier punto, el nivel acumulado cae por debajo de cero, entonces hay una falta de coincidencia:

 from itertools import accumulate def matched(s): return not any( level < 0 for level in accumulate((c=="(")-(c==")") for c in s)) 
 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) 

Aunque no estoy proponiendo una solución para su implementación, sugiero una versión más limpia y más python de la solución @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