aGrUM  0.13.2
formula_inl.h
Go to the documentation of this file.
1 /***************************************************************************
2  * Copyright (C) 2005 by Pierre-Henri WUILLEMIN et Christophe GONZALES *
3  * {prenom.nom}_at_lip6.fr *
4  * *
5  * This program is free software; you can redistribute it and/or modify *
6  * it under the terms of the GNU General Public License as published by *
7  * the Free Software Foundation; either version 2 of the License, or *
8  * (at your option) any later version. *
9  * *
10  * This program is distributed in the hope that it will be useful, *
11  * but WITHOUT ANY WARRANTY; without even the implied warranty of *
12  * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the *
13  * GNU General Public License for more details. *
14  * *
15  * You should have received a copy of the GNU General Public License *
16  * along with this program; if not, write to the *
17  * Free Software Foundation, Inc., *
18  * 59 Temple Place - Suite 330, Boston, MA 02111-1307, USA. *
19  ***************************************************************************/
20 
22 
23 namespace gum {
24 
25  // ==========================================================================
26  // === Class FormulaPart ===
27  // ==========================================================================
28 
29 
30  INLINE
32  switch (character) {
33  case '+':
34  case '-':
35  case '*':
36  case '/': {
37  return true;
38  }
39 
40  case '_': {
41  return false;
42  }
43  case '^': {
44  return false;
45  }
46 
47  default: { GUM_ERROR(OperationNotAllowed, "A - not an operator"); }
48  }
49  }
50 
51  INLINE
53  switch (character) {
54  case '_': {
55  return false;
56  }
57  default: { return !isLeftAssociative(); }
58  }
59  }
60 
61  INLINE
63  switch (character) {
64  case '+':
65  case '-': {
66  return 2;
67  }
68 
69  case '*':
70  case '/': {
71  return 3;
72  }
73 
74  case '^': {
75  return 4;
76  }
77 
78  case '_': {
79  return 5;
80  }
81 
82  default: { GUM_ERROR(OperationNotAllowed, "B - not an operator"); }
83  }
84  }
85 
86  INLINE
87  size_t FormulaPart::argc() const {
88  switch (type) {
89  case OPERATOR: {
90  return __operator_argc();
91  }
92 
93  case FUNCTION: {
94  return __function_argc();
95  }
96 
97  default: {
98  GUM_ERROR(OperationNotAllowed, "expecting a function or an operator");
99  }
100  }
101  }
102 
103  INLINE
105  switch (character) {
106  case '_': {
107  return (size_t)1;
108  }
109  case '+':
110  case '-':
111  case '*':
112  case '/':
113  case '^': {
114  return (size_t)2;
115  }
116 
117  default: { GUM_ERROR(OperationNotAllowed, "C - not an operator"); }
118  }
119  }
120 
121  INLINE
123  switch (function) {
124  case FormulaPart::token_function::exp: {
125  return 1;
126  }
127  case FormulaPart::token_function::log: {
128  return 1;
129  }
130  case FormulaPart::token_function::ln: {
131  return 1;
132  }
133  case FormulaPart::token_function::pow: {
134  return 2;
135  }
136  case FormulaPart::token_function::sqrt: {
137  return 1;
138  }
139  // case FormulaPart::token_function::nil: { return "nil"; }
140  default: { GUM_ERROR(OperationNotAllowed, "unknown function"); }
141  }
142  }
143 
145  INLINE
146  double
147  FormulaPart::__operator_eval(const std::vector< FormulaPart >& args) const {
148  switch (character) {
149  case '+': {
150  return args[1].number + args[0].number;
151  }
152 
153  case '-': {
154  return args[1].number - args[0].number;
155  }
156 
157  case '*': {
158  return args[1].number * args[0].number;
159  }
160 
161  case '/': {
162  return args[1].number / args[0].number;
163  }
164 
165  case '^': {
166  return std::pow(args[1].number, args[0].number);
167  }
168 
169  case '_': {
170  return 0 - args[0].number;
171  }
172 
173  default: { GUM_ERROR(OperationNotAllowed, "D - not an operator"); }
174  }
175  }
176 
178  INLINE
179  double
180  FormulaPart::__function_eval(const std::vector< FormulaPart >& args) const {
181  switch (function) {
182  case FormulaPart::token_function::exp: {
183  return std::exp(args[0].number);
184  }
185  case FormulaPart::token_function::log: {
186  return std::log(args[0].number);
187  }
188  case FormulaPart::token_function::ln: {
189  return std::log2(args[0].number);
190  }
191  case FormulaPart::token_function::pow: {
192  return std::pow(args[1].number, args[0].number);
193  }
194  case FormulaPart::token_function::sqrt: {
195  return std::sqrt(args[0].number);
196  }
197  // case FormulaPart::token_function::nil: { return "nil"; }
198  default: { GUM_ERROR(OperationNotAllowed, "unknown function"); }
199  }
200  }
201 
203  INLINE
204  FormulaPart FormulaPart::eval(const std::vector< FormulaPart >& args) const {
205  switch (type) {
206  case OPERATOR: {
207  return FormulaPart(token_type::NUMBER, __operator_eval(args));
208  }
209 
210  case FUNCTION: {
211  return FormulaPart(token_type::NUMBER, __function_eval(args));
212  }
213 
214  default: { GUM_ERROR(OperationNotAllowed, "cannot evaluate expression"); }
215  }
216  }
217 
218  // ==========================================================================
219  // === Class Formula ===
220  // ==========================================================================
221 
222 
223  INLINE
224  const std::string& Formula::formula() const { return __formula; }
225 
226  INLINE
227  std::string& Formula::formula() { return __formula; }
228 
229  INLINE
230  void Formula::__push_number(const double& v) {
231  FormulaPart t(FormulaPart::token_type::NUMBER, v);
232  __push_output(t);
233  }
234 
235  INLINE
237  if (__stack.empty()
238  || __stack.top().type != FormulaPart::token_type::OPERATOR) {
239  return false;
240  }
241 
242  if (o.isLeftAssociative() && o.precedence() <= __stack.top().precedence()) {
243  return true;
244  }
245 
246  if (o.isRightAssociative() && o.precedence() < __stack.top().precedence()) {
247  return true;
248  }
249 
250  return false;
251  }
252 
253  INLINE
255  if (__isUnaryOperator(o)) {
256  __push_unaryOperator(o);
257 
258  } else {
259  FormulaPart t(FormulaPart::token_type::OPERATOR, o);
260  __push_operator(t);
261  }
262  }
263 
264  INLINE
266  switch (__last_token.type) {
267  case FormulaPart::token_type::OPERATOR:
268  case FormulaPart::token_type::NIL:
269  case FormulaPart::token_type::ARG_SEP: {
270  return o == '-';
271  }
272 
273  case FormulaPart::token_type::PARENTHESIS: {
274  return (o == '-') && (__last_token.character == '(');
275  }
276 
277  default: { return false; }
278  }
279  }
280 
281  INLINE
283  // Only unary operator is the negative sign -
284  FormulaPart t(FormulaPart::token_type::OPERATOR, '_');
285  __push_operator(t);
286  }
287 
288  INLINE
290  while (__popOperator(t)) {
291  __push_output(__stack.top());
292  __stack.pop();
293  }
294 
295  __push_stack(t);
296  }
297 
298  INLINE
300  FormulaPart t(FormulaPart::token_type::PARENTHESIS, '(');
301  __push_stack(t);
302  }
303 
304  INLINE
306  while ((!__stack.empty()) && (__stack.top().character != '(')) {
307  __push_output(__stack.top());
308  __stack.pop();
309  }
310 
311  if (__stack.empty()) {
312  GUM_ERROR(OperationNotAllowed, "expecting '('");
313 
314  } else if (__stack.top().character != '(') {
315  GUM_ERROR(OperationNotAllowed, "expecting '('");
316  }
317 
318  __stack.pop();
319 
320  if ((!__stack.empty())
321  && __stack.top().type == FormulaPart::token_type::FUNCTION) {
322  __push_output(__stack.top());
323  __stack.pop();
324  }
325  __last_token = FormulaPart(FormulaPart::token_type::PARENTHESIS, ')');
326  }
327 
328  INLINE
330  while (!__stack.empty()) {
331  if (__stack.top().character == '(') {
332  GUM_ERROR(OperationNotAllowed, "expecting ')'");
333  }
334 
335  __push_output(__stack.top());
336  __stack.pop();
337  }
338  }
339 
340  INLINE
341  void
343  std::stack< FormulaPart >& stack) const {
344  std::vector< FormulaPart > args;
345 
346  if (stack.size() < item.argc()) {
347  GUM_ERROR(OperationNotAllowed, "not enought inputs ");
348  }
349 
350  while (item.argc() > args.size()) {
351  args.push_back(stack.top());
352  stack.pop();
353  }
354 
355  stack.push(item.eval(args));
356  }
357 
358  INLINE
360  __output.push_back(t);
361  __last_token = t;
362  }
363 
364  INLINE
366  __stack.push(t);
367  __last_token = t;
368  }
369 
370  INLINE
371  void Formula::__push_function(const std::string& func) {
372  if (func == "exp") {
373  FormulaPart t(FormulaPart::token_type::FUNCTION,
374  FormulaPart::token_function::exp);
375  __push_stack(t);
376 
377  } else if (func == "log") {
378  FormulaPart t(FormulaPart::token_type::FUNCTION,
379  FormulaPart::token_function::log);
380  __push_stack(t);
381 
382  } else if (func == "ln") {
383  FormulaPart t(FormulaPart::token_type::FUNCTION,
384  FormulaPart::token_function::ln);
385  __push_stack(t);
386 
387  } else if (func == "pow") {
388  FormulaPart t(FormulaPart::token_type::FUNCTION,
389  FormulaPart::token_function::pow);
390  __push_stack(t);
391 
392  } else if (func == "sqrt") {
393  FormulaPart t(FormulaPart::token_type::FUNCTION,
394  FormulaPart::token_function::sqrt);
395  __push_stack(t);
396 
397  } else {
398  GUM_ERROR(OperationNotAllowed, "unknown function");
399  }
400  }
401 
402  INLINE
404  while ((!__stack.empty()) && (__stack.top().character != '(')) {
405  __push_output(__stack.top());
406  __stack.pop();
407  }
408 
409  if (__stack.empty() || __stack.top().character != '(') {
410  GUM_ERROR(OperationNotAllowed, "expecting a '('");
411  }
412 
413  __last_token = FormulaPart(FormulaPart::token_type::ARG_SEP, ',');
414  }
415 
416  INLINE
418 
419  INLINE
421  return __variables;
422  }
423 
424  INLINE
425  void Formula::__push_variable(const std::string& var) {
426  if (__variables.exists(var)) {
427  __push_number(__variables[var]);
428 
429  } else {
430  GUM_ERROR(OperationNotAllowed, "unknonw variable");
431  }
432  }
433 
434  INLINE
435  void Formula::__push_identifier(const std::string& ident) {
436  try {
437  __push_function(ident);
438 
439  } catch (OperationNotAllowed&) {
440  try {
441  __push_variable(ident);
442 
443  } catch (OperationNotAllowed&) {
444  GUM_ERROR(OperationNotAllowed, "unknown identifier");
445  }
446  }
447  }
448 
449  // ========================================================================
450  // @name Arithmetic Operators
451  // ========================================================================
452 
453  INLINE
455  return Formula(std::to_string(-1 * a.result()));
456  }
457 
458  INLINE
459  Formula operator+(const Formula& a, const Formula& b) {
460  return Formula(std::to_string(a.result() + b.result()));
461  }
462 
463  INLINE
464  Formula operator-(const Formula& a, const Formula& b) {
465  return Formula(std::to_string(a.result() - b.result()));
466  }
467 
468  INLINE
469  Formula operator*(const Formula& a, const Formula& b) {
470  return Formula(std::to_string(a.result() * b.result()));
471  }
472 
473  INLINE
474  Formula operator/(const Formula& a, const Formula& b) {
475  return Formula(std::to_string(a.result() / b.result()));
476  }
477 
478  INLINE
479  std::string to_string(const Formula& f) { return std::to_string(f.result()); }
480 
481  INLINE
482  std::ostream& operator<<(std::ostream& os, const Formula& f) {
483  os << f.result();
484  return os;
485  }
486 
487 } // namespace gum
void __push_function(const std::string &func)
Push a function in the formula.
Definition: formula_inl.h:371
bool __isUnaryOperator(char o)
Returns true if o is an unary operator.
Definition: formula_inl.h:265
void __push_rightParenthesis()
Push a right parenthesis in the formula.
Definition: formula_inl.h:305
bool __popOperator(FormulaPart o)
Pop the operator in the inner formula&#39;s stack.
Definition: formula_inl.h:236
double result() const
Returns the result of this gum::Formula.
Definition: formula.cpp:295
bool isRightAssociative() const
Returns true if this gum::FormulaPart is right associative.
Definition: formula_inl.h:52
FormulaPart eval(const std::vector< FormulaPart > &args) const
Returns the evaluation of the vector of gum::FormulaPart as arguments of the value stored in this gum...
Definition: formula_inl.h:204
Formula operator+(const Formula &a, const Formula &b)
Definition: formula_inl.h:459
int precedence() const
Returns the precedence priority of the value stored in this gum::FormulaPart.
Definition: formula_inl.h:62
Evaluates a string as a algebraic formula.
Definition: formula.h:271
bool isLeftAssociative() const
Returns true if this gum::FormulaPart is left associative.
Definition: formula_inl.h:31
const std::string & formula() const
Returns the formula.
Definition: formula_inl.h:224
void __finalize()
Finalize the formula and prepare it for evaluation.
Definition: formula_inl.h:329
Headers files for the gum::FormulaPart and gum::Formula classes.
size_t __function_argc() const
Returns the number of arguments expected by the function stored in this gum::FormulaPart.
Definition: formula_inl.h:122
Represents part of a formula.
Definition: formula.h:57
gum is the global namespace for all aGrUM entities
Definition: agrum.h:25
void __reduceOperatorOrFunction(FormulaPart item, std::stack< FormulaPart > &stack) const
Evaluate an operator or function and push its result.
Definition: formula_inl.h:342
double __operator_eval(const std::vector< FormulaPart > &args) const
Returns the evaluation of the vector of gum::FormulaPart as arguments of the value stored in this gum...
Definition: formula_inl.h:147
void __push_number(const double &v)
Push a number in the formula.
Definition: formula_inl.h:230
void __push_identifier(const std::string &ident)
Use this if you don&#39;t know if ident is a function or a variable.
Definition: formula_inl.h:435
std::ostream & operator<<(std::ostream &output, const BayesNet< GUM_SCALAR > &bn)
Prints map&#39;s DAG in output using the Graphviz-dot format.
Definition: BayesNet_tpl.h:573
Formula operator/(const Formula &a, const Formula &b)
Definition: formula_inl.h:474
double __function_eval(const std::vector< FormulaPart > &args) const
Returns the evaluation of the vector of gum::FormulaPart as arguments of the value stored in this gum...
Definition: formula_inl.h:180
size_t argc() const
Returns the number of argument of the function stored in this gum::FormulaPart.
Definition: formula_inl.h:87
std::string to_string(const Formula &f)
Definition: formula_inl.h:479
void __push_variable(const std::string &var)
Push a variable in the formula.
Definition: formula_inl.h:425
Formula operator*(const Formula &a, const Formula &b)
Definition: formula_inl.h:469
token_type type
The token_type stored by this gum::FormulaPart.
Definition: formula.h:66
ListConstIterator< Val >::difference_type operator-(const ListConstIterator< Val > &iter1, const ListConstIterator< Val > &iter2)
For STL compliance, a distance operator.
Definition: list_tpl.h:346
FormulaPart()
Class constructor.
Definition: formula.cpp:82
void __push_stack(FormulaPart t)
Push the gum::FormulaPart in the stack.
Definition: formula_inl.h:365
size_t __operator_argc() const
Returns the number of arguments expected by the operator stored in this gum::FormulaPart.
Definition: formula_inl.h:104
void __push_comma()
Push a comma in the formula.
Definition: formula_inl.h:403
void __push_operator(char o)
Push an operator in the formula.
Definition: formula_inl.h:254
void __push_output(FormulaPart t)
Push the gum::FormulaPart in the output vector.
Definition: formula_inl.h:359
double number
The value stored by this gum::FormulaPart.
Definition: formula.h:75
HashTable< std::string, double > & variables()
Returns the variables used by this gum::Formula.
Definition: formula_inl.h:417
void __push_unaryOperator(char o)
Push an unary operator.
Definition: formula_inl.h:282
char character
The value stored by this gum::FormulaPart.
Definition: formula.h:76
void __push_leftParenthesis()
Push a left parenthesis in the formula.
Definition: formula_inl.h:299
#define GUM_ERROR(type, msg)
Definition: exceptions.h:66