fork(6) download
copy 
  1. // TransformAST.cpp : Defines the entry point for the console application.
  2. //
  3.  
  4. #include <boost/spirit/include/qi.hpp>
  5. #include <boost/fusion/include/adapt_struct.hpp>
  6.  
  7. #include <boost/variant/recursive_wrapper.hpp>
  8.  
  9. namespace qi = boost::spirit::qi;
  10.  
  11.  
  12.  
  13. // Abstract data type
  14.  
  15. struct op_or {};
  16. struct op_and {};
  17. struct op_imp {};
  18. struct op_iff {};
  19. struct op_not {};
  20.  
  21. namespace ast
  22. {
  23. 	typedef std::string var;
  24. 	template <typename tag> struct binop;
  25. 	template <typename tag> struct unop;
  26.  
  27. 	enum class expr_type { var = 0, not_, and_, or_, imp, iff };
  28. 	typedef boost::variant<var,
  29. 		boost::recursive_wrapper<unop <op_not> >,
  30. 		boost::recursive_wrapper<binop<op_and> >,
  31. 		boost::recursive_wrapper<binop<op_or> >,
  32. 		boost::recursive_wrapper<binop<op_imp> >,
  33. 		boost::recursive_wrapper<binop<op_iff> >
  34. 	> expr;
  35.  
  36. 	expr_type get_expr_type(const expr& expression)
  37. 	{
  38. 		return static_cast<expr_type>(expression.which());
  39. 	}
  40.  
  41. 	template <typename tag> struct binop
  42. 	{
  43. 		expr oper1, oper2;
  44. 	};
  45.  
  46. 	template <typename tag> struct unop
  47. 	{
  48. 		expr oper1;
  49. 	};
  50.  
  51. 	struct printer : boost::static_visitor<void>
  52. 	{
  53. 		printer(std::ostream& os) : _os(os) {}
  54. 		std::ostream& _os;
  55. 		mutable bool first{ true };
  56.  
  57. 		//
  58. 		void operator()(const ast::var& v) const { _os << v; }
  59.  
  60.  
  61. 		void operator()(const ast::binop<op_and>& b) const { print(" and ", b.oper1, b.oper2); }
  62. 		void operator()(const ast::binop<op_or>& b) const { print(" or ", b.oper1, b.oper2); }
  63. 		void operator()(const ast::binop<op_iff>& b) const { print(" iff ", b.oper1, b.oper2); }
  64. 		void operator()(const ast::binop<op_imp>& b) const { print(" imp ", b.oper1, b.oper2); }
  65.  
  66. 		void print(const std::string& op, const ast::expr& l, const ast::expr& r) const
  67. 		{
  68. 			_os << "(";
  69. 			boost::apply_visitor(*this, l);
  70. 			_os << op;
  71. 			boost::apply_visitor(*this, r);
  72. 			_os << ")";
  73. 		}
  74.  
  75. 		void operator()(const ast::unop<op_not>& u) const
  76. 		{
  77. 			_os << "not(";
  78. 			boost::apply_visitor(*this, u.oper1);
  79. 			_os << ")";
  80. 		}
  81. 	};
  82.  
  83. 	std::ostream& operator<<(std::ostream& os, const expr& e)
  84. 	{
  85. 		boost::apply_visitor(printer(os), e); return os;
  86. 	}
  87.  
  88. 	expr operator!(const expr& e)
  89. 	{
  90. 		return unop<op_not>{e};
  91. 	}
  92.  
  93. 	expr operator||(const expr& l, const expr& r)
  94. 	{
  95. 		return binop<op_or>{l, r};
  96. 	}
  97.  
  98. 	expr operator&&(const expr& l, const expr& r)
  99. 	{
  100. 		return binop<op_and>{l, r};
  101. 	}
  102.  
  103. }
  104.  
  105. BOOST_FUSION_ADAPT_TPL_STRUCT(
  106. 	(Tag),
  107. 	(ast::binop) (Tag),
  108. 	(ast::expr, oper1)
  109. 	(ast::expr, oper2)
  110. )
  111.  
  112. BOOST_FUSION_ADAPT_TPL_STRUCT(
  113. 	(Tag),
  114. 	(ast::unop) (Tag),
  115. 	(ast::expr, oper1)
  116. )
  117.  
  118.  
  119. // Grammar rules
  120.  
  121. template <typename It, typename Skipper = qi::space_type>
  122. struct parser : qi::grammar<It, ast::expr(), Skipper>
  123. {
  124. 	parser() : parser::base_type(expr_)
  125. 	{
  126. 		using namespace qi;
  127. 		const as<ast::binop<op_iff> > as_iff = {};
  128. 		const as<ast::binop<op_imp> > as_imp = {};
  129. 		const as<ast::binop<op_or> > as_or = {};
  130. 		const as<ast::binop<op_and> > as_and = {};
  131. 		const as<ast::unop<op_not> > as_not = {};
  132.  
  133. 		expr_ = iff_.alias();
  134.  
  135. 		iff_ = as_iff[imp_ >> "iff" >> iff_] | imp_;
  136. 		imp_ = as_imp[or_ >> "imp" >> imp_] | or_;
  137. 		or_ = as_or[and_ >> "or" >> or_] | and_;
  138. 		and_ = as_and[not_ >> "and" >> and_] | not_;
  139. 		not_ = as_not["not" > simple] | simple;
  140.  
  141. 		simple = (('(' > expr_ > ')') | var_);
  142. 		var_ = qi::lexeme[+alpha];
  143.  
  144. 		BOOST_SPIRIT_DEBUG_NODE(expr_);
  145. 		BOOST_SPIRIT_DEBUG_NODE(iff_);
  146. 		BOOST_SPIRIT_DEBUG_NODE(imp_);
  147. 		BOOST_SPIRIT_DEBUG_NODE(or_);
  148. 		BOOST_SPIRIT_DEBUG_NODE(and_);
  149. 		BOOST_SPIRIT_DEBUG_NODE(not_);
  150. 		BOOST_SPIRIT_DEBUG_NODE(simple);
  151. 		BOOST_SPIRIT_DEBUG_NODE(var_);
  152. 	}
  153.  
  154. private:
  155. 	qi::rule<It, ast::var(), Skipper> var_;
  156. 	qi::rule<It, ast::expr(), Skipper> not_, and_, or_, imp_, iff_, simple, expr_;
  157. };
  158.  
  159. template <typename Transform>
  160. struct ast_helper : boost::static_visitor<ast::expr>
  161. {
  162.  
  163. 	template <typename Tag>
  164. 	ast::expr pass_through(const ast::binop<Tag>& op) const
  165. 	{
  166. 		return ast::binop<Tag>{recurse(op.oper1), recurse(op.oper2)};
  167. 	}
  168.  
  169. 	template <typename Tag>
  170. 	ast::expr pass_through(const ast::unop<Tag>& op) const
  171. 	{
  172. 		return ast::unop<Tag>{recurse(op.oper1)};
  173. 	}
  174.  
  175. 	ast::expr pass_through(const ast::var& variable) const
  176. 	{
  177. 		return variable;
  178. 	}
  179.  
  180. 	ast::expr recurse(const ast::expr& expression) const
  181. 	{
  182. 		return boost::apply_visitor(Transform{}, expression);
  183. 	}
  184.  
  185. 	struct left_getter:boost::static_visitor<ast::expr>
  186. 	{
  187. 		template< template<class> class Op,typename Tag>
  188. 		ast::expr operator()(const Op<Tag>& op) const
  189. 		{
  190. 			return op.oper1;
  191. 		}
  192.  
  193. 		ast::expr operator()(const ast::var&) const
  194. 		{
  195. 			return{};//throw something?
  196. 		}
  197. 	};
  198.  
  199.  
  200. 	ast::expr left(const ast::expr& expression) const
  201. 	{
  202. 		return boost::apply_visitor(left_getter{}, expression);
  203. 	}
  204.  
  205. 	ast::expr child0(const ast::expr& expression) const
  206. 	{
  207. 		return left(expression);
  208. 	}
  209.  
  210. 	struct right_getter :boost::static_visitor<ast::expr>
  211. 	{
  212. 		template<typename Tag>
  213. 		ast::expr operator()(const ast::binop<Tag>& op) const
  214. 		{
  215. 			return op.oper2;
  216. 		}
  217.  
  218. 		template<typename Expr>
  219. 		ast::expr operator()(const Expr&) const
  220. 		{
  221. 			return{};//throw something?
  222. 		}
  223. 	};
  224.  
  225. 	ast::expr right(const ast::expr& expression) const
  226. 	{
  227. 		return boost::apply_visitor(right_getter{}, expression);
  228. 	}
  229.  
  230. };
  231.  
  232. struct eliminate_imp : ast_helper<eliminate_imp>
  233. {
  234. 	template <typename Op>
  235. 	ast::expr operator()(const Op& op) const
  236. 	{
  237. 		return pass_through(op);
  238. 	}
  239.  
  240. 	ast::expr operator()(const ast::binop<op_imp>& imp) const
  241. 	{
  242. 		return !recurse(imp.oper1) || recurse(imp.oper2);
  243. 	}
  244.  
  245. 	ast::expr operator()(const ast::expr& expression) const
  246. 	{
  247. 		return recurse(expression);
  248. 	}
  249. };
  250.  
  251. struct eliminate_iff : ast_helper<eliminate_iff>
  252. {
  253. 	template <typename Op>
  254. 	ast::expr operator()(const Op& op) const
  255. 	{
  256. 		return pass_through(op);
  257. 	}
  258.  
  259. 	ast::expr operator()(const ast::binop<op_iff>& imp) const
  260. 	{
  261. 		return (recurse(imp.oper1) || !recurse(imp.oper2)) && (!recurse(imp.oper1) || recurse(imp.oper2));
  262. 	}
  263.  
  264. 	ast::expr operator()(const ast::expr& expression) const
  265. 	{
  266. 		return recurse(expression);
  267. 	}
  268. };
  269.  
  270. struct distribute_nots : ast_helper<distribute_nots>
  271. {
  272. 	template <typename Op>
  273. 	ast::expr operator()(const Op& op) const
  274. 	{
  275. 		return pass_through(op);
  276. 	}
  277.  
  278. 	ast::expr operator()(const ast::unop<op_not>& not_) const
  279. 	{
  280. 		switch (ast::get_expr_type(not_.oper1)) //There is probably a better solution
  281. 		{
  282. 		case ast::expr_type::and_:
  283. 			return recurse(!recurse(left(not_.oper1))) || recurse(!recurse(right(not_.oper1)));
  284.  
  285. 		case ast::expr_type::or_:
  286. 			return recurse(!recurse(left(not_.oper1))) && recurse(!recurse(right(not_.oper1)));
  287.  
  288. 		case ast::expr_type::not_:
  289. 			return recurse(child0(not_.oper1));
  290. 		default:
  291. 			return pass_through(not_);
  292. 		}
  293. 	}
  294.  
  295. 	ast::expr operator()(const ast::expr& expression) const
  296. 	{
  297. 		return recurse(expression);
  298. 	}
  299. };
  300.  
  301. struct any_and_inside : boost::static_visitor<bool>
  302. {
  303. 	any_and_inside(const ast::expr& expression) :expression(expression) {}
  304. 	const ast::expr& expression;
  305.  
  306. 	bool operator()(const ast::var&) const
  307. 	{
  308. 		return false;
  309. 	}
  310.  
  311. 	template <typename Tag>
  312. 	bool operator()(const ast::binop<Tag>& op) const
  313. 	{
  314. 		return boost::apply_visitor(*this, op.oper1) || boost::apply_visitor(*this, op.oper2);
  315. 	}
  316.  
  317. 	bool operator()(const ast::binop<op_and>&) const
  318. 	{
  319. 		return true;
  320. 	}
  321.  
  322. 	template<typename Tag>
  323. 	bool operator()(const ast::unop<Tag>& op) const
  324. 	{
  325. 		return boost::apply_visitor(*this, op.oper1);
  326. 	}
  327.  
  328.  
  329. 	explicit operator bool() const
  330. 	{
  331. 		return boost::apply_visitor(*this, expression);
  332. 	}
  333.  
  334. };
  335.  
  336. struct distribute_ors : ast_helper<distribute_ors>
  337. {
  338. 	template <typename Op>
  339. 	ast::expr operator()(const Op& op) const
  340. 	{
  341. 		return pass_through(op);
  342. 	}
  343.  
  344. 	ast::expr operator()(const ast::binop<op_or>& or_) const
  345. 	{
  346. 		if (ast::get_expr_type(or_.oper1) == ast::expr_type::and_)
  347. 		{
  348. 			return recurse(recurse(left(or_.oper1)) || recurse(or_.oper2)) 
  349. 				&& recurse(recurse(right(or_.oper1)) || recurse(or_.oper2));
  350. 		}
  351. 		else if (ast::get_expr_type(or_.oper2) == ast::expr_type::and_)
  352. 		{
  353. 			return recurse(recurse(or_.oper1) || recurse(left(or_.oper2)))
  354. 				&& recurse(recurse(or_.oper1) || recurse(right(or_.oper2)));
  355. 		}
  356. 		else if (any_and_inside( or_ ))
  357. 		{
  358. 			return recurse(recurse(or_.oper1) || recurse(or_.oper2));
  359. 		}
  360. 		else
  361. 		{
  362. 			return pass_through(or_);
  363. 		}
  364. 	}
  365.  
  366. 	ast::expr operator()(const ast::expr& expression) const
  367. 	{
  368. 		return recurse(expression);
  369. 	}
  370.  
  371. };
  372.  
  373. ast::expr to_CNF(const ast::expr& expression)
  374. {
  375. 	return distribute_ors()(distribute_nots()(eliminate_iff()(eliminate_imp()(expression))));
  376. }
  377.  
  378.  
  379.  
  380.  
  381. // Test some examples in main and check the order of precedence
  382.  
  383. int main()
  384. {
  385. 	for (auto& input : std::list<std::string>{
  386.  
  387. 		// Test the order of precedence
  388. 		"(a and b) imp ((c and d) or (a and b));",
  389. 		"a and b iff (c and d or a and b);",
  390. 		"a and b imp (c and d or a and b);",
  391. 		"not a or not b;",
  392. 		"a or b;",
  393. 		"not a and b;",
  394. 		"not (a and b);",
  395. 		"a or b or c;",
  396. 		"aaa imp bbb iff ccc;",
  397. 		"aaa iff bbb imp ccc;",
  398.  
  399.  
  400. 		// Test elimination of equivalences
  401. 		"a iff b;",
  402. 		"a iff b or c;",
  403. 		"a or b iff b;",
  404. 		"a iff b iff c;",
  405.  
  406. 		// Test elimination of implications
  407. 		"p imp q;",
  408. 		"p imp not q;",
  409. 		"not p imp not q;",
  410. 		"p imp q and r;",
  411. 		"p imp q imp r;"
  412. 	})
  413. 	{
  414. 		auto f(std::begin(input)), l(std::end(input));
  415. 		parser<decltype(f)> p;
  416.  
  417. 		try
  418. 		{
  419. 			ast::expr result;
  420. 			bool ok = qi::phrase_parse(f, l, p > ';', qi::space, result);
  421.  
  422. 			if (!ok)
  423. 				std::cerr << "invalid input\n";
  424. 			else
  425. 			{
  426. 				std::cout << "original: " << result << "\n";
  427. 				std::cout << "CNF: " << to_CNF(result) << "\n";
  428. 			}
  429.  
  430. 		}
  431. 		catch (const qi::expectation_failure<decltype(f)>& e)
  432. 		{
  433. 			std::cerr << "expectation_failure at '" << std::string(e.first, e.last) << "'\n";
  434. 		}
  435.  
  436. 		if (f != l) std::cerr << "unparsed: '" << std::string(f, l) << "'\n";
  437. 	}
  438.  
  439. 	return 0;
  440. }
  441.  
  442.  
  443.  
