5

我有一个想要评估的逻辑表达式。表达式可以嵌套，由 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&problem=2967

编辑：我误解了部分问题。在给定的逻辑表达式中，AND/OR 运算符与每个括号“(”交替出现。如果我们要用树来表示表达式，那么 AND/OR 运算符取决于子树的深度级别。但是，它是最初考虑到最深层次的树是与树。我的任务是可能通过构建树来评估给定的表达式。感谢下面的答案澄清了问题的正确要求。

4

4 回答 4

3

从左到右扫描字符串。每次看到左括号时，向堆栈结构添加一个新条目。当您看到右括号时，弹出堆栈中最顶部的条目，将其评估为 T 或 F，再次弹出堆栈，并将计算值附加到弹出的项。继续直到字符串的末尾，此时您将获得一个由 T 和 F 组成的字符串，并对其进行评估。

要计算一串 Ts 和 Fs，如果都是 T，则返回 T，否则返回 F。所以我们有...

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"

或者类似的事情应该这样做（编辑：事实上，即使被问到，这也不能正确回答问题；请参阅评论。别管这个了，因为它仍然可以让一个人朝着正确的方向前进）。请注意，您可以只有一个函数评估，它执行评估 2 所做的工作，但在第一个循环之后，并且仅限于 subexpr。这避免了通过不必要的副本，但你有更少的代码。

于 2012-12-06T21:34:35.970 回答
2

在查看了原始问题之后，我认为您误解了它。

这个问题是关于一AND/OR棵树，其中最深层次的节点是AND节点。其他节点的逻辑操作员是由这个因素决定的——我们最初不知道它们是不是AND节点OR，我们只知道最深层次的节点是AND节点——所以下一个更高层次的节点是OR节点，下一个更高级别是AND节点，依此类推……逻辑操作符在树的不同深度之间交换。如果您查看AND/OR他们提供的示例树，这将变得很清楚。

我解决这个问题的方法是首先找出根节点的逻辑连接词。这可以通过对表达式进行一次扫描并跟踪括号的数量来完成。请注意，每个都()对应于树中的一个新节点（树的下一级）。例如，考虑以下表达式：

((F(TF))(TF))

当你走过这个表达式时，首先我们遇到 3 个左括号，2 个右括号，1 个左括号，最后是 2 个右括号。如果您在此步行期间的任何给定时间获取打开的最大括号数，它将是这AND/OR棵树的最大深度（3在上面的示例中）。

那么这是什么意思？如果树的深度是奇数，则根节点是一个AND节点，否则根是一个OR节点（因为连接词是交替的）。

一旦你知道了根节点的连接词，你就可以使用一个简单的基于堆栈的机器来评估这个表达式。我们需要记住，每次打开或关闭括号时，都需要翻转连接词。以下是上述表达式的求值方式：

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

请注意，项目符号表示我们在表达式中的位置（如堆栈顶部）。然后我们继续如下：

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

所以你得到的最终答案是F。这与shift-reduce 解析有一定关系，但这种情况下的减少取决于我们正在操作的 AST 的当前深度。我希望你能够将这个想法转化为代码（你需要一个堆栈和一个全局变量来跟踪当前有效的逻辑操作）。

最后，感谢您介绍该网站。您可能还喜欢这个网站。

于 2012-12-07T00:11:24.753 回答
1

通过阅读您链接到的站点上的问题描述，我认为您可能误解了该问题。您是否需要“逻辑与”或“逻辑或”这些术语取决于您从根节点向下的层数。

您可以通过将表达式解析为语法树来轻松解决此问题，然后递归地遍历树，评估每个子表达式，直到您回到根节点。

于 2012-12-06T21:38:57.063 回答
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++;
    }
}
于 2012-12-26T20:05:15.027 回答