我有一个想要评估的逻辑表达式。表达式可以嵌套，由T(True)或F(False)和括号组成。括号"("的意思是"逻辑或"。彼此相邻的两个项TF(或彼此相邻的任何其他两个组合)应为AND(逻辑AND)。
例如，表达式：
((TFT)T) = true
我需要一个算法来解决这个问题。我想先将表达式转换为析取或连接范式，然后我就可以很容易地评估表达式了。然而，我找不到一个能使表达式正常化的算法。有什么建议吗？非常感谢。
问题陈述可在此处找到：https://icpcarchive.ecs.baylor.edu/index.php?option=com_onlinejudge&项目ID=2&类别＝378&page=show_problem&问题=2967
编辑：我误解了问题的一部分。在给定的逻辑表达式中，AND/OR运算符与每个括号"("交替出现。如果我们要用树来表示表达式，那么AND/OR操作符取决于子树的深度级别。然而，最初假设最深级别的树是AND树。我的任务是通过构造树来评估给定的表达式。感谢您提供以下答案，这些答案澄清了问题的正确要求。
从左到右扫描字符串。每次看到左括号时，都要向堆栈结构中添加一个新条目。当您看到右括号时，弹出堆栈上最顶部的条目，将其求值为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"
或者应该这样做(编辑：事实上，即使被问到了，这也不能正确回答问题；请参阅评论。不要管它，因为它仍然会让人朝着正确的方向前进)。请注意，您可以只有一个函数evaluate，它执行evaluate2的操作，但在第一个循环之后，并且仅用于子xpr。这样可以避免进行不必要的复制，但如果采用其他方式，代码会更少。
看过最初的问题后，我认为您误解了它。
这个问题是关于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的当前深度。我希望您能够将这个想法转化为代码(您需要一个堆栈和一个全局变量来跟踪当前有效的逻辑操作)。
最后，感谢您介绍该网站。你可能也喜欢这个网站。
从您链接到的网站上的问题描述来看，我认为您可能误解了这个问题。是否需要"逻辑AND"或"逻辑or"，这些术语取决于从根节点向下的级别。
通过将表达式解析为语法树，然后递归遍历树，评估每个子表达式，直到返回到根节点，可以很容易地解决这个问题。
我使用与前面提到的技术不同的技术解决了这个问题。我得到了在线系统法官的认可。
在计算出树的第一层的运算符后(感谢@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++;
}
}