algorithm - Algoritmo para evaluar expresiones lógicas anidadas

tree conjunctive-normal-form

Question

Tengo una expresión lógica que me gustaría evaluar. La expresión se puede anidar y consiste en T (Verdadero) o F (Falso) y paréntesis. El paréntesis "(" significa "O lógico". Dos términos TF uno al lado del otro (o cualquier otra combinación una al lado de la otra), debe ser ANDED (lógico AND).

Por ejemplo, la expresión:

((TFT)T) = true

Necesito un algoritmo para resolver este problema. Pensé en convertir la expresión primero en forma normal disyuntiva o conjuntiva y luego puedo evaluar fácilmente la expresión. Sin embargo, no pude encontrar un algoritmo que normalice la expresión. ¿Alguna sugerencia? Gracias.

La declaración del problema se puede encontrar aquí: https://icpcarchive.ecs.baylor.edu/index.php?option=com_onlinejudge&Itemid=2&category=378&page=show_problem&problem=2967

Editar: He entendido mal parte del problema. En la expresión lógica dada, los operadores AND / OR se alternan con cada paréntesis "(". Si vamos a representar la expresión por un árbol, entonces los operadores AND / OR dependen del nivel de profundidad del subárbol. inicialmente dado que los árboles en el nivel más profundo son árboles AND. Mi tarea es evaluar la expresión dada, posiblemente, mediante la construcción del árbol. Gracias por las respuestas a continuación, que aclaró el requisito correcto del problema.

Answer 1

Después de leer la descripción del problema en el sitio al que se vinculó, creo que es posible que haya entendido mal el problema. Ya sea que necesite "lógica Y" u "lógica O", los términos dependen de cuántos niveles hacia abajo está desde el nodo raíz.

Puede resolver fácilmente este problema analizando la expresión en un árbol de sintaxis y luego recorriendo el árbol recursivamente, evaluando cada sub-expresión hasta que vuelva al nodo raíz.

Answer 2

Escanee la cadena de izquierda a derecha. Cada vez que vea un paréntesis izquierdo, agregue una nueva entrada a la estructura de la pila. Cuando veas un paréntesis a la derecha, coloca la entrada más alta en la pila, evalúala en T o F, vuelve a abrir la pila y anexa el valor calculado al término reventado. Continúa hasta el final de la cuerda, en ese punto tendrás una cuerda de T y F, y la evaluarás.

Para evaluar una cadena de Ts y Fs, devuelve T si todos son T y F de lo contrario. Entonces tenemos...

evaluate(String expression)
 1. subexpr = ""
 2. for i := 1 to n do
 3.     if expression[i] == "(" then
 4.         stack.push(subexpr)
 5.         subexpr = ""
 6.     else if expression[i] == ")" then
 7.         result = evaluateSimple(subexpr)
 8.         subexpr = stack.pop() + result
 9.     else subexpr += expression[i]
10. return evaluate2(subexpr)

evaluate2(String expression)
 1. for i := 1 to n do
 2.     if expression[i] == "F" then return "F"
 3. return "T"

O algo así debería hacerlo (EDITAR: de hecho, esto no responde correctamente a la pregunta, incluso como se le preguntó, vea los comentarios. Dejando esto solo, ya que sigue uno en la dirección correcta). Tenga en cuenta que solo podría tener una función, evaluar, que hace lo que evalúa2, pero después del primer ciclo, y solo para subexpr. Esto evita pasar por la copia innecesaria que implicaría, pero tendrías menos código en el otro sentido.

Answer 3

Después de haber analizado el problema original , creo que lo has malentendido.

Esta pregunta se trata de un árbol AND/OR donde los nodos en el nivel más profundo son AND nodos. Los operadores lógicos en los otros nodos están determinados por este factor: no sabemos si son Nodos AND u OR inicialmente, solo se nos da que los nodos en el nivel más profundo son AND , por lo que los nodos en el siguiente nivel superior son OR nodos, y el siguiente nivel superior son AND nodos, y así sucesivamente ... los operativos lógicos se intercambian entre diferentes profundidades del árbol. Esto quedará claro si mira la muestra AND/OR árbol que han proporcionado.

La forma en que abordaría este problema es primero descubrir la conexión lógica para el nodo raíz. Esto se puede hacer con un único escaneo sobre la expresión y haciendo un seguimiento del número de paréntesis. Tenga en cuenta que cada () corresponde a un nuevo nodo en el árbol (el siguiente nivel del árbol). Por ejemplo, considere la expresión:

((F(TF))(TF))

Cuando cruzas esta expresión, primero encontramos 3 paréntesis de apertura, 2 de cierre, 1 de apertura y finalmente 2 de cierre. Si toma el número máximo de paréntesis que se abrieron en un momento dado durante esta caminata, será la profundidad máxima de este árbol AND/OR ( 3 en el ejemplo anterior).

Entonces, ¿qué significa esto? Si la profundidad del árbol es impar, entonces el nodo raíz es un nodo AND ; de lo contrario, la raíz es un nodo OR (porque las conexiones se alternan).

