[pyar] [OT] - Checkeando parentesis balanceados.

[Fabian Ezequiel Gallina]

El día 18 de junio de 2010 13:24, Mariano Garcia Berrotarán
<garcia.berrotaran en 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