Алгоритм оценки вложенного логического выражения
У меня есть логическое выражение, которое я хотел бы оценить. Выражение может быть вложенным и состоит из 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. Моя задача - оценить данное выражение, возможно, путем построения дерева. Спасибо за ответы ниже, которые разъяснили правильное требование проблемы.
4 ответа
Я решил эту проблему, используя другую технику, чем упомянутые. И я получил это Принято судьей системы онлайн.
После выяснения оператора на первом уровне дерева (спасибо @Asiri Rathnayake за его идею) я рекурсивно создаю дерево выражений. Во время строительства я сканирую строку. Если символ "("), то я создаю узел с текущим значением оператора и добавляю его в дерево. Затем я чередую оператор и иду на более глубокий уровень рекурсии. Если символ "Т", тогда я создаю узел со значением "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++;
}
}
Сканирование строки слева направо. Каждый раз, когда вы видите левую скобку, добавьте новую запись в структуру стека. Когда вы видите правильную скобку, вставьте самую верхнюю запись в стек, оцените ее как 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, но после первого цикла и только для субэкспресса. Это позволяет избежать ненужных копий, но в противном случае у вас будет меньше кода.
Изучив исходную проблему, я думаю, вы ее неправильно поняли.
Этот вопрос о 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, Это имеет некоторое отношение к анализу сдвига-уменьшения, но сокращения в этом случае зависят от текущей глубины AST, с которой мы работаем. Я надеюсь, что вы сможете перевести эту идею в код (вам понадобится стек и глобальная переменная для отслеживания текущего логического действия в силе).
Наконец, спасибо за представление этого сайта. Вам также может понравиться этот сайт.
Из прочтения описания проблемы на сайте, на который вы ссылаетесь, я думаю, что вы, возможно, неправильно поняли проблему. Требуется ли вам "логическое И" или "логическое ИЛИ", условия зависят от того, на сколько уровней вы находитесь ниже корневого узла.
Вы можете легко решить эту проблему, анализируя выражение в синтаксическом дереве, а затем рекурсивно обходя дерево, оценивая каждое подвыражение, пока не вернетесь к корневому узлу.