Una vez que conozca la conexión del nodo raíz, puede evaluar esta expresión usando una máquina basada en pila simple. Debemos tener en cuenta que cada vez que abrimos o cerramos un paréntesis, debemos voltear el conector. Así es como se evalúa la expresión anterior:

AND |- (•(F(TF))(TF))

Observe que la viñeta indica dónde estamos en la expresión (como la parte superior de la pila). Luego procedemos de la siguiente manera:

OR  |- ((•F(TF))(TF))   // flipped the connective because we jumped a node
OR  |- ((F•(TF))(TF))   // nothing to evaluate on the current node, push F
AND |- ((F(•TF))(TF))
AND |- ((F(T•F))(TF))
AND |- ((F(TF•))(TF))
AND |- ((F(F•))(TF))    // Two booleans on top, T AND F = F (reduce)
OR  |- ((F(F)•)(TF))    // Jumped out of a node, flip the sign
OR  |- ((FF•)(TF))      // Completely evaluated node on top, (F) = F (reduce)
OR  |- ((F•)(TF))       // Two booleans on top, F OR F = F (reduce)
AND |- ((F)•(TF)) 
AND |- (F•(TF))
OR  |- (F(•TF))
OR  |- (F(T•F))
OR  |- (F(TF•))
OR  |- (F(T•))
AND |- (F(T)•)
AND |- (FT•)
AND |- (F•)

Entonces obtienes la respuesta final como F Esto tiene alguna relación con el análisis de desplazamiento-reducción, pero las reducciones en este caso dependen de la profundidad actual de la AST en la que estamos operando. Espero que puedas traducir esta idea en código (necesitarás una pila y una variable global para hacer un seguimiento del operativo lógico actual en vigor).

Finalmente, gracias por presentar ese sitio. También te puede interesar este sitio .

Answer 4

Resolví este problema usando una técnica diferente a las mencionadas. Y lo tengo Aceptado por el juez del sistema en línea.

Después de descubrir el operador en el primer nivel del árbol (Gracias a @Asiri Rathnayake por su idea), construyo recursivamente el árbol de expresiones. Durante la construcción, exploro la cadena. Si el personaje es ''('', entonces creo un nodo con el valor actual del operador y lo agrego al árbol. Luego, altero el operador y busco un nivel de recursión más profundo. Si el personaje es ''T'', entonces creo un nodo con el valor "True", agréguelo al árbol y continúe escaneando. Si el carácter es "F", entonces creo un nodo con el valor "False", lo agrego al árbol y sigo escaneando. Finalmente, si el el carácter es '')'', luego regreso a un nivel arriba de la recursión.

Al final, tendré completado el árbol de expresiones. Ahora, todo lo que necesito hacer es una evaluación simple para el árbol que usa la función recursiva básica.

A continuación está mi código C ++:

#include<iostream>
#include<string>
#include<vector>
#include<algorithm>

using namespace std;

struct Node {

    char value;
    vector<Node*> children;
};


void ConstructTree (int &index, string X, Node *&node, int op)
{

    for(; index<X.size(); index++)
    {
        if(X[index]==''T'')
        {
            Node *C= new Node;
            C->value=''T'';
            node->children.push_back(C);
        }


        else if(X[index]==''F'')
        {
            Node* C= new Node;
            C->value=''F'';
            node->children.push_back(C);
        }


        else if(X[index]==''('')
        {
            if(op==0)
            {
                Node* C= new Node;
                C->value=''O'';
                node->children.push_back(C);
            }


            else
            {
                Node* C= new Node;
                C->value=''A'';
                node->children.push_back(C);
            }

            index++;
            ConstructTree(index,X,node->children[node->children.size()-1],1-op);
        }

        else
            return;
    }



}

bool evaluateTree(Node* node)
{
    if(node->value==''T'')
        return true;
    else if(node->value==''F'')
        return false;
    else if(node->value==''O'')
    {
        for(int i=0; i<node->children.size(); i++)
            if(evaluateTree(node->children[i])==true)
                return true;

        return false;
    }

    else if(node->value==''A'')
    {

        for(int i=0; i<node->children.size(); i++)
            if(evaluateTree(node->children[i])==false)
                return false;

        return true;
    }
}


int main()
{
    string X;
    int testCase=1;

    while(cin>>X)
    {
        if(X=="()")
            break;


        int index=0;

        int op=-1;

        int P=0;

        int max=0;
        for(int i=0; i<X.size(); i++)
        {
            if(X[i]==''('')
                P++;
            if(X[i]=='')'')
                P--;

            if(P>max)
                max=P;
        }


        if(max%2==0)
            op=0; //OR
        else
            op=1; //AND


        Node* root = new Node;

        if(op==0)
        root->value=''O'';
        else
        root->value=''A'';

        index++;
        ConstructTree(index,X,root,1-op);

        if(evaluateTree(root))
            cout<<testCase<<". true"<<endl;
        else
            cout<<testCase<<". false"<<endl;

        testCase++;
    }
}