c++ - 什么是处理布尔代数方程的好数据结构？

Question

我正在创建一个程序来计算布尔代数方程的真值。我需要找到一个好的数据结构，它能够正确处理涉及 AND、OR、NOT 和括号的方程的运算顺序。公式将由用户输入。

Answer 1

任何类型的“操作顺序”对象通常都保存在树中。它看起来像这样：

• 您首先处理文本表示，找到最高优先级的项目
• 每个简单的语句（true OR false例如）将被放入一个节点
• 您可以为不同的操作使用不同类型的节点
• 节点本身可以​​插入到其他节点中，以进行复杂的语句

最终的树表示可能最终看起来像这样：

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

这将代表以下声明：

true OR (false AND NOT true)

Answer 2

二叉树就是这里的答案。

假设您有 expression 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根。