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
¿Us.fork () usará copia en escritura o realizará una copia completa del proceso padre en Python? ¿Cómo obtener nombres de campos de formulario y valores en Python? Cómo iniciar y configurar un cluster EMR usando boto Trazar flechas de distancia en dibujo técnico. ¿Hay formas más elegantes de manejar listas en Java? (Python VS Java) ¿Una zona horaria específica está usando DST en este momento? El progtwig no entra si el enunciado Hashing arrays en Python ¿Cómo verifico si dos números consecutivos (enteros) en una lista tienen el mismo valor? Suprimiendo salida en llamada de subproceso python ¿Cómo raspar los datos de URL del sitio de intranet usando python? Detectando enteros consecutivos en una lista seleccionando un rango de columnas en Python Matplotlib Incrustar un gráfico en una interfaz de usuario PyQt5 ¿Cómo convertirse en un buen codificador de Python?

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'