通过真值树解析布尔表达式，eg:A&B|C

第一步：求出一个表达式的truth tree

1.生成真值表

2.根据真值表生成真值树（合并短路产生相同的两个子树）

/****************************************
 * File: truth_tree.h
 *
 *A&B|C truth_table
  0  0  1          1
  0  1  1          1
  1  0  1          1
  1  1  0          1
  1  1  1          1
 *
 * Complete Binary Tree
 *                  -1(root)
                /                \
A:           0                      1
          /    \                  /   \
B:      0        1             0         1
         \        \             \      /  \
C:        1         1             1    0   1
 *
 *
 * After merge
 *  *                -1(root)
                /               \
A:           0                      1
          /                       /   \
B:      -1                      0       1
         \                      \      /
C:        1                       1   -1
 *
 *
 * *****************************************/

#ifndef UTIL_TRUTH_TREE_H
#define UTIL_TRUTH_TREE_H

#include <memory>
#include <vector>

namespace util {

struct TruthTreeNode
{
    int8_t                         value;
    std::shared_ptr<TruthTreeNode> left;
    std::shared_ptr<TruthTreeNode> right;

    explicit TruthTreeNode(int8_t in_v):value(in_v),left(nullptr),right(nullptr){}
    TruthTreeNode(const TruthTreeNode&)            = delete;
    TruthTreeNode(TruthTreeNode&&)                 = delete;
    TruthTreeNode& operator=(const TruthTreeNode&) = delete;
    TruthTreeNode& operator=(TruthTreeNode&&)      = delete;
};

using truth_table_t = std::vector<std::vector<bool>>;

class TruthTree
{
public: //Constructors and destructor
    TruthTree():m_root(nullptr){}

    TruthTree(const TruthTree& tree)
    {
        m_root = copy_tree(tree.root());
    }

    TruthTree& operator=(const TruthTree& tree)
    {
        if (this == &tree)
            return *this;

        m_root = copy_tree(tree.root());
        return *this;
    }

    TruthTree(TruthTree&&)                 = delete;
    TruthTree& operator=(TruthTree&&)      = delete;
    ~TruthTree()                           = default;

public: //interface   
    void initialize_tree(const truth_table_t& truth_table);

    const std::shared_ptr<TruthTreeNode>& root() const
    {
        return m_root;
    }

    bool empty() const
    {
        if (nullptr == m_root)
            return true;

        if (nullptr == m_root->left && nullptr == m_root->right)
            return true;

        return false;
    }

private: //static member method
    static std::shared_ptr<TruthTreeNode> copy_tree(const std::shared_ptr<TruthTreeNode>& parent_node_ptr);
    static std::shared_ptr<TruthTreeNode> table_to_tree(const truth_table_t& truth_table);
    static std::shared_ptr<TruthTreeNode> try_add_new_child_node(bool element, std::shared_ptr<TruthTreeNode> parent_node_ptr);
    static std::shared_ptr<TruthTreeNode> add_new_child_node(bool element, std::shared_ptr<TruthTreeNode> parent_node_ptr);
    static bool compare_tree(const std::shared_ptr<TruthTreeNode> left, const std::shared_ptr<TruthTreeNode> right);
    static void merge_child_trees(std::shared_ptr<TruthTreeNode> parent_node_ptr);

private: //member data
    std::shared_ptr<TruthTreeNode> m_root;
};

}

#endif //UTIL_TRUTH_TREE_H

View Code