[pyar] [OT] - Checkeando parentesis balanceados.
Mariano Garcia Berrotarán
el otro dia charlando con un compañero de trabajo, me contó que un
ejercicio que toma en entrevistas, es el siguiente:
escribir una función la cual recibe una cadena conformada unicamente
por parentesis abiertos y cerrados.
la funcion tiene que retornar un booleano representando si los
parentesis estan balanceados o no.
balanceados significa: todo parentesis que abre, corresponde a uno que cierra.
casos validos: (()), (), ()(), ((())), ((()())) ...
casos invalidos: )()), ((()) )( ...
despues de jugar un rato yo lo resolví de esta forma:
mi pregunta es la siguiente:
a alguien se le ocurre alguna forma de hacerlo usando list comprehension ?
alguna forma chiflada de hacerlo?
aca les dejo los unit tests para probarlo si quieren.
Saludos!
_______________________________________________
pyar mailing list py...@python.org.ar
http://listas.python.org.ar/listinfo/pyar
PyAr - Python Argentina - Sitio web: http://www.python.org.ar/
Juan BC
con un stack se hacia eso si mal no recuerdo
Daniel Moisset
Juanjo Conti
Si es (: lo metes en la pila
Si es ): sacas uno de la pila
Si el segundo paso da error por que no hay nada en la pila, entonces estån desbalanceados.
Era asi? Trate de recordarlo rapido.
Salutes!
--
Juanjo Conti
blog: http://www.juanjoconti.com.ar
Alejandro Santos
> Si, la forma clasica es con una pila. Vas leyendo los tokens de a uno:
>
> Si es (: lo metes en la pila
> Si es ): sacas uno de la pila
>
> Si el segundo paso da error por que no hay nada en la pila, entonces estån
> desbalanceados.
>
> Era asi? Trate de recordarlo rapido.
>
Sip, y por ultimo verificar que la pila este vacia.
--
Alejandro Santos
http://www.alejandrosantos.com.ar
Marcelo Rinesi
con un acumulador al que le sumás 1 cuando ves ( y restás uno cuando
ves )?. La condición de éxito sería que el acumulador nunca sea
negativo, y que al final de la función sea cero.
2010/6/18 Alejandro Santos <lis...@alejolp.com>:
Matigro
<garcia.b...@gmail.com> escribió:
> balanceados significa: todo parentesis que abre, corresponde a uno que cierra.
>>> def balanceau(cadena):
... cont = 0
... for c in cadena:
... if c == "(":
... cont += 1
... elif c == ")":
... cont -= 1
... return(cont == 0)
>>> balanceau(cadena)
0: False
>>> cadena = "()"
>>> print balanceau(cadena)
True
>>> cadena = """def hola():
... print("hola, como te va"
... """
>>> print balanceau(cadena)
False
>>> cadena = """def hola():
... print("hola, como te va)"
... """
>>> print balanceau(cadena)
True
--
http://www.linkedin.com/in/matigro
david weil
> balanceados significa: todo parentesis que abre, corresponde a uno que cierra.
¿Nadie lee acá que esto: ) ( sería valido?
--
There is no dark side of the moon really. Matter of fact it's all dark.
Alejandro Santos
> En este caso particular, creo que la pila es demasiado. ¿No alcanza
> con un acumulador al que le sumás 1 cuando ves ( y restás uno cuando
> ves )?. La condición de éxito sería que el acumulador nunca sea
> negativo, y que al final de la función sea cero.
>
En ese caso ")(" daria True, y eso no esta bien
Matigro
<marcelo...@gmail.com> escribió:
> En este caso particular, creo que la pila es demasiado. ¿No alcanza
> con un acumulador al que le sumás 1 cuando ves ( y restás uno cuando
> ves )?. La condición de éxito sería que el acumulador nunca sea
> negativo, y que al final de la función sea cero.
jeje, es el ejemplo que posteé recien. :)
--
http://www.linkedin.com/in/matigro
Jesús Francisco
> 2010/6/18 Mariano Garcia Berrotarán <garcia.b...@gmail.com>:
>
>> balanceados significa: todo parentesis que abre, corresponde a uno que cierra.
>
> ¿Nadie lee acá que esto: ) ( sería valido?
>
Y la solución sumando restando 1 da 0 en ese caso.
Marcelo Rinesi
> 2010/6/18 Marcelo Rinesi <marcelo...@gmail.com>:
>> En este caso particular, creo que la pila es demasiado. ¿No alcanza
>> con un acumulador al que le sumás 1 cuando ves ( y restás uno cuando
>> ves )?. La condición de éxito sería que el acumulador nunca sea
>> negativo, y que al final de la función sea cero.
>>
>
> En ese caso ")(" daria True, y eso no esta bien
Después de procesar el primer caracter el acumulador es -1, y eso
viola la primera parte de la condición :).
Alejandro Santos
> 2010/6/18 Marcelo Rinesi <marcelo...@gmail.com>:
>> En este caso particular, creo que la pila es demasiado. ¿No alcanza
>> con un acumulador al que le sumás 1 cuando ves ( y restás uno cuando
>> ves )?. La condición de éxito sería que el acumulador nunca sea
>> negativo, y que al final de la función sea cero.
>>
>
> En ese caso ")(" daria True, y eso no esta bien
>
No perdon, dije una huevada!!
()(()())
Eh.. si?
Juan BC
> 2010/6/18 Juanjo Conti<jjc...@gmail.com>:
>> Si, la forma clasica es con una pila. Vas leyendo los tokens de a uno:
>>
>> Si es (: lo metes en la pila
>> Si es ): sacas uno de la pila
>>
>> Si el segundo paso da error por que no hay nada en la pila, entonces estån
>> desbalanceados.
>>
>> Era asi? Trate de recordarlo rapido.
>>
>
> Sip, y por ultimo verificar que la pila este vacia.
>
si = "((())()())"
no= ")()()(())"
def balanceado(string):
stack = []
for c in string:
if c == ")" and stack and stack[-1] == "(":
stack.pop()
else:
stack.append(c)
return not len(stack)
print si, balanceado(si)
print no, balanceado(no)
Alejandro Santos
> El día 18 de junio de 2010 13:24, Mariano Garcia Berrotarán
> <garcia.b...@gmail.com> escribió:
>> balanceados significa: todo parentesis que abre, corresponde a uno que cierra.
>>>> cadena = "((()()())()))()()()))))((())))"
>
>>>> def balanceau(cadena):
> ... cont = 0
> ... for c in cadena:
> ... if c == "(":
> ... cont += 1
> ... elif c == ")":
> ... cont -= 1
> ... return(cont == 0)
Aca falla:
print balanceau(")(")
--
Alejandro Santos
http://www.alejandrosantos.com.ar
Ale
En este caso particular, creo que la pila es demasiado. ¿No alcanza
con un acumulador al que le sumás 1 cuando ves ( y restás uno cuando
ves )?. La condición de éxito sería que el acumulador nunca sea
negativo, y que al final de la función sea cero.
puede ser, pero que pasa con ")()(" ? Eso daría 0.
2010/6/18 Alejandro Santos <lis...@alejolp.com>:
> 2010/6/18 Juanjo Conti <jjc...@gmail.com>:
>> Si, la forma clasica es con una pila. Vas leyendo los tokens de a uno:
>>
>> Si es (: lo metes en la pila
>> Si es ): sacas uno de la pila
>>
>> Si el segundo paso da error por que no hay nada en la pila, entonces estån
>> desbalanceados.
>>
>> Era asi? Trate de recordarlo rapido.
>>
>
> Sip, y por ultimo verificar que la pila este vacia.
>
> --
> Alejandro Santos
> http://www.alejandrosantos.com.ar
> _______________________________________________
> pyar mailing list py...@python.org.ar
> http://listas.python.org.ar/listinfo/pyar
>
> PyAr - Python Argentina - Sitio web: http://www.python.org.ar/
>
_______________________________________________
pyar mailing list py...@python.org.ar
http://listas.python.org.ar/listinfo/pyar
PyAr - Python Argentina - Sitio web: http://www.python.org.ar/
--
Ale.
Jesús Francisco
> El día 18 de junio de 2010 13:24, Mariano Garcia Berrotarán
> <garcia.b...@gmail.com> escribió:
>> balanceados significa: todo parentesis que abre, corresponde a uno que cierra.
>>>> cadena = "((()()())()))()()()))))((())))"
>
>>>> def balanceau(cadena):
> ... cont = 0
> ... for c in cadena:
> ... if c == "(":
> ... cont += 1
> ... elif c == ")":
> ... cont -= 1
... return False
Juan BC
> print balanceau(")(")
el mio funca
si = "((())()())"
no= ")()()(())"
def balanceado(string):
stack = []
for c in string:
if c == ")" and stack and stack[-1] == "(":
stack.pop()
else:
stack.append(c)
return not len(stack)
print si, balanceado(si)
print no, balanceado(no)
print ")(", balanceado(")(")
Marcelo Rinesi
> El 18 de junio de 2010 13:38, Marcelo Rinesi <marcelo...@gmail.com>
> escribió:
>>
>> En este caso particular, creo que la pila es demasiado. ¿No alcanza
>> con un acumulador al que le sumás 1 cuando ves ( y restás uno cuando
>> ves )?. La condición de éxito sería que el acumulador nunca sea
>> negativo, y que al final de la función sea cero.
>>
>
> puede ser, pero que pasa con ")()(" ? Eso daría 0.
>
Por eso dije "que el acumulador nunca sea negativo." La secuencia va a ser
. Se inicializa el acumulador en cero
. Lee el primer caracter del input: ")"
. Como es ), resta uno al acumulador, que queda en -1.
. Como -1 es negativo, salta la condición, y reporta que no está balanceado.
No importa que la suma de cero; de hecho, el algoritmo nunca procesa
más allá del primer caracter.
Roberto Alsina
> a alguien se le ocurre alguna forma de hacerlo usando list comprehension ?
>
> alguna forma chiflada de hacerlo?
No sé si chiflada, pero...
Lo primero es poner los parentesis en forma numérica:
>>> s="()"
>>> t="()()"
>>> [(-1)**s.find(c) for c in t]
[1, -1, 1, -1]
Lo siguiente es decidir cuando falla:
1) Cuando la suma no es 0
2) Cuando la suma incremental se vuelve negativa en algún momento
O sea, balanceado sería algo como
def balanceado(t):
t1=[(-1)**s.find(c) for c in t]
if any (map (lambda x: x<0, [sum (t1[:i]) for i in range(len(t1))])) or
t1[-1]:
return False
return True
No lo probé mucho pero debería andar....
Roberto Alsina
> def balanceado(t):
> t1=[(-1)**s.find(c) for c in t]
> if any (map (lambda x: x<0, [sum (t1[:i]) for i in
> range(len(t1))])) or t1[-1]:
> return False
> return True
Podría hacer un
lambda balanceado t: return not (any (map (lambda x: x<0, [sum (t1[:i]) for i
in range(len(t1))])) or t1[-1])
pero me pareció demasiado horrible ;-)
Roberto Alsina
> On Friday 18 June 2010 13:53:45 Roberto Alsina wrote:
> > def balanceado(t):
> > t1=[(-1)**s.find(c) for c in t]
> > if any (map (lambda x: x<0, [sum (t1[:i]) for i in
> >
> > range(len(t1))])) or t1[-1]:
> > return False
> > return True
>
> Podría hacer un
>
> lambda balanceado t: return not (any (map (lambda x: x<0, [sum (t1[:i]) for
> i in range(len(t1))])) or t1[-1])
>
> pero me pareció demasiado horrible ;-)
Y ni siquiera es SUFICIENTEMENTE horrible porque me dejé media función afuera.
No veo como hacerlo one-liner, sería algo como
def balanceado (t):
t1=[(-1)**"()".find(c) for c in t]
return not (any (map (lambda x: x<0, [sum (t1[:i])\
for i in range(len(t1))])) or t1[-1])
_______________________________________________
Claudio Freire
2010/6/18 Juanjo Conti <jjc...@gmail.com>:
> Si, la forma clasica es con una pila. Vas leyendo los tokens de a uno:Sip, y por ultimo verificar que la pila este vacia.
>
> Si es (: lo metes en la pila
> Si es ): sacas uno de la pila
>
> Si el segundo paso da error por que no hay nada en la pila, entonces estån
> desbalanceados.
>
> Era asi? Trate de recordarlo rapido.
>
Versión con numpy:
>>>
>>> lines = [
... "(hola(chau))",
... "((",
... "()",
... "()()()",
... "((()(())()))",
... "((()(())())))",
... "(((()(())()))",
... ]
>>>
>>> for line in lines:
... if line:
... nline = numpy.ndarray((len(line),), dtype=numpy.uint8, buffer=line)
... nline = numpy.add.accumulate(nline == ord('(')) - numpy.add.accumulate(nline == ord(')'))
... if numpy.any(nline < 0):
... print "Parentesis desbalanceados en", line,
... print "parentesis extra en posicion", numpy.min((nline < 0).nonzero()) + 1
... elif nline[-1] > 0:
... print "Parentesis desbalanceados en", line,
... print "faltan cerrar", nline[-1], "parentesis"
...
Parentesis desbalanceados en (( faltan cerrar 2 parentesis
Parentesis desbalanceados en ((()(())()))) parentesis extra en posicion 13
Parentesis desbalanceados en (((()(())())) faltan cerrar 1 parentesis
>>>
Matigro
<lis...@alejolp.com> escribió:
>>>>> def balanceau(cadena):
>> ... cont = 0
>> ... for c in cadena:
>> ... if c == "(":
>> ... cont += 1
>> ... elif c == ")":
>> ... cont -= 1
>> ... return(cont == 0)
>
> Aca falla:
>
> print balanceau(")(")
Querían velocidad o precisión en la respuesta? :P
Dejamos a los que hacen la entrevista tener en cuenta ese pequeño 'detalle'.
Y para discutir y no obtener el trabajo le diría, ud pidió que:
"Escribir una función la cual recibe una cadena conformada unicamente
por parentesis abiertos y cerrados. la funcion tiene que retornar un
booleano representando si los parentesis estan balanceados o no."
La cadena está balanceada, tengo la misma cantidad de paréntesis de
abrir que de cerrar, no sirve para la sintaxis del castellano ni para
un lenguaje de programación reconocido, pero eso no dice en el
enunciado.
Por lo que, señor mío, aunque en mi documento aparezca otro apellido,
a mi me dicen Zapata, si no la gana...
Será hasta luego, espero que me llame.
Agarro mi lápiz, la campera y me voy :D
--
http://www.linkedin.com/in/matigro
Daniel Moisset
>
> a alguien se le ocurre alguna forma de hacerlo usando list comprehension ?
Si es obligatorio usar una comprehension te diria algo con esta idea...
def balanceado(s):
profundidades = [s[:index+1].count("(")-s[:index+1].count(")") for
index in xrange(len(s)) ]
return (not s) or (all(p>=0 for p in profundidades) and profundidades[-1]=0)
[escribi el codigo en el mail, ando con fiaca de testear. capaz no
compila/corre/anda]
igual todo lo que se me ocurre con comprensiones es cuadratico, se puede lineal
Saludos,
D.
Alejandro Santos
> No veo como hacerlo one-liner, sería algo como
>
One liner:
def parentesis4(data):
return 0 == reduce(lambda a, b: a < 0 and (-2*len(data)) or a + b,
[x == '(' and 1 or -1 for x in data], 0)
Otras tres alternativas más:
--
Alejandro Santos
http://www.alejandrosantos.com.ar
Claudio Freire
2010/6/18 Mariano Garcia Berrotarán <garcia.b...@gmail.com>:
> mi pregunta es la siguiente:Si es obligatorio usar una comprehension te diria algo con esta idea...
>
> a alguien se le ocurre alguna forma de hacerlo usando list comprehension ?
La idea numpy es "tipo list comprehension".
Si se quiere puro list comprehension, se puede seguir una idea similar:
>>> def balanceado(s):
... cum = 0
... for balance in [ cum for c in s for cum in [cum + int(c=='(') - int(c==')')] ]:
... if balance < 0:
... return False
... return balance == 0
...
>>>
>>>
... lines = [
... "(hola(chau))",
... "((",
... "()",
... "()()()",
... "((()(())()))",
... "((()(())())))",
... "(((()(())()))",
... ]
>>>
>>> for line in lines:
... print "balanceado:", line
... else:
... print "desbalanceado:", line
...
balanceado: (hola(chau))
desbalanceado: ((
balanceado: ()
balanceado: ()()()
balanceado: ((()(())()))
desbalanceado: ((()(())())))
desbalanceado: (((()(())()))
>>>
Sebastian Bassi
> parentesis estan balanceados o no.
Mi versión es facil de entender y pasa tus tests:
import unittest
class balanceTestCase(unittest.TestCase):
def testSimple(self):
self.assertEquals(balance("()"), True)
def testOnion(self):
self.assertEquals(balance("(((((())))))"), True)
def testInverted(self):
self.assertEquals(balance(")("), False)
def testBroken(self):
self.assertEquals(balance("())(()"), False)
def balance(s):
cont = 0
for x in s:
if cont<0:
return False
else:
cont = cont-1 if x == ')' else cont+1
return True if cont == 0 else False
suite = unittest.TestLoader().loadTestsFromTestCase(balanceTestCase)
unittest.TextTestRunner(verbosity=2).run(suite)
Sebastian Bassi
> La cadena está balanceada, tengo la misma cantidad de paréntesis de
> abrir que de cerrar, no sirve para la sintaxis del castellano ni para
> un lenguaje de programación reconocido, pero eso no dice en el
> enunciado.
Si yo te estuviera evaluando pondria en mi hoja:
Desempeño técnico: A+
Actitud para trabajo en equipo: D
Espera tranquilo que te llame :)
Mariano Guerra
> 2010/6/18 Mariano Garcia Berrotarán <garcia.b...@gmail.com>:
>> la funcion tiene que retornar un booleano representando si los
>> parentesis estan balanceados o no.
>
> Mi versión es facil de entender y pasa tus tests:
[snip]
Mi version es *mas* facil de entender y pasa sus tests:
import unittest
class balanceTestCase(unittest.TestCase):
def testSimple(self):
self.assertEquals(balance("()"), True)
def testOnion(self):
self.assertEquals(balance("(((((())))))"), True)
def testInverted(self):
self.assertEquals(balance(")("), False)
def testBroken(self):
self.assertEquals(balance("())(()"), False)
def balance(s):
if s in ["()", "(((((())))))"]:
return True
return False
suite = unittest.TestLoader().loadTestsFromTestCase(balanceTestCase)
unittest.TextTestRunner(verbosity=2).run(suite)
PD: si actualizan los unittests avisenme que tengo que hacerle unas
modificaciones ;)
Lucio Torre
> Mi versión es facil de entender y pasa tus tests:
> cont = 0
> for x in s:
> if cont<0:
> return False
> else:
> cont = cont-1 if x == ')' else cont+1
> return True if cont == 0 else False
Definitivamente creo que tiene que ser una cosa asi la solucion si la
vas a presentar en el ejecicio.
Si elijiese ponerme quisquilloso no lo haria un viernes y tampoco
haria estos comentarios:
- la llamaria "es_balanceado" o algo asi, que indique que devuelve un bool
- cont, s, y x los llamaria: abiertos, expresion y c
- "return True if cont == 0 else False" == "return (cont == 0)" (los
parentesis son por gusto)
- la construccion del suite la dejaria de lado y usaria nosetests
- el if oneliner lo expandiria a varias lineas y haria nada si el
caracter no es "(" o ")" (no esta especificado que hacer si hay otros
caracteres en el string. Yo propongo ignorarlos y dar un resultado
correcto igual a la cuenta de parentesis. La otra opcion es tirar una
excepcion. Dar un resultado errado no deberia ser opcion)
- Ya que estamos, el "else" del "if cont<0:" lo evitaria, el claro que
es una salida rapida de la funcion con el return ahi. me evito una
indentacion y pensar al respecto de eso.
Bueno, no se porque me la agarre con vos, en realidad queria decir que
para algo tan tonto como este ejercicio me preocupa mas como hacer
algo legible y de clara intencion que oneliner (no que oneliners no
sean divertidos, pero hoy me pego por aca)
Lucio.
Martin Cerdeira
Hola listeros:
el otro dia charlando con un compañero de trabajo, me contó que un
ejercicio que toma en entrevistas, es el siguiente:
escribir una función la cual recibe una cadena conformada unicamente
por parentesis abiertos y cerrados.
la funcion tiene que retornar un booleano representando si los
parentesis estan balanceados o no.
balanceados significa: todo parentesis que abre, corresponde a uno que cierra.
casos validos: (()), (), ()(), ((())), ((()())) ...
casos invalidos: )()), ((()) )( ...
despues de jugar un rato yo lo resolví de esta forma:
http://pastebin.com/5BHcxbDC
mi pregunta es la siguiente:
a alguien se le ocurre alguna forma de hacerlo usando list comprehension ?
alguna forma chiflada de hacerlo?
aca les dejo los unit tests para probarlo si quieren.
http://pastebin.com/7En3UzBk
Saludos!
Si el string empieza con ")" o termina con "(" [no importa que haya en el medio], ya estaría mal, no??
Si es así, y si no me falla el debugger cerebral, podrías chequear eso primero, y luego, usar el acumulador 1 / -1
Capaz estoy en pedo, así en el aire, me sonó bien. Corrijanme.
Mariano Garcia Berrotarán
> Si el string empieza con ")" o termina con "(" [no importa que haya en el
> medio], ya estaría mal, no??
sisi, son invalidos.
Sebastian Bassi
> - la llamaria "es_balanceado" o algo asi, que indique que devuelve un bool
Usé el nombre que venia, pero es buena la sugerencia.
> - cont, s, y x los llamaria: abiertos, expresion y c
ok
> - "return True if cont == 0 else False" == "return (cont == 0)" (los
> parentesis son por gusto)
Si, siempre aclaran para mi.
> - el if oneliner lo expandiria a varias lineas y haria nada si el
> caracter no es "(" o ")" (no esta especificado que hacer si hay otros
> caracteres en el string. Yo propongo ignorarlos y dar un resultado
> correcto igual a la cuenta de parentesis. La otra opcion es tirar una
> excepcion. Dar un resultado errado no deberia ser opcion)
Ojo que el enunciado presupone que hay solo parentesis:
"recibe una cadena conformada unicamente por parentesis abiertos y cerrados."
y actue en consecuencia, suponiendo que ya pasó por un filtro.
> - Ya que estamos, el "else" del "if cont<0:" lo evitaria, el claro que
> es una salida rapida de la funcion con el return ahi. me evito una
> indentacion y pensar al respecto de eso.
Si, totalmente al pedo pensando en la función (porque como decis puede
salir por el return) pero me parece bueno por una cuestión de mostrar
la lógica del programa.
Saludos,
SB.
Lucio Torre
>> - el if oneliner lo expandiria a varias lineas y haria nada si el
>> caracter no es "(" o ")" (no esta especificado que hacer si hay otros
>> caracteres en el string. Yo propongo ignorarlos y dar un resultado
>> correcto igual a la cuenta de parentesis. La otra opcion es tirar una
>> excepcion. Dar un resultado errado no deberia ser opcion)
>
> Ojo que el enunciado presupone que hay solo parentesis:
> "recibe una cadena conformada unicamente por parentesis abiertos y cerrados."
> y actue en consecuencia, suponiendo que ya pasó por un filtro.
Ok, pero el comportamiento que recibis cuando el input esta fuera de
lo supuesto es importante.
Las opciones son fallar o responder algo correcto bajo alguna
interpretacion mas amplia.
Responder algo que parezca que todo funciono pero que no haga sentido
bajo ninguna interpretacion es bastante malo.
A no ser que quieras una D en trabajo de equipo, obvio ;)
Lucio.
Martin Cerdeira
Si el string empieza con ")" o termina con "(" [no importa que haya en el medio], ya estaría mal, no??
Si es así, y si no me falla el debugger cerebral, podrías chequear eso primero, y luego, usar el acumulador 1 / -1
Capaz estoy en pedo, así en el aire, me sonó bien. Corrijanme.
-------------------------------------
Martín Cerdeira - Software Developer
[email] martinc...@gmail.com
[web] http://www.codmacs.blogspot.com/
Martin Cerdeira
Mi function era algo así:
Funcion CuentaPa(c) Boolean
k Integer
i Integer
If PrimerChar = ")" Or UltimoChar = "(" Then
CuentaPa = False
Exit
End If
For i = 0 To Largo(c)
If CurrentChar()= "(" Then
k = k + 1
Else
k = k - 1
End If
Next i
CuentaPa = (k = 0)
End
Claudio Freire
2010/6/18 Sebastian Bassi <sba...@clubdelarazon.org>:
> 2010/6/18 Mariano Garcia Berrotarán <garcia.b...@gmail.com>:[snip]
>> la funcion tiene que retornar un booleano representando si los
>> parentesis estan balanceados o no.
>
> Mi versión es facil de entender y pasa tus tests:
Mi version es *mas* facil de entender y pasa sus tests:
Mi versión es **más más** fácil de entender:
>>> def balanceado(s):
... try:
... return eval(s.replace('()','(True)'))
... except:
... return False
...
>>> balanceado('()')
True
>>> balanceado('(())')
True
>>> balanceado('(()))')
False
>>>
:-p
Tordek
def balance(s):
cont = 0
for x in s:
if cont<0:
return False
else:
cont = cont-1 if x == ')' else cont+1
return True if cont == 0 else False
Roberto Alsina
Má mejor:
def balanceado(s):
while s != s.replace('()',''): s=s.replace('()','')
return not s
Daniel Moisset
>
> Mi function era algo así:
>
> Funcion CuentaPa(c) Boolean
> k Integer
> i Integer
> If PrimerChar = ")" Or UltimoChar = "(" Then
> CuentaPa = False
> Exit
> End If
> For i = 0 To Largo(c)
> If CurrentChar()= "(" Then
> k = k + 1
> Else
> k = k - 1
> End If
> Next i
> CuentaPa = (k = 0)
> End
Pero no anda con "())(()"
D.
Daniel Moisset
> Má mejor:
>
> def balanceado(s):
> while s != s.replace('()',''): s=s.replace('()','')
> return not s
Oscar al mejor O(N^2) camuflado.
Martin Cerdeira
2010/6/18 Martin Cerdeira <martinc...@gmail.com>:
>
> Mi function era algo así:
>
> Funcion CuentaPa(c) Boolean
> k Integer
> i Integer
> If PrimerChar = ")" Or UltimoChar = "(" Then
> CuentaPa = False
> Exit
> End If
> For i = 0 To Largo(c)
> If CurrentChar()= "(" Then
> k = k + 1
> Else
> k = k - 1
> End If
> Next i
> CuentaPa = (k = 0)
> End
Pero no anda con "())(()"
D.
Roberto Alsina
> 2010/6/18 Roberto Alsina <ral...@netmanagers.com.ar>:
> > Má mejor:
> >
> > def balanceado(s):
> > while s != s.replace('()',''): s=s.replace('()','')
> > return not s
>
> Oscar al mejor O(N^2) camuflado.
Pero no me vas a decir que no es linda, sin contadores, sin pilas, sin dos
ifs... :-)
Roberto Alsina
> > Má mejor:
> >
> > def balanceado(s):
> > while s != s.replace('()',''): s=s.replace('()','')
> > return not s
>
> Oscar al mejor O(N^2) camuflado.
Aparte no es N^2 de la longitud de la cadena!
Es N^2 del nivel de anidamiento de los paréntesis!
Para cadenas larguísimas con parentesis sin anidar es recontra eficiente :-)
Daniel Moisset
<ral...@netmanagers.com.ar> wrote:
> On Friday 18 June 2010 16:25:57 Daniel Moisset wrote:
>> 2010/6/18 Roberto Alsina <ral...@netmanagers.com.ar>:
>> > Má mejor:
>> >
>> > def balanceado(s):
>> > while s != s.replace('()',''): s=s.replace('()','')
>> > return not s
>>
>> Oscar al mejor O(N^2) camuflado.
>
> Aparte no es N^2 de la longitud de la cadena!
>
> Es N^2 del nivel de anidamiento de los paréntesis!
En realidad es NM, con N la longitud de la cadena, y M la profundidad
de anidamiento.
Saludos,
D.
John Rowland Lenton
> Hola listeros:
>
> el otro dia charlando con un compañero de trabajo, me contó que un
> ejercicio que toma en entrevistas, es el siguiente:
>
> por parentesis abiertos y cerrados.
> parentesis estan balanceados o no.
>
>
> casos validos: (()), (), ()(), ((())), ((()())) ...
> casos invalidos: )()), ((()) )( ...
>
> despues de jugar un rato yo lo resolví de esta forma:
>
> http://pastebin.com/5BHcxbDC
>
> mi pregunta es la siguiente:
>
> a alguien se le ocurre alguna forma de hacerlo usando list comprehension ?
>
> alguna forma chiflada de hacerlo?
>
>
> aca les dejo los unit tests para probarlo si quieren.
>
> http://pastebin.com/7En3UzBk
que tal así:
def balanceados(caso):
try:
re.compile(caso)
except re.error:
return False
else:
return True
Hystrix
>
> Má mejor:
>
> def balanceado(s):
> while s != s.replace('()',''): s=s.replace('()','')
> return not s
La mas linda por lejos, sin duda.
--
Hystrix
Roberto Alsina
> que tal así:
>
> def balanceados(caso):
> try:
> re.compile(caso)
> except re.error:
> return False
> else:
> return True
No necesitás re:
def balanceado(caso):
try:
eval(caso)
return True
except SyntaxError:
return False
John Rowland Lenton
> On Friday 18 June 2010 17:29:27 John Rowland Lenton wrote:
> > que tal así:
> >
> > def balanceados(caso):
> > try:
> > re.compile(caso)
> > except re.error:
> > return False
> > else:
> > return True
>
> No necesitás re:
>
> def balanceado(caso):
> try:
> eval(caso)
> return True
> except SyntaxError:
> return False
eso falla con "()()", que entendí que estaba bien.
Además,
$ python -m timeit -s 'from q import f_eval, f_re' 'f_eval("(())")'
100000 loops, best of 3: 8.9 usec per loop
$ python -m timeit -s 'from q import f_eval, f_re' 'f_re("(())")'
100000 loops, best of 3: 1.24 usec per loop
además además,
$ python -m timeit -s 'from q import f_eval, f_re' 'f_re("("*100 + ")"*100)'
1000 loops, best of 3: 1.72 msec per loop
$ python -m timeit -s 'from q import f_eval, f_re' 'f_eval("("*100 + ")"*100)'
s_push: parser stack overflow
s_push: parser stack overflow
s_push: parser stack overflow
s_push: parser stack overflow
s_push: parser stack overflow
s_push: parser stack overflow
s_push: parser stack overflow
s_push: parser stack overflow
s_push: parser stack overflow
s_push: parser stack overflow
[snip]
y tomá mate.
Claudio Freire
¿por qué se está pareciendo a una competencia sobre intérpretes de brainfuck?
Hm....
Roberto Alsina
> y tomá mate.
tení razón, me tomo uno :-)
Claudio Freire
On Fri, Jun 18, 2010 at 06:54:03PM -0300, Claudio Freire wrote:
Definitivamente.
Aunque capaz que 2L está más al alcance.
Roberto Alsina
> ")"*100)' 1000 loops, best of 3: 1.72 msec per loop
> $ python -m timeit -s 'from q import f_eval, f_re' 'f_eval("("*100 +
> ")"*100)'
Si, pero re.compile falla a los 101, vivaracho :-D
>>> re.compile('()'*101)
Traceback (most recent call last):
File "<stdin>", line 1, in <module>
File "/usr/lib/python2.6/re.py", line 190, in compile
return _compile(pattern, flags)
File "/usr/lib/python2.6/re.py", line 243, in _compile
p = sre_compile.compile(pattern, flags)
File "/usr/lib/python2.6/sre_compile.py", line 517, in compile
"sorry, but this version only supports 100 named groups"
AssertionError: sorry, but this version only supports 100 named groups
Tordek
Definitivamente.
Aunque capaz que 2L está más al alcance.
Roberto Alsina
> Not enough information to check signature validity. Show Details
Aguantame un cachito que te lo implemento en FLIP (y para que no sea OT, ra-
flip está implementado en python ;-)
Flip en acción:
http://dl.dropbox.com/u/840438/flip.ogg
El intérprete:
http://code.google.com/p/ra-flip/
La explicación:
http://lateral.netmanagers.com.ar/weblog/posts/BB561.html
Todavia no puedo creer que este sea el unico lenguaje que traté de implementar
que funciona :-(
John Rowland Lenton
> On Friday 18 June 2010 18:49:15 John Rowland Lenton wrote:
> > $ python -m timeit -s 'from q import f_eval, f_re' 'f_re("("*100 +
> > ")"*100)' 1000 loops, best of 3: 1.72 msec per loop
> > $ python -m timeit -s 'from q import f_eval, f_re' 'f_eval("("*100 +
> > ")"*100)'
>
> Si, pero re.compile falla a los 101, vivaracho :-D
hacele .replace("(", "(?:") entonces :)
Claudio Freire
Sería bastante parecido a hacerlo con numpy.
Por lejos.
Claudio Freire
On Friday 18 June 2010 18:59:23 John Rowland Lenton wrote:
> Not enough information to check signature validity. Show Details
Aguantame un cachito que te lo implemento en FLIP (y para que no sea OT, ra->
> On Fri, Jun 18, 2010 at 06:54:03PM -0300, Claudio Freire wrote:
> >
> >
> > ¿por qué se está pareciendo a una competencia sobre intérpretes de
> > brainfuck?
>
> porque befunge sería demasiado para esta altura de la semana.
flip está implementado en python ;-)
Flip en acción:
http://dl.dropbox.com/u/840438/flip.ogg
No lo conocía...
...parece como si fuera para programar algoritmos cuánticos o algo así
(las bolitas fotones, los "espejos", los "operadores cuánticos"...)
Peperulo Sandro
No importa si es pesado o liviano. Con Hotmail Skydrive tenés 25 GB para guardar todo. Clic aquí
Lucio Torre
> buenas gente. la pregunta no es dificil.. pero si un tanto confusa.
> quiero en mi programa abrir una base de datos al inicio.. en un modulo
> NN.py, y luego no cerrar esa base de datos nunca y en otro modulo (agrego.py
> por ej.) ubicado en la misma carpeta.. utilizar la variable que hace
> referencia a esa base y no andar conectando nuevamente con la base.. creo
> que la pregunta es un poco mas general quizas y la duda sea como importar
> solo variables.. pero la verdad que con el tema de la base de datos no me
> funciona.. probe haciendo import de todo tipo y declarando variables
> globales pero nada.. no me queda claro porque no me reconoce la conexion ya
> abierta en la base de datos en los diferentes archivos ubicados en la misma
> carpeta.
No te funciona para conecciones de base de datos pero si para otras cosas?
Lucio
Roberto Alsina
> buenas gente. la pregunta no es dificil.. pero si un tanto confusa.
> quiero en mi programa abrir una base de datos al inicio.. en un modulo
> NN.py, y luego no cerrar esa base de datos nunca y en otro modulo
> (agrego.py por ej.) ubicado en la misma carpeta.. utilizar la variable que
> hace referencia a esa base y no andar conectando nuevamente con la base..
> creo que la pregunta es un poco mas general quizas y la duda sea como
> importar solo variables.. pero la verdad que con el tema de la base de
> datos no me funciona.. probe haciendo import de todo tipo y declarando
> variables globales pero nada.. no me queda claro porque no me reconoce la
> conexion ya abierta en la base de datos en los diferentes archivos
> ubicados en la misma carpeta.
>
> se habrá entendido?
>
> de todas formas agradezco..
>
> uso MYSQLdb para conectarme con la base. y python 2.6.
Create un modulo db.py
En ese módulo guardá una variable global "conn" con la conexión.
Importá el módulo desde NN.py y desde agrego.py
Usá esa variable global "db.conn"
Peperulo Sandro
Tu vida no tiene límites, ahora Hotmail tampoco. 25 GB para organizar y compartir todo. Ver más
Carlos Marcelo Cabrera
poco.
El Fri, 18 Jun 2010 19:24:23 -0300
Roberto Alsina <ral...@netmanagers.com.ar> escribió:
> La explicación:
>
> http://lateral.netmanagers.com.ar/weblog/posts/BB561.html
Aviso: El enlace al vídeo en la página está roto. Creo que sería bueno que lo
actualices.
Saludos
--
/* ************************************************************
Carlos Marcelo Cabrera, alias "Point to null"
Medios de contacto adicionales:
Weblog: http://pointtonull.esdebian.org
Jabber: point_...@esdebian.org
Yahoo: dxm...@yahoo.com.ar
ICQ: 303014677
************************************************************ */
Roberto Alsina
> Realmente muy interesante realmente, creo que lo usaré para procastinar
> un poco.
>
> El Fri, 18 Jun 2010 19:24:23 -0300
>
> Roberto Alsina <ral...@netmanagers.com.ar> escribió:
> > La explicación:
> >
> >
> > http://lateral.netmanagers.com.ar/weblog/posts/BB561.html
>
> Aviso: El enlace al vídeo en la página está roto. Creo que sería bueno que
> lo actualices.
Sí, por eso pasé otro link.
El servicio que usaba para los archivos grandes falleció, y me da pereza
revisar entre los 950 posts adonde lo usé :-(
Sebastian Bassi
>> def balanceado(s):
>> while s != s.replace('()',''): s=s.replace('()','')
>> return not s
> La mas linda por lejos, sin duda.
Para mi esto es pensamiento lateral o "thinking outside the box".
Felicitaciones Roberto.
Sebastian Bassi
> buenas gente. la pregunta no es dificil.. pero si un tanto confusa.
> quiero en mi programa abrir una base de datos al inicio.. en un modulo
> NN.py, y luego no cerrar esa base de datos nunca y en otro modulo (agrego.py
Ya lo solucionaste pero queria comentar algo. Deics "no cerrar esa
base de datos nunca", tené en cuenta que en MySQL despues de un tiempo
sin queries, la conexión "se corta" (timeout error). No se si se
aplica a tu caso, pero es para tener en cuenta.
Carlos Marcelo Cabrera
Sebastian Bassi <sba...@clubdelarazon.org> escribió:
> On Fri, Jun 18, 2010 at 5:35 PM, Hystrix <e...@hystrix.com.ar> wrote:
> >> def balanceado(s):
> >> while s != s.replace('()',''): s=s.replace('()','')
> >> return not s
> > La mas linda por lejos, sin duda.
>
> Para mi esto es pensamiento lateral o "thinking outside the box".
> Felicitaciones Roberto.
Totalmente de acuerdo, es la solución más elegante.
Aunque.. ¿no es un poco más eficiente (y legible) usar "in"?. Algo así:
"""
def is_balanced(string):
while "()" in string:
string = string.replace("()", "")
return not string
"""
Según timeit usando "in" tarda solo un 60% del tiempo usado con la versión
".replace".
Roberto Alsina
> El Fri, 18 Jun 2010 22:14:04 -0300
> Sebastian Bassi <sba...@clubdelarazon.org> escribió:
>> On Fri, Jun 18, 2010 at 5:35 PM, Hystrix <e...@hystrix.com.ar> wrote:
>> >> def balanceado(s):
>> >> while s != s.replace('()',''): s=s.replace('()','')
>> >> return not s
>> > La mas linda por lejos, sin duda.
>>
>> Para mi esto es pensamiento lateral o "thinking outside the box".
>> Felicitaciones Roberto.
>
> Totalmente de acuerdo, es la solución más elegante.
>
> Aunque.. ¿no es un poco más eficiente (y legible) usar "in"?. Algo así:
>
> """
> def is_balanced(string):
> while "()" in string:
> string = string.replace("()", "")
> return not string
> """
>
> Según timeit usando "in" tarda solo un 60% del tiempo usado con la versión
> ".replace".
Sí, es mejor.
Matigro
<sba...@clubdelarazon.org> escribió:
> 2010/6/18 Matigro <mat...@gmail.com>:
>> La cadena está balanceada, tengo la misma cantidad de paréntesis de
>> abrir que de cerrar, no sirve para la sintaxis del castellano ni para
>> un lenguaje de programación reconocido, pero eso no dice en el
>> enunciado.
>
> Si yo te estuviera evaluando pondria en mi hoja:
> Desempeño técnico: A+
> Actitud para trabajo en equipo: D
> Espera tranquilo que te llame :)
jejeje. Si fuera para conseguir un trabajo, lo escribo hasta con
biromes de colores :)
Se podría verificar que el primer paréntesis no sea un ')', de serlo
retorna false. Despues dejo el código que estaba, pero con cometarios,
para que mi Actitud de Trabajo en Equipo se un 'pierde tiempo
comentando código que nadie va a leer'.
Salute
--
http://www.linkedin.com/in/matigro
Hernan Olivera
On Fri, Jun 18, 2010 at 5:35 PM, Hystrix <e...@hystrix.com.ar> wrote:Para mi esto es pensamiento lateral o "thinking outside the box".
>> def balanceado(s):
>> while s != s.replace('()',''): s=s.replace('()','')
>> return not s
> La mas linda por lejos, sin duda.
Felicitaciones Roberto.
Si, totalmente de acuerdo. Una obra de arte.
Creo que piensa como una maquina de Turing ;-)
_______________________________________________
pyar mailing list py...@python.org.ar
http://listas.python.org.ar/listinfo/pyar
PyAr - Python Argentina - Sitio web: http://www.python.org.ar/
--
Hernan Olivera
Fabian Ezequiel Gallina
<garcia.b...@gmail.com> escribió:
> Hola listeros:
>
> el otro dia charlando con un compañero de trabajo, me contó que un
> ejercicio que toma en entrevistas, es el siguiente:
>
> escribir una función la cual recibe una cadena conformada unicamente
> por parentesis abiertos y cerrados.
> la funcion tiene que retornar un booleano representando si los
> parentesis estan balanceados o no.
>
> balanceados significa: todo parentesis que abre, corresponde a uno que cierra.
>
> casos validos: (()), (), ()(), ((())), ((()())) ...
> casos invalidos: )()), ((()) )( ...
>
> despues de jugar un rato yo lo resolví de esta forma:
>
> http://pastebin.com/5BHcxbDC
>
> mi pregunta es la siguiente:
>
> a alguien se le ocurre alguna forma de hacerlo usando list comprehension ?
>
> alguna forma chiflada de hacerlo?
>
>
> aca les dejo los unit tests para probarlo si quieren.
>
> http://pastebin.com/7En3UzBk
>
Forma en que la hubiera presentado:
def check_parens(string):
checker = 0
for char in string:
if char == ")":
checker -= 1
elif char == "(":
checker += 1
if checker < 0:
return False
return checker == 0
Onliner marca gripe A para los objetivos del post:
def check_parens(s):
return reduce(lambda t, v: len(s) if t < 0 else v + t, [1 if c ==
"(" else -1 for c in s]) == 0
Tests baratos:
assert check_parens("(") == False
assert check_parens(")") == False
assert check_parens(")()") == False
assert check_parens("((())))") == False
assert check_parens("(((()))") == False
assert check_parens(")((())))") == False
assert check_parens(")((()))(") == False
assert check_parens("()()")
assert check_parens("((((())))())")
Saludos resfriados,
--
Fabián E. Gallina
http://www.from-the-cloud.com
Esteban Ordano
Marcos Alcazar
cadena es par o impar? Si es impar, no es posible que esté balanceada.
Me evitaría todas las posibles comprobaciones posteriores. No sé qué
tanto es bueno para el rendimiento, pero la comprobación creo que es
válida.
if len(cadena_de_strings)%2==0: #es la mejor forma?
#el resto
Saludos!
--
Marcos Alcazar
Usá Software Libre!!
Federico Heinz
> Si es obligatorio usar una comprehension te diria algo con esta
> idea...
> def balanceado(s):
> profundidades = [s[:index+1].count("(")-s[:index+1].count(")")
> for index in xrange(len(s)) ]
> return (not s) or (all(p>=0 for p in profundidades) and
> profundidades[-1]=0)
Esto debería ser lineal, pero usa una variable global que estoy
seguro que se puede reemplazar por algo más cheto.
c = 0
def balanceado(s):
global c
c = 0
def f(x):
global c
c = c+{'(': 1, ')': -1}[x]
return c
p = [f(x) for x in s]
return (not s) or (all(x >= 0 for x in p) and p[-1] == 0)
Fede
Facundo Batista
> Ya lo solucionaste pero queria comentar algo. Deics "no cerrar esa
> base de datos nunca", tené en cuenta que en MySQL despues de un tiempo
> sin queries, la conexión "se corta" (timeout error). No se si se
> aplica a tu caso, pero es para tener en cuenta.
Si vas a hacer algo más o menos eficiente, no podés tener los
roundtrips de conexión cada vez que querés usar la BD.
Es mejor soportar que el motor te cierre la conexión, y reabrirla en ese caso.
Por último, un detalle si van a tener conexiones abiertas: no accedan
a las mismas desde diferentes hilos, la mayoría de los módulos tienen
problema con eso.
Slds.
--
. Facundo
Blog: http://www.taniquetil.com.ar/plog/
PyAr: http://www.python.org/ar/
Roberto Alsina
> On Friday 18 June 2010 21:16:19 Carlos Marcelo Cabrera wrote:
> > Realmente muy interesante realmente, creo que lo usaré para procastinar
> >
> > un poco.
> >
> >
> >
> > El Fri, 18 Jun 2010 19:24:23 -0300
> >
> >
> >
> > Roberto Alsina <ral...@netmanagers.com.ar> escribió:
> > > La explicación:
> > >
> > >
> > > http://lateral.netmanagers.com.ar/weblog/posts/BB561.html
> >
> >
> >
> > Aviso: El enlace al vídeo en la página está roto. Creo que sería bueno
> > que lo actualices.
>
> Sí, por eso pasé otro link.
>
> El servicio que usaba para los archivos grandes falleció, y me da pereza
> revisar entre los 950 posts adonde lo usé :-(
Gracias a Carlos Cabrera que arregló algunas cosas, ahora ra-flip puede
generar la secuencia de fibonacci:
http://www.youtube.com/watch?v=83dKhdKsw9Q
Federico Heinz
> Esto debería ser lineal, pero usa una variable global que estoy
> seguro que se puede reemplazar por algo más cheto.
*Esto* es lo que estaba buscando. No usa exactamente list
comprehension, pero espero que el uso de 'all' califique.
def acc(n):
value = [n]
def addacc(m):
value[0] += m
return value[0]
return addacc
def balanceado(s):
c = acc(0)
return (not s) or (all(c({'(':1 ,')':-1}[x]) >= 0 for x in s) and c(0) == 0)