Eliminar un elemento de una lógica de filtro

MaSoBa

Buenas a todos,

Estoy trabjando en un proyecto personal y tengo un problema que no se cómo abordarlo eficientemente y sin romperme mucho la cabeza. He intentado buscar algún planteamiento pero no he encontrado nada (seguramente sea porque no doy exactamente con las palabras necesarias para la búsqueda).

Supongamos que tenemos una cadena de texto que representa una lógica a aplicar.

Un ejemplo más o menos sencillo

((1 OR 2) AND 3 OR (4 OR 2) OR 5

Si te dicen de eliminar el 2 se tendría que quedar así

(1 AND 3 OR 4) OR 5

Mi primer acercamiento ha sido tirar de expresiones regulares teniendo en cuenta algunos casos de uso en los que podría estar el número. Pero este acercamiento creo que no es el correcto porque creo que hay demasiados casos de uso que se me escapan. ¿A alguien se le ocurre como plantear el problema?

Mi acercamiento
Naith

Empezaría por transformar la cadena de texto a una estructura de datos más apropiada. Por ejemplo, un árbol. Una vez con el árbol si te piden que quites uno resuelves los nodos padres de los nodos que contenga lo que tengas que eliminar.

1 1 respuesta
frekaice

Yo creo que deberías plantear un árbol binario y al eliminar el elemento, volver a hacer la representación a texto. También me viene a la cabeza que quizá con notación polaca se podría hacer algo

Al menos yo creo que seria más simple que empezar a trabajar con regex y empezar con casos extraños

1 respuesta
MaSoBa

#2 #3 Veo que ambos coincidís en usar un árbol binario. Nunca he implementado ninguno y por lo que me informé en su momento no consigo ver cómo plantearlo.

Si no me equivoco, un árbol binario tiene un nodo principal en el que se informa su valor y qué nodos tiene a su izquierda y derecha. Y a su vez estos nodos tienen cada uno su valor y qué nodos tienen a su izquierda y derecha...

No veo cómo implementar un árbol binario a este problema. Seguramente sea porque nunca he implementado uno. En el caso del ejemplo que puse en el primer post, ¿qué valor tendría que tener el nodo principal? No lo consigo ver...

1 respuesta
Naith
#4MaSoBa:

Veo que ambos coincidís en usar un árbol binario

No tiene por que ser estrictamente binario. Si vas a usar solamente AND y OR si, pero si tienes otros operadores que requieran de 3 valores un binario no te serviría.

Sería algo así, pero cambiando add y subb por AND y OR:

El concepto es el mismo que el que se usa en el proceso de interpretar/compilar un programa, árbol de sintaxis abstracto.

2 1 respuesta
MaSoBa

#5 Mmm, de acuerdo. Me voy a poner un poco las pilas con estos temas porque la verdad que ahora mismo no tengo nada claro el concepto del árbol. A ver si leyendo sobre el tema me hace clic la cabeza y empiezo a ver el funcionamiento.

Muchas gracias!

desu

En este caso diría que se resuelve como si fuera un SAT solver.

Por un lado tienes las expresiones, por otro lado la lista de relaciones variable - expresión

Si te piden quitar una variable, consultas la lista de expresiones relacionadas y las quitas.

En tu caso concreto quizás puedes tener un árbol estilo trie para recorrerlo linealmente de padre a hijos e ir haciendo pop de las expresiones a quitar. La gracia es este pop.

Pero vamos, necesitas dos estructuras para lo mas eficiente / rápido.

@fyn4r te ayuda

Usuarios habituales

  • desu
  • MaSoBa
  • Naith
  • frekaice