Success #stdin #stdout 0.01s 3560KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
original: ((a and b) imp ((c and d) or (a and b)))
CNF: ((((not(a) or not(b)) or (c or a)) and ((not(a) or not(b)) or (c or b))) and (((not(a) or not(b)) or (d or a)) and ((not(a) or not(b)) or (d or b))))
original: ((a and b) iff ((c and d) or (a and b)))
CNF: ((((a or (not(c) or not(d))) and (a or (not(a) or not(b)))) and ((b or (not(c) or not(d))) and (b or (not(a) or not(b))))) and ((((not(a) or not(b)) or (c or a)) and ((not(a) or not(b)) or (c or b))) and (((not(a) or not(b)) or (d or a)) and ((not(a) or not(b)) or (d or b)))))
original: ((a and b) imp ((c and d) or (a and b)))
CNF: ((((not(a) or not(b)) or (c or a)) and ((not(a) or not(b)) or (c or b))) and (((not(a) or not(b)) or (d or a)) and ((not(a) or not(b)) or (d or b))))
original: (not(a) or not(b))
CNF: (not(a) or not(b))
original: (a or b)
CNF: (a or b)
original: (not(a) and b)
CNF: (not(a) and b)
original: not((a and b))
CNF: (not(a) or not(b))
original: (a or (b or c))
CNF: (a or (b or c))
original: ((aaa imp bbb) iff ccc)
CNF: (((not(aaa) or bbb) or not(ccc)) and ((aaa or ccc) and (not(bbb) or ccc)))
original: (aaa iff (bbb imp ccc))
CNF: (((aaa or bbb) and (aaa or not(ccc))) and (not(aaa) or (not(bbb) or ccc)))
original: (a iff b)
CNF: ((a or not(b)) and (not(a) or b))
original: (a iff (b or c))
CNF: (((a or not(b)) and (a or not(c))) and (not(a) or (b or c)))
original: ((a or b) iff b)
CNF: (((a or b) or not(b)) and ((not(a) or b) and (not(b) or b)))
original: (a iff (b iff c))
CNF: ((((a or (not(b) or b)) and (a or (not(b) or not(c)))) and ((a or (c or b)) and (a or (c or not(c))))) and ((not(a) or (b or not(c))) and (not(a) or (not(b) or c))))
original: (p imp q)
CNF: (not(p) or q)
original: (p imp not(q))
CNF: (not(p) or not(q))
original: (not(p) imp not(q))
CNF: (p or not(q))
original: (p imp (q and r))
CNF: ((not(p) or q) and (not(p) or r))
original: (p imp (q imp r))
CNF: (not(p) or (not(q) or r))
https://ideone.com/LByavz
language:
C++14 (gcc 8.3)
created:
9 years ago
visibility:
public

Share or Embed source code

Discover > Sphere Engine API

The brand new service which powers Ideone!

Discover > IDE Widget

Widget for compiling and running the source code in a web browser!