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 = "+-*/";
  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 = "+-*/";
  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     }
 160     else {
 161       value1 = elt.toDouble(&ok);
 162       if (!ok) throw(-index);
 163       stack.push(value1);
 164     }
 165     index += 1;
 166   }
 167
 168   value1 = stack.pop();
 169   if (!stack.isEmpty()) throw(-1);
 170   return value1;
 171 }
 172
 173 /* NOTE :
 174   expr is of form:
 175   ([ value1 | var1 | func1 | expr1 ] op1 [ value2 | var2 | func2 | expr2 ] op2 ... [ valuen | varn | funcn | exprn ])
 176
 177   Thus, if the whole expression does not end with ), we encapsulate it with ( ).
 178
 179   If we don't consider priority among operators, then expression is converted into
 180   A1 A2 op1 A3 op2 ... An opn-1
 181
 182   example : 1+2+3-4-5 -> 1 2 + 3 + 4 -
 183
 184   If there is priority : * > / > + or - or func, then it is more complex
 185
 186   example : 1+2+3/4*5-6 -> 1 2 + 3 4 5 * / + 6 -
 187
 188   with parenthesis, we can do the same recursively
 189
 190   example : 1+(2+3/4)*5-6 = 1 + expr1 * 5 - 6 -> 1 expr1 5 * + 6 -
 191   but expr1 -> 2 3 4 / +, then we finally have 1 2 3 4 / + 5 * + 6 -
 192
 193   a func is of form:
 194   func_name(expr)
 195
 196   example : ((1+3-sin(5/6))*(4+(7/3)))
 197
 198   recursive cross in-depth of the expression leads to do a recursive call each time a ( is encountered.
 199   Return of the recursive call is done when ) is encountered.
 200
 201  */
 202
 203 void ArithmeticEvaluator::convert(const QString& _expression) throw(int) {
 204
 205   QString expr = _expression;
 206   QString result="";
 207   expr.remove(QChar(' '), Qt::CaseInsensitive);
 208   foreach(QString func, fctMarkers) {
 209     QString rep = QString("\x1b%1").arg(fctMarkers.indexOf(QRegExp(func)));
 210
 211     expr.replace(QRegExp(func),rep);
 212   }
 213
 214   int offset = 0;
 215   try {
 216     result = convertRecur(expr,&offset);
 217     expression = result.split(",");
 218   }
 219   catch(int err) {
 220     cerr << "error while recursive conversion: ";
 221     throw(err);
 222   }
 223
 224 }
 225
 226 QString ArithmeticEvaluator::convertRecur(const QString& _expression, int *offset) throw(int) {
 227   QString result="";
 228   QStack<QChar> pile;
 229
 230   int size;
 231   QChar c;
 232
 233   QString number;
 234   QString expr = _expression;
 235
 236   // testing if it starts by a (,number, variable or function
 237   if (!checkAfterOp(expr,*offset-1)) throw(*offset);
 238
 239   // testing if it starts with a number
 240   if ((expr[*offset] == '-') || (expr[*offset].isDigit())) {
 241     number = getNumber(expr,*offset,&size);
 242     result.append(number+",");
 243     *offset += size;
 244   }
 245   // testing if it starts with a variable
 246   else if (varMarkers.contains(expr[*offset])){
 247     number = getVariable(expr,*offset,&size);
 248     result.append(number+",");
 249     *offset += size;
 250   }
 251
 252   while (*offset<expr.size()) {
 253
 254     if ( expr[*offset] == '\x1b') {
 255       int numFunc = getFunction(expr,*offset,&size);
 256       if (numFunc == -1) throw(*offset);
 257       *offset += size;
 258       if (expr[*offset] != '(') throw(*offset);
 259       *offset += 1;
 260       result += convertRecur(expr,offset);
 261       result += QString("\x1b%1,").arg(numFunc);
 262     }
 263     else if ( expr[*offset] == '(') {
 264
 265       *offset += 1;
 266       result += convertRecur(expr,offset);
 267     }
 268
 269     else if ( expr[*offset] == ')') {
 270
 271       if (!checkAfterPar(expr,*offset)) throw(*offset);
 272
 273       while (! pile.isEmpty()) {
 274         c = pile.pop();
 275         result.append(c).append(",");
 276       }
 277       *offset += 1;
 278       return result;
 279     }
 280     else if ( (expr[*offset] == '+') || (expr[*offset] == '-')) {
 281
 282       if (!checkAfterOp(expr,*offset)) throw(*offset);
 283
 284       // destack operators with equal or greater priority
 285       while (!pile.isEmpty()) {
 286         c = pile.pop();
 287         result.append(c).append(",");
 288       }
 289       pile.push(expr[*offset]);
 290
 291       // catch the function, number or variable after operator if next char is not (
 292       if ( varMarkers.contains(expr[*offset+1])) {
 293         number = getVariable(expr,*offset+1,&size);
 294         result.append(number+",");
 295         *offset += size+1;
 296       }
 297       else if (expr[*offset+1].isDigit()) {
 298         number = getNumber(expr,*offset+1,&size);
 299         result.append(number+",");
 300         *offset += size+1;
 301       }
 302       else {
 303         *offset += 1;
 304       }
 305     }
 306     else if (expr[*offset] == '/') {
 307
 308       if (!checkAfterOp(expr,*offset)) throw(*offset);
 309
 310       // destack operator with equal or greater priority (/ and *)
 311       c = '1';
 312       while ( (pile.isEmpty() == false) && (c != '(') && (c != '+') && (c != '-')) {
 313         c = pile.pop();
 314         if ( (c=='*') || (c == '/')) {
 315           result.append(c).append(",");
 316         }
 317         else {
 318           pile.push(c);
 319         }
 320       }
 321       pile.push(expr[*offset]);
 322
 323       // catch the number or variable after operator if next char is not (
 324       if ( varMarkers.contains(expr[*offset+1])) {
 325         number = getVariable(expr,*offset+1,&size);
 326         result.append(number+",");
 327         *offset += size+1;
 328       }
 329       else if ( expr[*offset+1].isDigit()) {
 330         number = getNumber(expr,*offset+1,&size);
 331         result.append(number+",");
 332         *offset += size+1;
 333       }
 334       else {
 335         *offset += 1;
 336       }
 337     }
 338     /* CASES with * : a*b, (expra)*b, a*(exprb), (expra)*(exprb)
 339        Since * has the most priority, then :
 340        a*b and (expra)*b can be translate in ... b *
 341        In the two other cases, the * is stacked.
 342      */
 343     else if ( expr[*offset] == '*') {
 344
 345       if (!checkAfterOp(expr,*offset)) throw(*offset);
 346
 347       // catch the number or variable after operator if next char is not (
 348       if ( varMarkers.contains(expr[*offset+1])) {
 349         number = getVariable(expr,*offset+1,&size);
 350         result.append(number+",*,");
 351         *offset += size+1;
 352       }
 353       else if ( expr[*offset+1].isDigit()) {
 354         number = getNumber(expr,*offset+1,&size);
 355         result.append(number+",*,");
 356         *offset += size+1;
 357       }
 358       else {
 359         *offset += 1;
 360         pile.push('*');
 361       }
 362     }
 363   }
 364
 365   while (pile.isEmpty() == false) {
 366
 367     c = pile.pop();
 368     result.append(c).append(",");
 369   }
 370   result.chop(1);
 371   return result;
 372 }
 373
 374 QString ArithmeticEvaluator::getNumber(const QString& _expression, int offset, int *size) {
 375   int i = offset;
 376   QString number="";
 377   *size = 0;
 378   if (_expression[i] == '-') {
 379     number.append('-');
 380     i += 1;
 381     *size = 1;
 382   }
 383
 384   while (_expression[i].isDigit()) {
 385     number.append(_expression[i]);
 386     i += 1;
 387     *size += 1;
 388   }
 389
 390   // test if it's a floatting point value
 391   if (_expression[i] == '.') {
 392     number.append(".");
 393     i += 1;
 394     *size += 1;
 395     while (_expression[i].isDigit()) {
 396       number.append(_expression[i]);
 397       i += 1;
 398       *size += 1;
 399     }
 400   }
 401   return number;
 402 }
 403
 404 QString ArithmeticEvaluator::getVariable(const QString& _expression, int offset, int *size) {
 405   int i = offset;
 406   QString number="";
 407   *size = 0;
 408   if (varMarkers.contains(_expression[i])) {
 409     number.append(_expression[i]);
 410     i += 1;
 411     *size = 1;
 412   }
 413
 414   while ((_expression[i].isLetterOrNumber()) || (_expression[i] == '_')) {
 415     number.append(_expression[i]);
 416     i += 1;
 417     *size += 1;
 418   }
 419
 420   return number;
 421 }
 422
 423 int ArithmeticEvaluator::getFunction(const QString& _expression, int offset, int *size) {
 424   int numFunc = -1;
 425   int i = offset;
 426   QString number="";
 427   *size = 0;
 428   if (_expression[i] != '\x1b') return -1;
 429   i+= 1;
 430   *size += 1;
 431
 432   while (_expression[i].isDigit()) {
 433     number.append(_expression[i]);
 434     i += 1;
 435     *size += 1;
 436   }
 437   bool ok;
 438   numFunc = number.toInt(&ok);
 439   if ((!ok) || (numFunc >= fctMarkers.size())) return -1;
 440   return numFunc;
 441 }
 442
 443 bool ArithmeticEvaluator::checkAfterOp(const QString& _expression, int offset) {
 444   int size;
 445   if (offset+1 >= _expression.size()) return false;
 446
 447   if (_expression[offset+1] == '(') return true;
 448   else if (_expression[offset+1].isDigit()) return true;
 449   else if (_expression[offset+1] == '-') {
 450     if ((offset+2 < _expression.size()) && (_expression[offset+2].isDigit())) return true;
 451   }
 452   else if (varMarkers.contains(_expression[offset+1])) {
 453     if ((offset+2 < _expression.size()) && (_expression[offset+2].isLetterOrNumber())) return true;
 454   }
 455   else if (getFunction(_expression, offset+1,&size) != -1) {
 456     return true;
 457   }
 458
 459   return false;
 460 }
 461
 462 bool ArithmeticEvaluator::checkAfterPar(const QString& _expression, int offset) {
 463   if (offset >= _expression.size()) return false;
 464   // if ) is the last char of the expression : OK
 465   if (offset == _expression.size()-1) return true;
 466
 467   if (_expression[offset+1] == ')') return true;
 468   else if (_expression[offset+1] == '+') return true;
 469   else if (_expression[offset+1] == '-') return true;
 470   else if (_expression[offset+1] == '*') return true;
 471   else if (_expression[offset+1] == '/') return true;
 472
 473   return false;
 474 }