Как оценить логическое выражение с помощью дерева C ++

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;
}

Answer 2

В дополнение к вашему дереву вам нужна таблица символов.
Работа таблицы символов заключается в сопоставлении переменных со значениями:

typedef std::map<std::string, ValueType>    SymbolTable;
SymbolTable    symbolTable;

Тогда, если мы предположим, что ваше дерево выражений имеет интерфейс, оцененный,Вы просто передаете таблицу символов в качестве параметра для оценки.

class Node
{
    virtual ValueType  evaluated(SymbolTable const& symbols) = 0;
};
class Variable: public Node
{
    std::string name;
    Variable( std::string const& n) : name(n) {};
    virtual ValueType  evaluated(SymbolTable const& symbols)
    {
        return symbols[name]; // looks up the value of the variable in the symbol table.
    }
};
class NotNode: public Node
{
    std::auto_ptr<Node>    child;
    NotNode(std::auto_ptr<Node> x): child(c) {}
    virtual ValueType  evaluated(SymbolTable const& symbols)
    {
         return child->evaluated(symbols).not();  // Assume Value type knows how to not itself.
    }
}
// etc

Когда вы вызываете метод оценки для корневой ноты, вы просто передаете текущую таблицу символов для оценки и должны получить результат обратно.

Answer 3

Ваше дерево должно хранить пары ключ-значение, то есть хранить не только x1, но и его значение (True или False). После того, как вы создадите свое дерево таким образом, вы сможете пройтись по нему, чтобы найти результат.