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

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


c++ user-input data-structures mathematical-expressions boolean-algebra
person user3208209    schedule 10.03.2014    source источник
comment
Когда я работал на калькуляторе в школе, мы преобразовывали ввод в RPN, а затем вычисляли, используя стек.   -  person clcto    schedule 10.03.2014
comment
Вы можете анализировать и оценивать с помощью парсера рекурсивного спуска и без явной структуры данных, такой как дерево или стек. .   -  person Jim Mischel    schedule 11.03.2014

Ответы (2)


arrow_upward
2
arrow_downward

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

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

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

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

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

true OR (false AND NOT true)
person Damien Black    schedule 10.03.2014

arrow_upward
1
arrow_downward

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

Допустим, у вас есть выражение 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 в корне.

person Community    schedule 10.03.2014