fork download
copy 
  1. #include <iostream>
  2. #include <iomanip>
  3. #include <unordered_set>
  4. #include <memory>
  5. #include <sstream>
  6. #include <algorithm>
  7. #include <functional>
  8. #include <cctype>
  9. #include <iterator>
  10. #include <stdexcept>
  11.  
  12. namespace MemoryManagement
  13. {
  14.       template<typename type, typename allocator_t = std::allocator<type> >
  15.       class Allocator
  16.       {
  17.             std::unordered_set<type*> mSet;
  18.             allocator_t mAllocator;
  19.  
  20.       public:
  21.  
  22.             type* allocate(type const& val = type());
  23.  
  24.             ~Allocator();
  25.       };
  26.  
  27.       template<typename type, typename allocator_t>
  28.       type* Allocator<type, allocator_t>::allocate(type const& val)
  29.       {
  30.             type* rval = mAllocator.allocate(1);
  31.             mAllocator.construct(rval, val);
  32.             mSet.insert(rval);
  33.             return rval;
  34.       }
  35.  
  36.       template<typename type, typename allocator_t>
  37.       Allocator<type, allocator_t>::~Allocator()
  38.       {
  39.             for(auto iter(mSet.begin());iter != mSet.end();++iter)
  40.             {
  41.                   mAllocator.destroy(*iter);
  42.                   mAllocator.deallocate(*iter, 1);
  43.             }
  44.  
  45.             mSet.clear();
  46.       }
  47.  
  48.       template<typename type, typename allocator_t = std::allocator<type> >
  49.       type* allocate(type const& val = type())
  50.       {
  51.             static Allocator<type, allocator_t> all;
  52.             return all.allocate(val);
  53.       }
  54. }
  55.  
  56. namespace TermLexer
  57. {
  58. 	struct Object
  59. 	{
  60. 		virtual ~Object();
  61.  
  62. 		enum class type
  63. 		{
  64. 			Real,
  65. 			Operator
  66. 		} const mObjectType;
  67.  
  68. 		Object(type);
  69.  
  70. 		bool is(type a)
  71. 		{
  72. 			return a == mObjectType;
  73. 		}
  74. 	};
  75.  
  76. 	Object::~Object() {}
  77.  
  78. 	Object::Object(Object::type a):
  79. 	mObjectType(a) {}
  80.  
  81. 	struct Real : public Object
  82.       {
  83.             typedef long double real_t;
  84.  
  85.             real_t mNumber;
  86.  
  87.             Real(real_t);
  88.       };
  89.  
  90.       struct Operator : public Object
  91.       {
  92.             enum operator_type
  93.             {
  94.                   plus,
  95.                   minus,
  96.                   multiply,
  97.                   divide,
  98.                   power,
  99.                   openBrace,
  100.                   closeBrace,
  101.             } mOperatorType;
  102.  
  103.             static const std::string operatorChar;
  104.  
  105.             Operator(operator_type);
  106.       };
  107.  
  108.       Operator::operator_type fromChar(char const a)
  109.       {
  110.             return static_cast<Operator::operator_type>(Operator::operatorChar.find(a));
  111.       }
  112.  
  113.       char toChar(Operator::operator_type a)
  114.       {
  115.             return Operator::operatorChar[a];
  116.       }
  117.  
  118.       const std::string Operator::operatorChar("+-*/e()");
  119.  
  120. 	Real::Real(Real::real_t t):
  121. 	Object(Object::type::Real),
  122. 	mNumber(t) {}
  123.  
  124. 	Operator::Operator(Operator::operator_type t):
  125. 	Object(Object::type::Operator),
  126. 	mOperatorType(t) {}
  127.  
  128.  
  129. 	    struct parseException : public std::logic_error
  130. 	    {
  131. 	          parseException(std::string const&);
  132. 	    };
  133.  
  134.       namespace Parser
  135.       {
  136.             std::vector<Object*> parseTerm(std::string const&);
  137.             Real::real_t solveTerm(std::vector<Object*>);
  138.       }
  139.  
  140. 	parseException::parseException(std::string const& w):
  141. 	std::logic_error(w) {}
  142.  
  143. 	std::vector<Object*> TermLexer::Parser::parseTerm(std::string const& str)
  144. 	{
  145. 	      std::vector<Object*> rval;
  146. 	      size_t comma(0);
  147. 	      bool parsingInt(false);
  148. 	      Real::real_t current(0);
  149.  
  150. 	      for(auto c(str.begin());c != str.end();++c)
  151. 	      {
  152. 	            if(std::string(Operator::operatorChar).find(*c) != std::string::npos)
  153. 	            {
  154. 	                  if(parsingInt)
  155. 	                        rval.push_back(MemoryManagement::allocate<Real>(current));
  156. 	                  rval.push_back(MemoryManagement::allocate<Operator>(fromChar(*c)));
  157. 	                  comma = current = parsingInt = 0;
  158. 	            }
  159. 	            else if(std::isdigit(*c) || *c == '.')
  160. 	            {
  161. 	                  if(*c == '.')
  162. 	                        ++comma;
  163. 	                  else if(!parsingInt)
  164. 	                        current = *c - '0';
  165. 	                  else if(!comma)
  166. 	                        current = current * 10 + *c - '0';
  167. 	                  else
  168. 	                        current += (*c - '0') / (Real::real_t)std::pow(10, comma++);
  169.  
  170. 	                  parsingInt = true;
  171. 	            }
  172. 	            else if(*c != ' ')///Skip
  173. 	                  throw parseException("Invalid Character in Term!");
  174. 	      }
  175.  
  176. 	      if(parsingInt)
  177. 	            rval.push_back(MemoryManagement::allocate<Real>(current));
  178.  
  179. 	      return rval;
  180. 	}
  181.  
  182. 	Real::real_t TermLexer::Parser::solveTerm(std::vector<Object*> objects)
  183. 	{
  184. 	      #define Opiter(x) dynamic_cast<Operator*>(obj_iter[x])
  185. 	      #define Realiter(x) dynamic_cast<Real*>(obj_iter[x])
  186.  
  187. 	      for(auto obj_iter(objects.begin());obj_iter != objects.end();++obj_iter)
  188. 	            if((*obj_iter)->is(Object::type::Operator)
  189. 	            && Opiter(0)->mOperatorType == Operator::operator_type::openBrace)
  190. 	            {
  191. 	                  auto closeBraceiter = obj_iter + 1;
  192. 	                  for(size_t ct(1);ct;++closeBraceiter)
  193. 	                  {
  194. 	                        if(closeBraceiter == objects.end())
  195. 	                              throw parseException("An open brace wasn't closed!");
  196. 	                        else if((*closeBraceiter)->is(Object::type::Operator))
  197. 	                              switch(dynamic_cast<Operator*>(*closeBraceiter)->mOperatorType)
  198. 	                              {
  199. 	                                    case Operator::operator_type::closeBrace:
  200. 	                                          --ct;
  201. 	                                    break;
  202. 	                                    case Operator::operator_type::openBrace:
  203. 	                                          ++ct;
  204. 	                              }
  205. 	                  }
  206.  
  207. 	                  std::vector<Object*> braceEnclosedObjects(obj_iter + 1, closeBraceiter - 1);
  208. 	                  Real::real_t res(solveTerm(braceEnclosedObjects));
  209. 	                  auto before = obj_iter - 1;
  210. 	                  objects.erase(obj_iter, closeBraceiter);
  211. 	                  objects.insert(before + 1, MemoryManagement::allocate<Real>(Real(res)));
  212. 	                  obj_iter = before;
  213. 	            }
  214.  
  215. 	      auto computeUnaryOperator = [&](Operator::operator_type op_Type, std::function<void(Real&)> process)
  216. 	      {
  217. 	            for(auto obj_iter(objects.begin());obj_iter != objects.end();++obj_iter)
  218. 	                  if((*obj_iter)->is(Object::type::Operator)
  219. 	                  && Opiter(0)->mOperatorType == op_Type)
  220. 	                  {
  221. 	                        if(obj_iter + 1 == objects.end()
  222. 	                        || !obj_iter[1]->is(Object::type::Real))
  223. 	                              throw parseException("An unary Operator must occur before a real number!");
  224. 	                        else if(Opiter(0)->mOperatorType == op_Type
  225. 	                             && (obj_iter == objects.begin()
  226. 	                              || obj_iter[-1]->is(Object::type::Operator)))
  227. 	                        {
  228. 	                              process(*Realiter(1));
  229. 	                              objects.erase(obj_iter);
  230. 	                        }
  231. 	                  }
  232. 	      };
  233.  
  234. 	      auto computeOperator = [&](Operator::operator_type op_Type1, std::function<void(Real&, Real const&)> process1,
  235. 	                                 Operator::operator_type op_Type2  = static_cast<Operator::operator_type>(-1), std::function<void(Real&, Real const&)> process2 = [](Real& r, Real const& r2){})
  236. 	      {
  237. 	            for(auto obj_iter(objects.begin());obj_iter != objects.end();++obj_iter)
  238. 	                  if((*obj_iter)->is(Object::type::Operator))
  239. 	                  {
  240. 	                        if(obj_iter + 1 == objects.end()
  241. 	                        || !obj_iter[1]->is(Object::type::Real)
  242. 	                        || obj_iter == objects.begin()
  243. 	                        || !obj_iter[-1]->is(Object::type::Real))
  244. 	                              throw parseException("Invalid use of binary operator!");
  245.  
  246. 	                        if(Opiter(0)->mOperatorType == op_Type1)
  247. 	                              process1(*Realiter(-1), *Realiter(1));
  248. 	                        else if(Opiter(0)->mOperatorType == op_Type2)
  249. 	                              process2(*Realiter(-1), *Realiter(1));
  250. 	                        else continue;
  251.  
  252. 	                        auto tmpiter = obj_iter - 1;
  253. 	                        objects.erase(obj_iter + 1);
  254. 	                        objects.erase(obj_iter);
  255. 	                        obj_iter = tmpiter;
  256. 	                  }
  257. 	      };
  258.  
  259.  
  260. 	      computeUnaryOperator(Operator::operator_type::minus, [&](Real& r){r.mNumber = -r.mNumber;});
  261. 	      computeUnaryOperator(Operator::operator_type::plus, [&](Real& r){});
  262.  
  263. 	      computeOperator(Operator::power, [&](Real& r, Real const& r2){r.mNumber = std::pow(r.mNumber, r2.mNumber);});
  264.  
  265. 	      computeOperator(Operator::multiply, [](Real& r, Real const& r2){r.mNumber *= r2.mNumber;},
  266. 	                      Operator::divide, [](Real& r, Real const& r2)
  267. 	                      {
  268. 	                            if(!r2.mNumber)
  269. 	                               throw std::logic_error("It is not allowed to divide by zero!");
  270. 	                            r.mNumber /= r2.mNumber;
  271. 	                      });
  272.  
  273. 	      computeOperator(Operator::plus, [](Real& r, Real const& r2){r.mNumber += r2.mNumber;},
  274. 	                      Operator::minus,[](Real& r, Real const& r2){r.mNumber -= r2.mNumber;});
  275.  
  276. 	      return dynamic_cast<Real*>(objects.front())->mNumber;
  277. 	}
  278. }
  279.  
  280. int main() try
  281. {
  282.      auto res = TermLexer::Parser::solveTerm(TermLexer::Parser::parseTerm("10*5e-7"));
  283.  
  284.       std::cout << res << '\n';
  285. }
  286. catch(TermLexer::parseException& e)
  287. {
  288.       std::cerr << "A parse error occured (corresponding to your syntax):\n"
  289.                 << e.what() << '\n';
  290. }
  291. catch(std::exception &e)
  292. {
  293.       std::cerr << "\nAn error occured:\n"
  294.                 << e.what() << "!\n";
  295. }
  296. catch(...)
  297. {
  298.       std::cerr << "\nAn (!)unknown(!) error occured! Please check your syntax and/or report as bug!\n";
  299. }
  300.  
Success #stdin #stdout 0s 2980KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
0.000128
https://ideone.com/O77pp
language:
C++14 (gcc 8.3)
created:
13 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!