Что такое хорошая структура данных для обработки уравнений булевой алгебры?
Я создаю программу, которая будет вычислять значения истинности для уравнения булевой алгебры. Мне нужно найти хорошую структуру данных, которая сможет правильно обрабатывать порядок операций уравнения, включающего AND, OR, NOT, а также круглые скобки. Уравнение будет введено пользователем.
Решение
Любые объекты типа «порядок работы» обычно хранятся в деревья. Это будет выглядеть так:
- Сначала вы обрабатываете текстовое представление, находя элементы с наивысшим приоритетом
- Каждое простое утверждение (
true OR falseнапример) будет помещен в узел - Вы могли бы иметь разные типы узлов для разных операций
- Сами узлы могут быть вставлены в другие узлы, чтобы сделать сложные заявления
Окончательное представление дерева может выглядеть примерно так:
OR
___|__
| |
true AND
___|___
| |
false NOT
|
true
Это будет представлять собой заявление:
true OR (false AND NOT true)
Другие решения
Бинарное дерево является ответом здесь.
Скажи, что у тебя есть выражение A and B or C, то представление, которое вы ищете, будет выглядеть так:
or
/ \
and C
/ \
A B
Обратите внимание, что дерево уже кодирует правила приоритета.
Простое решение будет выглядеть так:
class tree_node
{
public:
virtual ~tree_node() = default;
virtual bool evaluate() = 0;
};
class false_literal_node : public tree_node
{
bool evaluate() override
{
return false;
}
};
// Same goes for `true` literal...
class variable_node : public tree_node
{
bool evaluate() override
{
return value;
}
bool value;
};
class conjunction_node : public tree_node
{
bool evaluate() override
{
return lhs->evaluate() && rhs->evaluate();
}
std::unique_ptr<tree_node> lhs;
std::unique_ptr<tree_node> rhs;
};
Вы поняли идею …
Оценка выражения будет состоять в том, чтобы проанализировать его (что даст вам дерево) и затем вызвать evaluate на корню.