Algorithm for evaluating nested logical expression

Question

I have a logical expression that I would like to evaluate. The expression can be nested and consists of T (True) or F (False) and parenthesis. The parenthesis "(" means "logical OR". Two terms TF beside each others (or any other two combinations beside each others), should be ANDED (Logical AND).

For example, the expression:

((TFT)T) = true

I need an algorithm for solving this problem. I thought of converting the expression first to disjunctive or conjunctive normal form and then I can easily evaluate the expression. However, I couldn't find an algorithm that normalizes the expression. Any suggestions? Thank you.

The problem statement can be found here: https://icpcarchive.ecs.baylor.edu/index.php?option=com_onlinejudge&Itemid=2&category=378&page=show_problem&problem=2967

Edit: I misunderstood part of the problem. In the given logical expression, the AND/OR operators alternate with every parenthesis "(". If we are to represent the expression by a tree, then the AND/OR operators depend on the the sub-tree's depth-level. However, it's initially given that the trees at the deepest level are AND-trees. My task is to evaluate the given expression possibly by constructing the tree. Thanks for the answers below which clarified the correct requirement of the problem.

Landloper

Answer 1

I solved this problem using a different technique than the ones mentioned. And I got it Accepted by the online system judge.

After figuring out the operator at the first level of the tree (Thanks to @Asiri Rathnayake for his idea), I recursively construct the expression tree. During the construction, I scan the string. If the character is '(', then I create a node with the current operator value and add it to the tree. Then, I alternate the operator and go for a deeper recursion level. If the character is 'T', then I create a node with value "True", add it to the tree and continue scanning. If the character is 'F', then I create a node with the value "False", add it to the tree and continue scanning. Finally, if the character is ')', then I return to one level up of the recursion.

At the end, I will have the expression tree completed. Now, all I need to do is a simple evaluation for the tree using basic recursive function.

Below is my C++ code:

#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++;
    }
}

Landloper

Answer 2

Scan the string from left to right. Every time you see a left parenthesis, add a new entry to a stack structure. When you see a right parenthesis, pop the top-most entry on the stack, evaluate it to T or F, pop the stack again, and append the computed value to the popped term. Continue until the end of the string, at which point you will have a string of T and F, and you evaluate it.

To evaluate a string of Ts and Fs, return T if all are T, and F otherwise. So we have...

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"

Or something like that should do it (EDIT: in fact, this does not correctly answer the question, even as asked; see the comments. Leaving this alone since it still gets one going in the right direction). Note that you could just have one function, evaluate, that does what evaluate2 does, but after the first loop, and only to subexpr. This avoids going through the unnecessary copy that would entail, but you'd have less code the other way.

Valerivaleria

you don't need stack if you use a recursive function – Kinship

This looks clear and reasonable. I will try it and let you know. Thanks. – Landloper

More importantly, the evaluation rule used by evaluate2 is incorrect. The OP seems to have misunderstood the original problem statement -- see the page he linked to. – Electroanalysis

@TravelingSalesman Actually, there is a problem with my pseudocode... I never do a logical "or", only "and". It shouldn't be too hard to fix that, however... at least this shows you how to handle the stack. – Valerivaleria

Answer 3

After having looked at the original problem, I think you have misunderstood it.

This question is about an AND/OR tree where the nodes at the deepest level are AND nodes. The logical operatives at the other nodes are determined by this factor - we do not know if they are AND or OR nodes initially, we're only given that the nodes at the deepest level are AND nodes - so the nodes at the next higher level are OR nodes, and the next higher level are AND nodes, and so and so on... the logical operatives interchange between different depths of the tree. This will become clear if you look at the sample AND/OR tree they have provided.

The way I'd approach this problem is to first figure out the logical connective for the root node. This can be done with a single scan over the expression and keeping track of the number of parentheses. Note that each () corresponds to a new node in the tree (the next level of the tree). For an example, consider the expression:

((F(TF))(TF))

When you walk across this expression, first we encounter 3 opening parentheses, 2 closing, 1 opening and then finally 2 closing. If you take the maximum number of parentheses that were open at any given time during this walk, it'll be the maximum depth of this AND/OR tree (3 in the above example).

So what does this mean? If the depth of the tree is odd, then the root node is an AND node, otherwise the root is an OR node (because the connectives alternate).

Once you know the connective of the root node, you can evaluate this expression using a simple stack based machine. We need to keep in mind that every time we open or close a parentheses, we need to flip the connective. Here's how the above expression gets evaluated:

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

Notice that the bullet indicates where we are at the expression (like top of the stack). Then we proceed like below:

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•)

So you get the final answer as F. This has some relation to shift-reduce parsing but the reductions in this case depend on the current depth of the AST we're operating at. I hope you'll be able to translate this idea into code (you'll need a stack and a global variable for keeping track of the current logical operative in force).

Finally, thank you for introducing that site. You might also like this site.

Toback

Thanks alot for your help. I will translate it to a code and let you know. – Landloper

I believe that the root node is always an AND, the next level is OR, the next level is AND, and so on. – Electroanalysis

@AlexD: In the input section of the problem, it says The trees at the deepest level are AND-trees. May be they just wanted to make the problem harder... – Toback

That's just referring to the sample tree which is shown in the problem page. If you carefully read the definition of a "conjunctive normal form" expression, it's not defined in terms of the bottom level of the tree. – Electroanalysis

Answer 4

From reading the problem description at the site you linked to, I think you may have misunderstood the problem. Whether you need to "logical AND" or "logical OR" the terms depends on how many levels down you are from the root node.

You can easily solve this problem by parsing the expression into a syntax tree, and then walking the tree recursively, evaluating each sub-expression until you get back up to the root node.

Electroanalysis

I agree with you that the solution can be done by converting the expression into a tree. And then easily evaluating that tree. However, my question is, what's the algorithm for constructing that tree? This is my original question. – Landloper

@TravelingSalesman: That's usual parser construction. You have to think of the grammar of the expressions (will need left-recursion elimination as well in this case) and then code a parser according to that grammar. May be Alex will update his answer with this information. – Toback

Thanks. I will consider your advice. The problem itself is giving a hint for constructing a tree in order to solve the problem. – Landloper