ArithmeticEvaluator.cpp

   1 /*-==============================================================-
   2
   3 file : ArithmeticEvaluator.cpp
   4
   5 creation date : 19/05/2015
   6
   7 author : S. Domas (sdomas@univ-fcomte.fr)
   8
   9 description :
  10
  11 supp. infos : saved in UTF-8 [éè]
  12
  13 -==============================================================-*/
  14 #include "ArithmeticEvaluator.h"
  15 #include <math.h>
  16
  17 ArithmeticEvaluator::ArithmeticEvaluator() {
  18   opMarkers = "+-*/|%"; // | is for euclidan division
  19   varMarkers = "$";
  20   expression = QStringList();
  21   /* CAUTION : function are mandatory using ( ) to encapsulate the operand
  22      since spaces are removed. Thus, an expression like sin 10 will lead to
  23      sin10 after spaces removal, and thus becomes invalid.
  24    */
  25   fctMarkers << "sin" << "cos" << "log10" << "log2" << "log" << "ceil" << "floor" << "round";
  26 }
  27
  28 ArithmeticEvaluator::ArithmeticEvaluator(const QString& _expression) throw(int) {
  29   opMarkers = "+-*/|%"; // | is for euclidan division
  30   varMarkers = "$";
  31   expression = QStringList();
  32   /* CAUTION : function are mandatory using ( ) to encapsulate the operand
  33      since spaces are removed. Thus, an expression like sin 10 will lead to
  34      sin10 after spaces removal, and thus becomes invalid.
  35    */
  36   fctMarkers << "sin" << "cos" << "log10" << "log2" << "log" << "ceil" << "floor" << "round";
  37
  38   try {
  39     setExpression(_expression);
  40   }
  41   catch(int e) {
  42     throw(e);
  43   }
  44 }
  45
  46 void ArithmeticEvaluator::setExpression(const QString& _expression) throw(int) {
  47
  48   setVariableNames(_expression);
  49
  50   try {
  51     convert(_expression);
  52   }
  53   catch(int e) {
  54     throw(e);
  55   }
  56 }
  57
  58 void ArithmeticEvaluator::setVariablesValue(const QHash<QString,double>& _varValues) {
  59   varValues =  _varValues;
  60   /*
  61   QHashIterator<QString,double> iterV(varValues);
  62   while (iterV.hasNext()) {
  63     iterV.next();
  64     cout << "var " << qPrintable(iterV.key()) << " = " << iterV.value() << endl;
  65   }
  66   */
  67 }
  68
  69 void ArithmeticEvaluator::setVariableNames(const QString& _expression) {
  70   varNames.clear();
  71   QRegularExpression re("[$][a-zA-Z0-9_]+");
  72   QRegularExpressionMatchIterator matcher = re.globalMatch(_expression);
  73   while(matcher.hasNext()) {
  74     QRegularExpressionMatch m = matcher.next();
  75     QString var = m.captured(0);
  76     varNames.append(var);
  77   }
  78 }
  79
  80 void ArithmeticEvaluator::print() {
  81   foreach(QString elt, expression) {
  82     cout << qPrintable(elt) << " ";
  83   }
  84   cout << endl;
  85 }
  86
  87 double ArithmeticEvaluator::evalFunction(int indexFunc, double value) {
  88   double res = 0.0;
  89   if (indexFunc == 0) {
  90     res = sin(value);
  91   }
  92   else if (indexFunc == 1) {
  93     res = cos(value);
  94   }
  95   else if (indexFunc == 2) {
  96     res = log10(value);
  97   }
  98   else if (indexFunc == 3) {
  99     res = log2(value);
 100   }
 101   else if (indexFunc == 4) {
 102     res = log(value);
 103   }
 104   else if (indexFunc == 5) {
 105     res = ceil(value);
 106   }
 107   else if (indexFunc == 6) {
 108     res = floor(value);
 109   }
 110   else if (indexFunc == 7) {
 111     res = round(value);
 112   }
 113
 114   return res;
 115 }
 116
 117 double ArithmeticEvaluator::evaluate() throw(int) {
 118   errorMessage = "";
 119   QStack<double> stack;
 120   bool ok;
 121   double value1,value2;
 122   int index = 0;
 123   QChar c;
 124   foreach(QString elt, expression) {
 125     c = elt.at(0);
 126     /* CAUTION :
 127      \x1bn, n must correspond to the order of QString in fctMarkers.
 128      */
 129     if (c == '\x1b') {
 130       value1 = stack.pop();
 131       elt.remove(0,1);
 132       int idFunc = elt.toInt(&ok);
 133       if ((!ok) || (idFunc < 0) || (idFunc >= fctMarkers.size())) throw(-index);
 134       stack.push(evalFunction(idFunc,value1));
 135     }
 136     else if (varMarkers.contains(c)) {
 137       if (!varValues.contains(elt)) {
 138         errorMessage = "cannot find value of ";
 139         errorMessage += qPrintable(elt);
 140         throw(-index);
 141       }
 142       stack.push(varValues.value(elt));
 143     }
 144     else if (opMarkers.contains(c)) {
 145       value2 = stack.pop();
 146       value1 = stack.pop();
 147       if (c == '+') {
 148         stack.push(value1+value2);
 149       }
 150       else if (c == '-') {
 151         stack.push(value1-value2);
 152       }
 153       else if (c == '*') {
 154         stack.push(value1*value2);
 155       }
 156       else if (c == '/') {
 157         stack.push(value1/value2);
 158       }
 159       else if (c == '|') {
 160         int val1 = (int)value1;
 161         int val2 = (int)value2;
 162         stack.push(val1/val2);
 163       }
 164       else if (c == '%') {
 165         int val1 = (int)value1;
 166         int val2 = (int)value2;
 167         stack.push(val1%val2);
 168       }
 169     }
 170     else {
 171       value1 = elt.toDouble(&ok);
 172       if (!ok) throw(-index);
 173       stack.push(value1);
 174     }
 175     index += 1;
 176   }
 177
 178   value1 = stack.pop();
 179   if (!stack.isEmpty()) throw(-1);
 180   return value1;
 181 }
 182
 183 /* NOTE :
 184   expr is of form:
 185   ([ value1 | var1 | func1 | expr1 ] op1 [ value2 | var2 | func2 | expr2 ] op2 ... [ valuen | varn | funcn | exprn ])
 186
 187   Thus, if the whole expression does not end with ), we encapsulate it with ( ).
 188
 189   If we don't consider priority among operators, then expression is converted into
 190   A1 A2 op1 A3 op2 ... An opn-1
 191
 192   example : 1+2+3-4-5 -> 1 2 + 3 + 4 -
 193
 194   If there is priority : * > / > + or - or func, then it is more complex
 195
 196   example : 1+2+3/4*5-6 -> 1 2 + 3 4 5 * / + 6 -
 197
 198   with parenthesis, we can do the same recursively
 199
 200   example : 1+(2+3/4)*5-6 = 1 + expr1 * 5 - 6 -> 1 expr1 5 * + 6 -
 201   but expr1 -> 2 3 4 / +, then we finally have 1 2 3 4 / + 5 * + 6 -
 202
 203   a func is of form:
 204   func_name(expr)
 205
 206   example : ((1+3-sin(5/6))*(4+(7/3)))
 207
 208   recursive cross in-depth of the expression leads to do a recursive call each time a ( is encountered.
 209   Return of the recursive call is done when ) is encountered.
 210
 211  */
 212
 213 void ArithmeticEvaluator::convert(const QString& _expression) throw(int) {
 214
 215   QString expr = _expression;
 216   QString result="";
 217   expr.remove(QChar(' '), Qt::CaseInsensitive);
 218   foreach(QString func, fctMarkers) {
 219     QString rep = QString("\x1b%1").arg(fctMarkers.indexOf(QRegExp(func)));
 220
 221     expr.replace(QRegExp(func),rep);
 222   }
 223
 224   int offset = 0;
 225   try {
 226     result = convertRecur(expr,&offset);
 227     expression = result.split(",");
 228   }
 229   catch(int err) {
 230     cerr << "error while recursive conversion: ";
 231     throw(err);
 232   }
 233
 234 }
 235
 236 QString ArithmeticEvaluator::convertRecur(const QString& _expression, int *offset) throw(int) {
 237   QString result="";
 238   QStack<QChar> pile;
 239
 240   int size;
 241   QChar c;
 242
 243   QString number;
 244   QString expr = _expression;
 245
 246   // testing if it starts by a (,number, variable or function
 247   if (!checkAfterOp(expr,*offset-1)) throw(*offset);
 248
 249   // testing if it starts with a number
 250   if ((expr[*offset] == '-') || (expr[*offset].isDigit())) {
 251     number = getNumber(expr,*offset,&size);
 252     result.append(number+",");
 253     *offset += size;
 254   }
 255   // testing if it starts with a variable
 256   else if (varMarkers.contains(expr[*offset])){
 257     number = getVariable(expr,*offset,&size);
 258     result.append(number+",");
 259     *offset += size;
 260   }
 261
 262   while (*offset<expr.size()) {
 263
 264     if ( expr[*offset] == '\x1b') {
 265       int numFunc = getFunction(expr,*offset,&size);
 266       if (numFunc == -1) throw(*offset);
 267       *offset += size;
 268       if (expr[*offset] != '(') throw(*offset);
 269       *offset += 1;
 270       result += convertRecur(expr,offset);
 271       result += QString("\x1b%1,").arg(numFunc);
 272     }
 273     else if ( expr[*offset] == '(') {
 274
 275       *offset += 1;
 276       result += convertRecur(expr,offset);
 277     }
 278
 279     else if ( expr[*offset] == ')') {
 280
 281       if (!checkAfterPar(expr,*offset)) throw(*offset);
 282
 283       while (! pile.isEmpty()) {
 284         c = pile.pop();
 285         result.append(c).append(",");
 286       }
 287       *offset += 1;
 288       return result;
 289     }
 290     else if ( (expr[*offset] == '+') || (expr[*offset] == '-')) {
 291
 292       if (!checkAfterOp(expr,*offset)) throw(*offset);
 293
 294       // destack operators with equal or greater priority
 295       while (!pile.isEmpty()) {
 296         c = pile.pop();
 297         result.append(c).append(",");
 298       }
 299       pile.push(expr[*offset]);
 300
 301       // catch the function, number or variable after operator if next char is not (
 302       if ( varMarkers.contains(expr[*offset+1])) {
 303         number = getVariable(expr,*offset+1,&size);
 304         result.append(number+",");
 305         *offset += size+1;
 306       }
 307       else if (expr[*offset+1].isDigit()) {
 308         number = getNumber(expr,*offset+1,&size);
 309         result.append(number+",");
 310         *offset += size+1;
 311       }
 312       else {
 313         *offset += 1;
 314       }
 315     }
 316     else if ((expr[*offset] == '/')||(expr[*offset] == '|')||(expr[*offset] == '%')) {
 317
 318       if (!checkAfterOp(expr,*offset)) throw(*offset);
 319
 320       // destack operator with equal or greater priority (/ and *)
 321       c = '1';
 322       while ( (pile.isEmpty() == false) && (c != '(') && (c != '+') && (c != '-')) {
 323         c = pile.pop();
 324         if ( (c=='*') || (c == '/') || (c == '|') || (c=='%')) {
 325           result.append(c).append(",");
 326         }
 327         else {
 328           pile.push(c);
 329         }
 330       }
 331       pile.push(expr[*offset]);
 332
 333       // catch the number or variable after operator if next char is not (
 334       if ( varMarkers.contains(expr[*offset+1])) {
 335         number = getVariable(expr,*offset+1,&size);
 336         result.append(number+",");
 337         *offset += size+1;
 338       }
 339       else if ( expr[*offset+1].isDigit()) {
 340         number = getNumber(expr,*offset+1,&size);
 341         result.append(number+",");
 342         *offset += size+1;
 343       }
 344       else {
 345         *offset += 1;
 346       }
 347     }
 348     /* CASES with * : a*b, (expra)*b, a*(exprb), (expra)*(exprb)
 349        Since * has the most priority, then :
 350        a*b and (expra)*b can be translate in ... b *
 351        In the two other cases, the * is stacked.
 352      */
 353     else if ( expr[*offset] == '*') {
 354
 355       if (!checkAfterOp(expr,*offset)) throw(*offset);
 356
 357       // catch the number or variable after operator if next char is not (
 358       if ( varMarkers.contains(expr[*offset+1])) {
 359         number = getVariable(expr,*offset+1,&size);
 360         result.append(number+",*,");
 361         *offset += size+1;
 362       }
 363       else if ( expr[*offset+1].isDigit()) {
 364         number = getNumber(expr,*offset+1,&size);
 365         result.append(number+",*,");
 366         *offset += size+1;
 367       }
 368       else {
 369         *offset += 1;
 370         pile.push('*');
 371       }
 372     }
 373   }
 374
 375   while (pile.isEmpty() == false) {
 376
 377     c = pile.pop();
 378     result.append(c).append(",");
 379   }
 380   result.chop(1);
 381   return result;
 382 }
 383
 384 QString ArithmeticEvaluator::getNumber(const QString& _expression, int offset, int *size) {
 385   int i = offset;
 386   QString number="";
 387   *size = 0;
 388   if (_expression[i] == '-') {
 389     number.append('-');
 390     i += 1;
 391     *size = 1;
 392   }
 393
 394   while (_expression[i].isDigit()) {
 395     number.append(_expression[i]);
 396     i += 1;
 397     *size += 1;
 398   }
 399
 400   // test if it's a floatting point value
 401   if (_expression[i] == '.') {
 402     number.append(".");
 403     i += 1;
 404     *size += 1;
 405     while (_expression[i].isDigit()) {
 406       number.append(_expression[i]);
 407       i += 1;
 408       *size += 1;
 409     }
 410   }
 411   return number;
 412 }
 413
 414 QString ArithmeticEvaluator::getVariable(const QString& _expression, int offset, int *size) {
 415   int i = offset;
 416   QString number="";
 417   *size = 0;
 418   if (varMarkers.contains(_expression[i])) {
 419     number.append(_expression[i]);
 420     i += 1;
 421     *size = 1;
 422   }
 423
 424   while ((_expression[i].isLetterOrNumber()) || (_expression[i] == '_')) {
 425     number.append(_expression[i]);
 426     i += 1;
 427     *size += 1;
 428   }
 429
 430   return number;
 431 }
 432
 433 int ArithmeticEvaluator::getFunction(const QString& _expression, int offset, int *size) {
 434   int numFunc = -1;
 435   int i = offset;
 436   QString number="";
 437   *size = 0;
 438   if (_expression[i] != '\x1b') return -1;
 439   i+= 1;
 440   *size += 1;
 441
 442   while (_expression[i].isDigit()) {
 443     number.append(_expression[i]);
 444     i += 1;
 445     *size += 1;
 446   }
 447   bool ok;
 448   numFunc = number.toInt(&ok);
 449   if ((!ok) || (numFunc >= fctMarkers.size())) return -1;
 450   return numFunc;
 451 }
 452
 453 bool ArithmeticEvaluator::checkAfterOp(const QString& _expression, int offset) {
 454   int size;
 455   if (offset+1 >= _expression.size()) return false;
 456
 457   if (_expression[offset+1] == '(') return true;
 458   else if (_expression[offset+1].isDigit()) return true;
 459   else if (_expression[offset+1] == '-') {
 460     if ((offset+2 < _expression.size()) && (_expression[offset+2].isDigit())) return true;
 461   }
 462   else if (varMarkers.contains(_expression[offset+1])) {
 463     if ((offset+2 < _expression.size()) && (_expression[offset+2].isLetterOrNumber())) return true;
 464   }
 465   else if (getFunction(_expression, offset+1,&size) != -1) {
 466     return true;
 467   }
 468
 469   return false;
 470 }
 471
 472 bool ArithmeticEvaluator::checkAfterPar(const QString& _expression, int offset) {
 473   if (offset >= _expression.size()) return false;
 474   // if ) is the last char of the expression : OK
 475   if (offset == _expression.size()-1) return true;
 476
 477   if (_expression[offset+1] == ')') return true;
 478   else if (_expression[offset+1] == '+') return true;
 479   else if (_expression[offset+1] == '-') return true;
 480   else if (_expression[offset+1] == '*') return true;
 481   else if (_expression[offset+1] == '/') return true;
 482   else if (_expression[offset+1] == '|') return true;
 483   else if (_expression[offset+1] == '%') return true;
 484
 485   return false;
 486 }