算法评估嵌套逻辑EX pression [英] Algorithm for evaluating nested logical expression

问题描述

我有一个合乎逻辑的EX pression，我想评价。 这位前pression可以嵌套，由T（真）或F（假）和括号。 括号（意为逻辑或。 每个人身边两个方面TF（或每个人的身边其他两个组合），应进行AND（逻辑与）。

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

例如，前pression：

For example, the expression:

((TFT)T) = true

我需要一种算法来解决此问题。我认为首先将前pression以析取或合取范式，然后我可以很容易地评估EX pression。但是，我无法找到一个算法，恢复正常前pression。有什么建议么？谢谢你。

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.

问题描述可以在这里找到： <一href="https://icpcarchive.ecs.baylor.edu/index.php?option=com_onlinejudge&Itemid=2&category=378&page=show_problem&problem=2967" rel="nofollow">https://icpcarchive.ecs.baylor.edu/index.php?option=com_onlinejudge&Itemid=2&category=378&page=show_problem&problem=2967

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

编辑：我误解了问题的一部分。在给定的逻辑EX pression，与/或运营商相间每个括号（如果我们要重新present前pression一棵树，然后和/或运营商通过在该子树的深度水平。不过，最初给这么树木在最深层次是和树。我的任务是通过构造树可能评估给定的前pression。 低于此谢谢你的答案澄清问题的正确的要求。

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.

推荐答案

我使用的是不同的技术提到的那些解决了这个问题。而我得到了它接受了在线系统的法官。

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

搞清楚运营商在树的第一层后（感谢@Asiri拉斯纳亚克他的想法），我递归构建EX pression树。在施工过程中，我扫描的字符串。如果字符'（'，然后我创建了当前运营商值的节点，并把它添加到树中。然后，我交替运营商去进行更深层次的递归级别，如果字符是'T'，然后创建与值的节点真，它如果添加到树，并继续扫描。如果字符'F'，然后创建，其值为假的一个节点，将其添加到树，并继续扫描。最后，字符是'）'，然后我回到递归的上一层。

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.

最后，我将前pression树完成。现在，所有我需要做的是利用基本的递归函数树一个简单的评测。

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.

下面是我的C ++ code：

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

这篇关于算法评估嵌套逻辑EX pression的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！