построение графика из булевого выражения в C++

Question

Я пытаюсь преобразовать (A+(B*C)) в структуру графика, где + представляет собой параллельное соединение, а * представляет собой последовательное соединение. если n1, n2 и n3 являются тремя узлами в графе то:

n1 имеет edge(A),edge(B).

n2 имеет edge(B),edge(C).

n3 имеет edge(A),edge(C).

Я знаю, что переменные в булевом выражении будут ребрами, но я не могу понять, как найти узлы из выражения, данного для вершин графа.

Answer 1

Вы можете использовать expression templates для создания синтаксического дерева выражения:

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