c++ - 如何使用树 C++ 评估 bool 语句

Question

我有一个类似(x1 & x2) || 的语句(x3 || !x4)。 我会把这个声明变成一棵树。 问题是如何生成 true、false 值并将其分配给 x 变量并获取此语句的所有输出？

我们有 *T 作为树根和所有树函数。树也定义为链表树。

Answer 1

你在追求这样的东西吗？根据您实际创建和操作树的方式，您可能希望查看内存管理；它在示例中是基本的。您可能还想为输出添加调试标志。

#include <string>
#include <vector>
#include <iostream>

class Variable
{
public:
     Variable(const std::string& name = "Un-named", bool value = false)
         : name_(name)
     {}
     void setValue(bool val)
     {
         value_ = val;
     }
     bool getValue() const
     {
         return value_;
     }
     const std::string& getName() const { return name_;}
     void setName(const std::string& name)  { name_ = name;}
private:
    std::string name_;
    bool value_;
};



class NodeAbc
{
public:
    virtual bool getValue() const = 0;
    virtual std::ostream& operator<<(std::ostream& os) const = 0;
    virtual ~NodeAbc() = 0;
};

NodeAbc::~NodeAbc() { }

std::ostream& operator<<(std::ostream& os, const NodeAbc& rhs)
{
    return rhs << os;
}

class NodeAtom : public NodeAbc
{
public:
    NodeAtom(const Variable* atom)
        : v_(atom)
    {}
    // Default copy OK for Atom.
    virtual bool getValue() const { return v_->getValue();}
    virtual std::ostream& operator<<(std::ostream& os) const
    {
        return os << v_->getName();
    }
private:
    // Not owned, so no free in destructor;
    const Variable* v_;
};

class UnaryOpAbc
{
public:
    // No virtual destructor - stateless type
    virtual bool eval(bool lhs) const = 0;
    virtual  std::string getName() const = 0;

};

class Not : public UnaryOpAbc
{
public:
    virtual bool eval(bool lhs) const { return !lhs;}
    virtual std::string getName() const { return "!";}
};

class BinaryOpAbc
{
public:
        // No virtual destructor - stateless type
    virtual bool eval(bool lhs, bool rhs) const = 0;
    virtual std::string getName() const = 0;
};

class And : public BinaryOpAbc
{
public:
    virtual bool eval(bool lhs, bool rhs) const{ return lhs && rhs;}
    virtual std::string getName() const { return "&&";}
};

class Or : public BinaryOpAbc
{
public:
    virtual bool eval(bool lhs, bool rhs) const{ return lhs || rhs;}
    virtual  std::string getName()const { return "||";}
};


struct Operators
{
    static And and;
    static Or or;
    static Not not;
};

And Operators::and;
Or Operators::or;
Not Operators::not;

class NodeBinary : public NodeAbc
{
public:
    NodeBinary(NodeAbc* lhs, NodeAbc* rhs, const BinaryOpAbc& op )
        : lhs_(lhs),
        rhs_(rhs),
        op_(op)
    {}

    virtual ~NodeBinary()
    {
        delete lhs_;
        delete rhs_;
    }
    virtual bool getValue() const { return op_.eval( lhs_->getValue(), rhs_->getValue());}
    virtual std::ostream& operator<<(std::ostream& os) const
    {
        return os << "(" << *lhs_ << " " << op_.getName() << " " << *rhs_<< " )";
    }

private:
    // No copy;
    NodeBinary(const NodeBinary& other);

    NodeAbc* lhs_;
    NodeAbc* rhs_;
    const BinaryOpAbc& op_;
};

class NodeUnary : public NodeAbc
{
public:
    NodeUnary(NodeAbc* lhs, const UnaryOpAbc& op )
        : lhs_(lhs),
        op_(op)
    {}
    virtual ~NodeUnary()
    {
        delete lhs_;        
    }
    virtual bool getValue() const { return op_.eval( lhs_->getValue());}
    virtual std::ostream& operator<<(std::ostream& os) const
    {
        return os << op_.getName() << *lhs_;
    }
private:
    // No copy.
    NodeUnary(const NodeUnary& other);
    NodeAbc* lhs_;
    const UnaryOpAbc& op_;
};

int main(int argc, _TCHAR* argv[])
{
    std::vector<Variable> variables(4);

    Variable* x1 = &(variables[0] = Variable("x1", true));
    Variable* x2 = &(variables[1] = Variable("x2", true));
    Variable* x3 = &(variables[2] = Variable("x3", true));
    Variable* x4 = &(variables[3] = Variable("x4", true));

    NodeAbc* x1AndX2 = new NodeBinary( new NodeAtom(x1), new NodeAtom(x2), Operators::and);
    NodeAbc* notX4 = new NodeUnary( new NodeAtom(x4),  Operators::not);
    NodeAbc* x3OrNotX4 = new NodeBinary( new NodeAtom(x3),notX4 , Operators::or);
    NodeAbc* root = new NodeBinary(x1AndX2, x3OrNotX4, Operators::or);

    std::cout << * root << "\t" << root->getValue() << std::endl;

    x2->setValue(false);
    x3->setValue(false);

    std::cout << * root << "\t" << root->getValue() << std::endl;

    delete root;

    return 0;
}