嵌套逻辑表达式的计算方法

Question

我有一个逻辑表达式,我想评估.表达式可以嵌套,由T(True)或F(False)和括号组成.括号"("表示"逻辑或".彼此旁边的两个术语TF(或彼此旁边的任何其他两个组合)应该是ANDED(逻辑与).

例如,表达式:

((TFT)T) = true

我需要一个算法来解决这个问题.我想到首先将表达式转换为析取或连接的正规形式,然后我可以轻松地评估表达式.但是,我找不到一个规范化表达式的算法.有什么建议？谢谢.

问题陈述可以在这里找到:https: //icpcarchive.ecs.baylor.edu/index.php？option = com_onlinejudge&Itemid = 2&category = 378&page = show_problem&issueble = 2967

编辑:我误解了部分问题.在给定的逻辑表达式中,AND/OR运算符与每个括号"(")交替.如果我们要通过树表示表达式,则AND/OR运算符取决于子树的深度级别.但是,它是最初认为最深层的树是AND树.我的任务是通过构建树来评估给定的表达式.感谢下面的答案,澄清了问题的正确要求.

Answer 1

我使用与上述技术不同的技术解决了这个问题。并且我得到了在线系统评委的认可。

在弄清楚树的第一层的运算符之后（感谢@Asiri Rathnayake 的想法），我递归地构建了表达式树。在构建过程中，我扫描了字符串。如果字符是“(”，那么我使用当前运算符值创建一个节点并将其添加到树中。然后，我交替运算符并进行更深的递归级别。如果字符是“T”，那么我创建一个值为“True”的节点，将其添加到树中并继续扫描。如果字符是“F”，则创建一个值为“False”的节点，将其添加到树中并继续扫描。最后，如果字符是“)”，然后我返回到递归的上一层。

最后，我将完成表达式树。现在，我需要做的就是使用基本递归函数对树进行简单的评估。

下面是我的 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++;
    }
}