ツリーを使用してブールステートメントを評価する方法++

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

ツリーにはキーと値のペアが格納されている必要があります。つまり、x1だけでなく値（TrueまたはFalse）も格納されます。このようにしてツリーを作成したら、ツリーをたどって結果を見つけることができます。

Answer 3

ツリーに加えて、シンボルテーブルが必要です。
シンボルテーブルの仕事は、値に変数をマップすることです。そして、

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 

ルートノートで評価を呼び出すときは、現在のシンボルテーブルを評価するだけで結果を戻す必要があります。