Что такое хорошая структура данных для обработки уравнений булевой алгебры?

Я создаю программу, которая будет вычислять значения истинности для уравнения булевой алгебры. Мне нужно найти хорошую структуру данных, которая сможет правильно обрабатывать порядок операций уравнения, включающего AND, OR, NOT, а также круглые скобки. Уравнение будет введено пользователем.

3

Решение

Любые объекты типа «порядок работы» обычно хранятся в деревья. Это будет выглядеть так:

  • Сначала вы обрабатываете текстовое представление, находя элементы с наивысшим приоритетом
  • Каждое простое утверждение (true OR false например) будет помещен в узел
  • Вы могли бы иметь разные типы узлов для разных операций
  • Сами узлы могут быть вставлены в другие узлы, чтобы сделать сложные заявления

Окончательное представление дерева может выглядеть примерно так:

     OR
___|__
|    |
true  AND
___|___
|     |
false   NOT
|
true

Это будет представлять собой заявление:

true OR (false AND NOT true)
2

Другие решения

Бинарное дерево является ответом здесь.

Скажи, что у тебя есть выражение 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 на корню.

1

По вопросам рекламы [email protected]