fork download 
  1. #ifndef AST_HPP
  2. #define AST_HPP
  3.  
  4. #include <cmath>
  5. #include <memory>
  6.  
  7. #define override
  8.  
  9. typedef double number;
  10.  
  11. struct node_base
  12. {
  13. 	virtual number evaluate() const = 0;
  14. 	virtual ~node_base() {}
  15. };
  16.  
  17. struct node_value : node_base
  18. {
  19. 	node_value(number value)
  20. 		: value_(value)
  21. 	{}
  22.  
  23. 	virtual number evaluate() const override
  24. 	{
  25. 		return value_;
  26. 	}
  27.  
  28. private:
  29. 	number value_;
  30. };
  31.  
  32. template <typename BinaryOperator>
  33. struct node_binary_operator : node_base
  34. {
  35. 	node_binary_operator(std::unique_ptr<node_base> left, std::unique_ptr<node_base> right)
  36. 		: left_(std::move(left)), right_(std::move(right))
  37. 	{}
  38.  
  39. 	virtual number evaluate() const override
  40. 	{
  41. 		return BinaryOperator()(left_->evaluate(), right_->evaluate());
  42. 	}
  43.  
  44. private:
  45. 	std::unique_ptr<node_base> left_, right_;
  46. };
  47.  
  48. struct power
  49. {
  50. 	number operator () (number a, number b) const
  51. 	{
  52. 		return std::pow(a, b);
  53. 	}
  54. };
  55.  
  56. typedef node_binary_operator<std::plus      <number>> node_add;
  57. typedef node_binary_operator<std::minus     <number>> node_sub;
  58. typedef node_binary_operator<std::multiplies<number>> node_mul;
  59. typedef node_binary_operator<std::divides   <number>> node_div;
  60. typedef node_binary_operator<power> node_pow;
  61.  
  62. #endif // AST_HPP
  63.  
  64. #ifndef MAKE_UNIQUE_HPP
  65. #define MAKE_UNIQUE_HPP
  66.  
  67. #include <memory>
  68. #include <utility>
  69.  
  70. template <typename T, typename... Args>
  71. std::unique_ptr<T> make_unique(Args&&... args)
  72. {
  73. 	return std::unique_ptr<T>(new T(std::forward<Args>(args)...));
  74. }
  75.  
  76. #endif // MAKE_UNIQUE_HPP
  77.  
  78. #ifndef PARSER_HPP
  79. #define PARSER_HPP
  80.  
  81. //#include "ast.hpp"
  82. //#include "make_unique.hpp"
  83.  
  84. template <char Symbol, typename NodeType>
  85. struct operator_left;
  86.  
  87. template <char Symbol, typename NodeType>
  88. struct operator_right;
  89.  
  90. template <typename... Operators>
  91. struct operator_group;
  92.  
  93. template <typename... Groups>
  94. struct operator_table;
  95.  
  96. template <typename LeftNextParser, typename RightNextParser, typename... Parsers>
  97. struct operator_parser;
  98.  
  99. template <typename LeftNextParser, typename RightNextParser>
  100. struct operator_parser<LeftNextParser, RightNextParser>
  101. {
  102. 	static bool parse(char const*&, std::unique_ptr<node_base>&)
  103. 	{
  104. 		return false;
  105. 	}
  106. };
  107.  
  108. template <typename LeftNextParser, typename RightNextParser, typename NextParser, char Symbol, typename NodeType, typename... Operators>
  109. bool operator_parse_helper(char const*& string, std::unique_ptr<node_base>& result)
  110. {
  111. 	if(*string == Symbol)
  112. 	{
  113. 		result = make_unique<NodeType>(std::move(result), NextParser::parse(++string));
  114. 		return true;
  115. 	}
  116.  
  117. 	return operator_parser<LeftNextParser, RightNextParser, Operators...>::parse(string, result);
  118. }
  119.  
  120. template <typename LeftNextParser, typename RightNextParser, char Symbol, typename NodeType, typename... Operators>
  121. struct operator_parser<LeftNextParser, RightNextParser, operator_left<Symbol, NodeType>, Operators...>
  122. {
  123. 	static bool parse(char const*& string, std::unique_ptr<node_base>& result)
  124. 	{
  125. 		return operator_parse_helper<LeftNextParser, RightNextParser, LeftNextParser, Symbol, NodeType, Operators...>(string, result);
  126. 	}
  127. };
  128.  
  129. template <typename LeftNextParser, typename RightNextParser, char Symbol, typename NodeType, typename... Operators>
  130. struct operator_parser<LeftNextParser, RightNextParser, operator_right<Symbol, NodeType>, Operators...>
  131. {
  132. 	static bool parse(char const*& string, std::unique_ptr<node_base>& result)
  133. 	{
  134. 		return operator_parse_helper<LeftNextParser, RightNextParser, RightNextParser, Symbol, NodeType, Operators...>(string, result);
  135. 	}
  136. };
  137.  
  138. template <typename Skipper, typename EndParser, typename NextParser, typename... Groups>
  139. struct operator_group_parser;
  140.  
  141. template <typename Skipper, typename EndParser, typename NextParser, typename... GroupParsers, typename... Groups>
  142. struct operator_group_parser<Skipper, EndParser, NextParser, operator_group<GroupParsers...>, Groups...>
  143. {
  144. 	static std::unique_ptr<node_base> parse(char const*& string)
  145. 	{
  146. 		std::unique_ptr<node_base> result = NextParser::parse(string);
  147.  
  148. 		do Skipper::skip(string);
  149. 		while(operator_parser<NextParser, operator_group_parser<Skipper, EndParser, NextParser, operator_group<GroupParsers...>>, GroupParsers...>::parse(string, result));
  150.  
  151. 		return result;
  152. 	}
  153. };
  154.  
  155. template <typename Skipper, typename EndParser, typename Table>
  156. struct operator_table_parser
  157. {
  158. 	static std::unique_ptr<node_base> parse(char const*& string)
  159. 	{
  160. 		return EndParser::parse(string);
  161. 	}
  162. };
  163.  
  164. template <typename Skipper, typename EndParser, typename Group, typename... Groups>
  165. struct operator_table_parser<Skipper, EndParser, operator_table<Group, Groups...>>
  166. {
  167. 	static std::unique_ptr<node_base> parse(char const*& string)
  168. 	{
  169. 		return operator_group_parser<Skipper, EndParser, operator_table_parser<Skipper, EndParser, operator_table<Groups...>>, Group>::parse(string);
  170. 	}
  171. };
  172.  
  173. template <typename Skipper, typename EndParser, typename Table>
  174. std::unique_ptr<node_base> parse(char const*& string)
  175. {
  176. 	return operator_table_parser<Skipper, EndParser, Table>::parse(string);
  177. }
  178.  
  179. #endif // PARSER_HPP
  180.  
  181. #include <cctype>
  182. #include <cstdlib>
  183. #include <functional>
  184. #include <iostream>
  185. #include <memory>
  186. #include <stdexcept>
  187. #include <string>
  188. #include <utility>
  189.  
  190. //#include "ast.hpp"
  191. //#include "parser.hpp"
  192.  
  193. struct parse_error : std::runtime_error
  194. {
  195. 	parse_error(std::string const& what)
  196. 		: runtime_error(what)
  197. 	{}
  198. };
  199.  
  200. struct whitespace_skipper
  201. {
  202. 	static void skip(char const*& string)
  203. 	{
  204. 		while(std::isspace(*string))
  205. 			++string;
  206. 	}
  207. };
  208.  
  209. std::unique_ptr<node_base> parse_number(char const*& string)
  210. {
  211. 	return make_unique<node_value>(std::strtod(string, const_cast<char**>(&string)));
  212. }
  213.  
  214. std::unique_ptr<node_base> parse_binary_expression(char const*& string);
  215.  
  216. struct binary_operator_parser
  217. {
  218. 	static std::unique_ptr<node_base> parse(char const*& string);
  219. };
  220.  
  221. struct primary_expression_parser
  222. {
  223. 	static std::unique_ptr<node_base> parse(char const*& string)
  224. 	{
  225. 		whitespace_skipper::skip(string);
  226.  
  227. 		if(*string == '(')
  228. 		{
  229. 			auto ast = binary_operator_parser::parse(++string);
  230. 			whitespace_skipper::skip(string);
  231.  
  232. 			if(*string != ')')
  233. 				throw parse_error("expected closing '(' here: " + std::string(string));
  234.  
  235. 			++string;
  236. 			return ast;
  237. 		}
  238.  
  239. 		return parse_number(string);
  240. 	}
  241. };
  242.  
  243. typedef operator_table
  244. <
  245. 	operator_group
  246. 	<
  247. 		operator_left<'+', node_add>,
  248. 		operator_left<'-', node_sub>
  249. 	>,
  250. 	operator_group
  251. 	<
  252. 		operator_left<'*', node_mul>,
  253. 		operator_left<'/', node_div>
  254. 	>,
  255. 	operator_group
  256. 	<
  257. 		operator_right<'^', node_pow>
  258. 	>
  259. > operators;
  260.  
  261. std::unique_ptr<node_base> binary_operator_parser::parse(char const*& string)
  262. {
  263. 	return ::parse<whitespace_skipper, primary_expression_parser, operators>(string);
  264. }
  265.  
  266. std::unique_ptr<node_base> parse(char const* string)
  267. {
  268. 	auto ast = binary_operator_parser::parse(string);
  269.  
  270. 	if(*string)
  271. 		throw parse_error("unexpected character here: " + std::string(string));
  272.  
  273. 	return ast;
  274. }
  275.  
  276. int main()
  277. {
  278. 	for(std::string line; std::getline(std::cin, line);)
  279. 		try
  280. 		{
  281. 			auto ast = parse(line.c_str());
  282. 			std::cout << ast->evaluate() << '\n';
  283. 		}
  284.  
  285. 		catch(parse_error const& e)
  286. 		{
  287. 			std::cout << e.what() << '\n';
  288. 		}
  289. }
  290.  
Success #stdin #stdout 0s 3032KB
comments (?)
stdin 
1+1
(3+4)*5
3*4^3
2/4-3
stdout 
2
35
192
-2.5
https://ideone.com/si1fy
language:
C++14 (gcc 8.3)
created:
13 years ago
visibility:
secret

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!