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