26-10-2012 02:09
(25-10-2012 22:24)Nikayuri link Ando pensando, aparte de todo esto, cómo diseñar un programita (subprograma, en realidad) que sea capaz de calcular y realizar operaciones de álgebra de Boole (todo esto a raíz de un reto que me propuso un compañero de clase). Quiero pensarlo por mí misma (o sea, no quiero que nadie me dé la solución xD), pero alguna pista no me vendría mal. He pensado que tal vez con arrays, ordenando las letras, pueda realizar las simplificaciones pertinentes.
Lo primero sería hacer un pequeño analizador léxico que sepa distinguir los tokens del lenguaje. Los tokens podrían ser los valores booleanos (0 y 1), el paréntesis derecho, el paréntesis izquierdo, y luego todos los operadores binarios: disyunción, conjunción, negación, condición material, bicondicional, negación conjunta, ectétera. Esta ristra de tokens podrías guardarla en una estructura como una lista enlazada, pienso que sería lo más adecuado. Lo más sencillo sería asignar un número a cada token, y cada vez que se encuentre este token añadir (por el principio) ese entero a la lista. Probablemente la clase list de C++ funcione bien. Permite todo lo que debería permitir una lista enlazada; insertar en la posición que quieras, sustituir el valor de la posición que quieras y eliminar de la lista las posiciones que quieras; y además es bastante eficiente.
Sabemos que todo operador lógico puede simplificarse utilizando paréntesis, disyunciones, conjunciones y negaciones. Las simplificaciones las puedes encontrar aquí, aunque supongo que ya las conocerás. Por último sería cuestión de hacer recorridos a la lista, simplificándola, hasta obtener el resultado.
Te pondré un ejemplo de cómo lo haría yo. Por ejemplo, tenemos la cadena:
1 AND ¬ ( 0 1 AND 1 ) OR 0
Esta cadena es leía y guardada en una lista, y entonces se llama al procedimiento general; un procedimiento de simplificación de cadenas que tendrá como parámetro la propia lista; que devolverá un valor lógico 1 (true) o 0 (falso). Este procedimiento hará tres recorridos de la lista, simplificándolo hasta que sólo quede un booleano, que será el que devuelva.
En el primer recorrido, se buscará cualquier operador que se pueda simplificar excepto disyunciones y conjunciones. Así encontramos el condicional (bueno, en realidad encontraremos el entero que representa al condicional). Encontrado el condicional, llamamos a un procedimiento que, pasándole como parámetro la posición actual de la lista, simplifique este operador. Obviamente habrá que definir un procedimiento de simplificación para cada operador y para simplificar las operaciones entre paréntesis haremos una llamada a otro procedimiento general.
La simplificación en este caso es bien sencilla, añadir en la lista una negación delante del valor booleano que va en la posición anterior (en la lista) del condicional, y cambiar el token condicional por uno de disyunción:
1 AND ¬ ( ¬ 0 OR 1 AND 1 ) OR 0
Una vez simplificado el máximo número posible de operadores, haríamos el segundo recorrido, para simplificar operaciones dentro de paréntesis o negaciones. Hay dos opciones para este caso: recorrido hacia delante (desde el comienzo hasta el fin) y recorrido hacia atrás (desde el fin hasta el comienzo). Yo recomiendo hacer un recorrido hacia atrás, buscando paréntesis izquierdos y negaciones, por ser más bastante más sencillo que el otro.
Lo primero que encontramos es una negación, así que llamamos al procedimiento de simplificación de negaciones, que lo que hace es cambiar (asignar) el valor booleano que va en la posición posterior de la negación y eliminar la negación:
1 AND ¬ ( 1 OR 1 AND 1 ) OR 0
Luego encontramos un paréntesis izquierdo, así que encontramos el paréntesis derecho que lo cierra (que será el próximo si recorremos la lista de nuevo hacia delante). En el recorrido de un paréntesis a otro iremos creando una nueva lista con todos los tokens que hay entre los paréntesis, con lo que llamamos a otro procedimiento general:
1 OR 1 AND 1
Y lo de siempre, empezamos a recorrer la lista de nuevo. Hará el primer y el segundo recorrido pero no encontrará nada, así que en seguida pasará con el tercer recorrido; el de buscar OR y AND. Encontramos un OR, vale, simplifiquémoslo con su respectivo procedimiento. ¿Cómo simplificarlo? Muy fácil:
IF valor_anterior=1 OR valor_siguiente=1 THEN 1
ELSE 0
Así que borramos de la lista la posición del valor anterior y del valor siguiente, y sustituimos el token OR por el valor correspondiente, en este caso 1. Y tenemos:
1 AND 1
Más de lo mismo, llamamos al respectivo procedimiento de simplificación de AND:
IF valor_anterior=1 AND valor_siguiente=1 THEN 1
ELSE 0
Y entonces tenemos 1. Como este ya sólo quedará un booleano, significará que ha terminado a su estado final. Así que el procedimiento devolverá ese booleano. El procedimiento principal recibirá el booleano, eliminará toda la cadena que había entre los parénteis (y los paréntesis) y pondrá en su lugar el 1:
1 AND ¬ 1 OR 0
Se simplificaría la negación:
1 AND 0 OR 0
Y como ya no quedarían más paréntesis ni negaciones, pasaría al tercer recorrido, que ya acabamos de ver. Y así sucesivamente...
El único problema es que siempre tienes que escribir fórmulas bien formadas. Si hay algún error gramatical, el programa no funcionará correctamente.┬á Para hacerlo robusto habría que utilizar otras herramientas de análisis sintáctico y semántico, como Flex o Bison, que en mi opinión son algo complicadas para un alumno de primero.
En fin, no sé si se me ha entendido bien, si tienes alguna duda pregunta. Si quieres lo puedo escribir en pseudocódigo, aunque como decías que querías una explicación y no una solución, he preferido no hacerlo.
PD: Ahora que me doy cuenta el programa anterior lo hice de binario a decimal, y no de decimal a binario, como se pedía. Vaya fallo. Pero bueno, de decimal a binario es más o menos igual de sencillo.