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:
)
transiciones a algún otro estado. (
mientras que en Antes . 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'