Desarrollo de Python
  1. Desarrollo de Python
  3. Elimine los paréntesis alrededor del primer elemento en un árbol de expresión y en cada uno de sus árboles de subexpresión en Python
Intereting Posts
ejecutar django con xampp en windows Comparando matrices NumPy para que los NaN se comparen iguales ¿Insertando unicode en sqlite? Convertir imagen PIL a MIMEImage ¿Es posible agregar varias columnas a la vez a un dataframe de pandas? La función no está definida como error en Python filas coincidentes entre marcos de datos en pandas en python Código de Python simple sobre doble bucle. Parcelas hechas con rpy enviado a X11 de repente cerca? ¿Qué poner en un módulo de documentación de python? AttributeError: el objeto ‘propiedad’ no tiene atributo Cómo cambiar el color del botón con tkinter Error al construir uwsgi con pip en un entorno virtual ¿Cómo ejecutar Spyder en un entorno virtual? python -> combinaciones de números y letras

Elimine los paréntesis alrededor del primer elemento en un árbol de expresión y en cada uno de sus árboles de subexpresión en Python

El objective es implementar una operación de simplificación: elimine los paréntesis alrededor del primer elemento en un árbol de expresión y en cada uno de sus árboles de subexpresión, donde la expresión se da como una entrada de cadena entre varios paréntesis. Esto debe funcionar para un número arbitrario de paréntesis, por ejemplo:

(12) 3 ((45) 6) -> 123 (456), quite los paréntesis alrededor de 12 luego alrededor de 45

((12) 3) 4 (((5) 67) 8) -> 1234 (5678), quite los paréntesis alrededor de 12, luego 123, luego 5, luego 567. No quite los paréntesis alrededor de 5678 ya que esa es la segunda elemento.

¿Cómo hago esto?

EDIT: hasta ahora lo que tengo es esto: 

def simplify(expression): """ call itself recursively until no consecutive parentheses exist """ result = [] consec_parens = 0 inside_nested = False for char in expression: if char == ')' and inside_nested: inside_nested = False consec_parens = 0 continue if char == '(': consec_parens += 1 else: consec_parens = 0 if consec_parens == 2: inside_nested = True else: result.append(char) result = ''.join(result) if result == expression: return result return simplify(result)

Funciona para todos los casos donde el número de paréntesis nesteds es al menos dos, pero no funciona para la cabeza, es decir, para (AB) C, no elimina los paréntesis alrededor de AB. Sin embargo, para ((AB) C) elimina los paréntesis alrededor de AB, lo que da como resultado (ABC).

Esto puede verse como una máquina de estados finitos (con tres estados) que crea una instancia por nivel, donde cada símbolo ( crea un nuevo nivel). Alternativamente, es un autómata de empuje determinista con dos estados triviales (un estado en progreso y un estado estado terminado, ninguno de los cuales modelamos explícitamente) y tres símbolos de stack, cada uno representa el estado de la máquina para el nivel actual:

  • Antes : el estado en el que nos encontramos inmediatamente después de ingresar a un nivel. Encuentro con cualquier personaje excepto ) transiciones a algún otro estado.
  • En el interior : el estado en el que estamos, entre paréntesis, que debe eliminarse. Se ingresa por encoutering a ( mientras que en Antes .
  • Hecho : el estado en el que estamos cuando se ha procesado el nivel actual. Esto significa que o bien ya eliminamos un conjunto de paréntesis o no necesitábamos hacerlo, ya que el primer elemento no estaba incluido en ellos.

Además, al encontrar un ( coloca un nuevo símbolo en la stack, los modelos que ingresan a un nuevo nivel, y a ) saca un símbolo, los modelos que salen de un nivel. Todos los caracteres de entrada se adjuntan al resultado, excepto cuando se producen las transiciones Antes → Interior e Interior → Hecho .

El siguiente código es una traducción simple de lo anterior a Python: 

 from enum import Enum class State(Enum): Before = 0 Inside = 1 Done = 2 def simplify(expression): levels = [State.Before] result = [] for c in expression: if c == '(': if levels[-1] == State.Before: levels[-1] = State.Inside else: result.append(c) levels.append(State.Before) elif c == ')': levels.pop() if levels[-1] == State.Inside: levels[-1] = State.Done else: result.append(c) else: if levels[-1] == State.Before: levels[-1] = State.Done result.append(c) return ''.join(result)

Probando lo anterior, obtenemos: 

 >>> simplify('(12)3((45)6)') '123(456)' >>> simplify('((12)3)4(((5)67)8)') '1234(5678)' >>> simplify('(AB)C') 'ABC' >>> simplify('((AB)C)') 'ABC'