c++ - C ++でブール式からグラフを作成する

Question

並列接続を表し、直列接続を表す(A+(B*C))グラフ構造に変換しようとしています。、、およびがグラフの 3 つのノードである場合:+*n1n2n3

n1持っていedge(A),edge(B)ます。

n2持っていedge(B),edge(C)ます。

n3持っていedge(A),edge(C)ます。

ブール式の変数がエッジになることは知っていますが、グラフの頂点に指定された式からノードを見つける方法がわかりません。

Answer 1

式テンプレートを使用して、式の構文ツリーを生成できます。

class Boolean
{
public:
    Boolean(bool b) : _b( b ) {}

private:
    bool _b;
};

template<typename LHS , typename RHS>
struct parallel
{
    LHS& left;
    RHS& right;  

    parallel(const LHS& _left , const RHS& _right) : left( _left ) , right( _right ) {}
};

template<typename LHS , typename RHS>
struct serie
{
    LHS& first;
    RHS& second;  

    serie(const LHS& _left , const RHS& _right) : first( _left ) , second( _right ) {}
};


/* Boolean vs Boolean parallel expression */
parallel<Boolean,Boolean> operator+(const Boolean& lhs , const Boolean& rhs)
{
    return parallel<Boolean,Boolean>( lhs , rhs );
}

/* Boolean vs Boolean serie expression */
serie<Boolean,Boolean> operator*(const Boolean& lhs , const Boolean& rhs)
{
    return serie<Boolean,Boolean>( lhs , rhs );
}


/* Boolean vs internal node parallel expressions */

template<typename LHS , typename RHS>
parallel<parallel<LHS,RHS>,Boolean> operator+(const parallel<LHS,RHS>& lhs , const Boolean& rhs)
{
    return parallel<parallel<LHS,RHS>,Boolean>( lhs , rhs );
}

template<typename LHS , typename RHS>
parallel<Boolean,parallel<LHS,RHS>> operator+(const Boolean& lhs , const parallel<LHS,RHS>& rhs)
{
    return parallel<Boolean,parallel<LHS,RHS>>( lhs , rhs );
}

template<typename LHS , typename RHS>
parallel<serie<LHS,RHS>,Boolean> operator+(const serie<LHS,RHS>& lhs , const Boolean& rhs)
{
    return parallel<serie<LHS,RHS>,Boolean>( lhs , rhs );
}

template<typename LHS , typename RHS>
parallel<Boolean,serie<LHS,RHS>> operator+(const Boolean& lhs , const serie<LHS,RHS>& rhs)
{
    return parallel<Boolean,serie<LHS,RHS>>( lhs , rhs );
}


/* Boolean vs internal node serie expresssions */

template<typename LHS , typename RHS>
serie<parallel<LHS,RHS>,Boolean> operator*(const parallel<LHS,RHS>& lhs , const Boolean& rhs)
{
    return serie<parallel<LHS,RHS>,Boolean>( lhs , rhs );
}

template<typename LHS , typename RHS>
serie<Boolean,parallel<LHS,RHS>> operator*(const Boolean& lhs , const parallel<LHS,RHS>& rhs)
{
    return serie<Boolean,parallel<LHS,RHS>>( lhs , rhs );
}

template<typename LHS , typename RHS>
serie<serie<LHS,RHS>,Boolean> operator*(const serie<LHS,RHS>& lhs , const Boolean& rhs)
{
    return serie<serie<LHS,RHS>,Boolean>( lhs , rhs );
}

template<typename LHS , typename RHS>
serie<Boolean,serie<LHS,RHS>> operator*(const Boolean& lhs , const serie<LHS,RHS>& rhs)
{
    return serie<Boolean,serie<LHS,RHS>>( lhs , rhs );
}


/* internal node vs internal node parallel expressions */

template<typename LHS1 , typename RHS1 , typename LHS2 , typename RHS2>
parallel<parallel<LHS1,RHS1>,parallel<LHS2,RHS2>> operator+(const parallel<LHS1,RHS1>& lhs , const parallel<LHS2,RHS2>& rhs)
{
    return parallel<parallel<LHS1,RHS1>,parallel<LHS2,RHS2>>( lhs , rhs );
}

template<typename LHS1 , typename RHS1 , typename LHS2 , typename RHS2>
parallel<serie<LHS1,RHS1>,serie<LHS2,RHS2>> operator+(const serie<LHS1,RHS1>& lhs , const serie<LHS2,RHS2>& rhs)
{
    return parallel<serie<LHS1,RHS1>,serie<LHS2,RHS2>>( lhs , rhs );
}

template<typename LHS1 , typename RHS1 , typename LHS2 , typename RHS2>
parallel<parallel<LHS1,RHS1>,serie<LHS2,RHS2>> operator+(const parallel<LHS1,RHS1>& lhs , const serie<LHS2,RHS2>& rhs)
{
    return parallel<parallel<LHS1,RHS1>,serie<LHS2,RHS2>>( lhs , rhs );
}

template<typename LHS1 , typename RHS1 , typename LHS2 , typename RHS2>
parallel<serie<LHS1,RHS1>,parallel<LHS2,RHS2>> operator+(const serie<LHS1,RHS1>& lhs , const parallel<LHS2,RHS2>& rhs)
{
    return parallel<serie<LHS1,RHS1>,parallel<LHS2,RHS2>>( lhs , rhs );
}


/* internal node vs internal node serie expressions */

template<typename LHS1 , typename RHS1 , typename LHS2 , typename RHS2>
serie<parallel<LHS1,RHS1>,parallel<LHS2,RHS2>> operator*(const parallel<LHS1,RHS1>& lhs , const parallel<LHS2,RHS2>& rhs)
{
    return serie<parallel<LHS1,RHS1>,parallel<LHS2,RHS2>>( lhs , rhs );
}

template<typename LHS1 , typename RHS1 , typename LHS2 , typename RHS2>
serie<serie<LHS1,RHS1>,serie<LHS2,RHS2>> operator*(const serie<LHS1,RHS1>& lhs , const serie<LHS2,RHS2>& rhs)
{
    return serie<serie<LHS1,RHS1>,serie<LHS2,RHS2>>( lhs , rhs );
}

template<typename LHS1 , typename RHS1 , typename LHS2 , typename RHS2>
serie<parallel<LHS1,RHS1>,serie<LHS2,RHS2>> operator*(const parallel<LHS1,RHS1>& lhs , const serie<LHS2,RHS2>& rhs)
{
    return serie<parallel<LHS1,RHS1>,serie<LHS2,RHS2>>( lhs , rhs );
}

template<typename LHS1 , typename RHS1 , typename LHS2 , typename RHS2>
serie<serie<LHS1,RHS1>,parallel<LHS2,RHS2>> operator*(const serie<LHS1,RHS1>& lhs , const parallel<LHS2,RHS2>& rhs)
{
    return serie<serie<LHS1,RHS1>,parallel<LHS2,RHS2>>( lhs , rhs );
}

その使用例は次のとおりです。

int main()
{
    Boolean a(true) , b(false) , c(true);
    auto result = (a+b)*(a+c); //serie(parallel(a,b),parallel(a,c))
}