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
 169   QString expr = _expression;
 170   cout << "converting " << qPrintable(expr) << endl;
 171   QString result="";
 172   expr.remove(QChar(' '), Qt::CaseInsensitive);
 173   cout << "converting " << qPrintable(expr) << endl;
 174   foreach(QString func, fctMarkers) {
 175     cout << "for " << qPrintable(func) << endl;
 176     QString rep = QString("\x1b%1").arg(fctMarkers.indexOf(QRegExp(func)));
 177
 178     expr.replace(QRegExp(func),rep);
 179   }
 180   cout << "packed expr: " << qPrintable(expr) << endl;
 181
 182   int offset = 0;
 183   try {
 184     result = convertRecur(expr,&offset);
 185     expression = result.split(",");
 186   }
 187   catch(int err) {
 188     cerr << "error while recursive conversion: ";
 189     throw(err);
 190   }
 191
 192 }
 193
 194 QString ArithmeticEvaluator::convertRecur(const QString& _expression, int *offset) throw(int) {
 195   QString result="";
 196   QStack<QChar> pile;
 197
 198   int size;
 199   QChar c;
 200
 201   QString number;
 202   QString expr = _expression;
 203
 204   // testing if it starts by a (,number, variable or function
 205   if (!checkAfterOp(expr,*offset-1)) throw(*offset);
 206
 207   // testing if it starts with a number
 208   if ((expr[*offset] == '-') || (expr[*offset].isDigit())) {
 209     number = getNumber(expr,*offset,&size);
 210     result.append(number+",");
 211     *offset += size;
 212   }
 213   // testing if it starts with a variable
 214   else if (varMarkers.contains(expr[*offset])){
 215     number = getVariable(expr,*offset,&size);
 216     result.append(number+",");
 217     *offset += size;
 218   }
 219
 220   while (*offset<expr.size()) {
 221
 222     if ( expr[*offset] == '\x1b') {
 223       int numFunc = getFunction(expr,*offset,&size);
 224       if (numFunc == -1) throw(*offset);
 225       *offset += size;
 226       if (expr[*offset] != '(') throw(*offset);
 227       *offset += 1;
 228       result += convertRecur(expr,offset);
 229       result += QString("\x1b%1,").arg(numFunc);
 230     }
 231     else if ( expr[*offset] == '(') {
 232
 233       *offset += 1;
 234       result += convertRecur(expr,offset);
 235     }
 236
 237     else if ( expr[*offset] == ')') {
 238
 239       if (!checkAfterPar(expr,*offset)) throw(*offset);
 240
 241       while (! pile.isEmpty()) {
 242         c = pile.pop();
 243         result.append(c).append(",");
 244       }
 245       *offset += 1;
 246       return result;
 247     }
 248     else if ( (expr[*offset] == '+') || (expr[*offset] == '-')) {
 249
 250       if (!checkAfterOp(expr,*offset)) throw(*offset);
 251
 252       // destack operators with equal or greater priority
 253       while (!pile.isEmpty()) {
 254         c = pile.pop();
 255         result.append(c).append(",");
 256       }
 257       pile.push(expr[*offset]);
 258
 259       // catch the function, number or variable after operator if next char is not (
 260       if ( varMarkers.contains(expr[*offset+1])) {
 261         number = getVariable(expr,*offset+1,&size);
 262         result.append(number+",");
 263         *offset += size+1;
 264       }
 265       else if (expr[*offset+1].isDigit()) {
 266         number = getNumber(expr,*offset+1,&size);
 267         result.append(number+",");
 268         *offset += size+1;
 269       }
 270       else {
 271         *offset += 1;
 272       }
 273     }
 274     else if (expr[*offset] == '/') {
 275
 276       if (!checkAfterOp(expr,*offset)) throw(*offset);
 277
 278       // destack operator with equal or greater priority (/ and *)
 279       c = '1';
 280       while ( (pile.isEmpty() == false) && (c != '(') && (c != '+') && (c != '-')) {
 281         c = pile.pop();
 282         if ( (c=='*') || (c == '/')) {
 283           result.append(c).append(",");
 284         }
 285         else {
 286           pile.push(c);
 287         }
 288       }
 289       pile.push(expr[*offset]);
 290
 291       // catch the 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     /* CASES with * : a*b, (expra)*b, a*(exprb), (expra)*(exprb)
 307        Since * has the most priority, then :
 308        a*b and (expra)*b can be translate in ... b *
 309        In the two other cases, the * is stacked.
 310      */
 311     else if ( expr[*offset] == '*') {
 312
 313       if (!checkAfterOp(expr,*offset)) throw(*offset);
 314
 315       // catch the number or variable after operator if next char is not (
 316       if ( varMarkers.contains(expr[*offset+1])) {
 317         number = getVariable(expr,*offset+1,&size);
 318         result.append(number+",*,");
 319         *offset += size+1;
 320       }
 321       else if ( expr[*offset+1].isDigit()) {
 322         number = getNumber(expr,*offset+1,&size);
 323         result.append(number+",*,");
 324         *offset += size+1;
 325       }
 326       else {
 327         *offset += 1;
 328         pile.push('*');
 329       }
 330     }
 331   }
 332
 333   while (pile.isEmpty() == false) {
 334
 335     c = pile.pop();
 336     result.append(c).append(",");
 337   }
 338   result.chop(1);
 339   return result;
 340 }
 341
 342 QString ArithmeticEvaluator::getNumber(const QString& _expression, int offset, int *size) {
 343   int i = offset;
 344   QString number="";
 345   *size = 0;
 346   if (_expression[i] == '-') {
 347     number.append('-');
 348     i += 1;
 349     *size = 1;
 350   }
 351
 352   while (_expression[i].isDigit()) {
 353     number.append(_expression[i]);
 354     i += 1;
 355     *size += 1;
 356   }
 357
 358   // test if it's a floatting point value
 359   if (_expression[i] == '.') {
 360     number.append(".");
 361     i += 1;
 362     *size += 1;
 363     while (_expression[i].isDigit()) {
 364       number.append(_expression[i]);
 365       i += 1;
 366       *size += 1;
 367     }
 368   }
 369   return number;
 370 }
 371
 372 QString ArithmeticEvaluator::getVariable(const QString& _expression, int offset, int *size) {
 373   int i = offset;
 374   QString number="";
 375   *size = 0;
 376   if (varMarkers.contains(_expression[i])) {
 377     number.append(_expression[i]);
 378     i += 1;
 379     *size = 1;
 380   }
 381
 382   while ((_expression[i].isLetterOrNumber()) || (_expression[i] == '-') || (_expression[i] == '_')) {
 383     number.append(_expression[i]);
 384     i += 1;
 385     *size += 1;
 386   }
 387
 388   return number;
 389 }
 390
 391 int ArithmeticEvaluator::getFunction(const QString& _expression, int offset, int *size) {
 392   int numFunc = -1;
 393   int i = offset;
 394   QString number="";
 395   *size = 0;
 396   if (_expression[i] != '\x1b') return -1;
 397   i+= 1;
 398   *size += 1;
 399
 400   while (_expression[i].isDigit()) {
 401     number.append(_expression[i]);
 402     i += 1;
 403     *size += 1;
 404   }
 405   bool ok;
 406   numFunc = number.toInt(&ok);
 407   if ((!ok) || (numFunc >= fctMarkers.size())) return -1;
 408   return numFunc;
 409 }
 410
 411 bool ArithmeticEvaluator::checkAfterOp(const QString& _expression, int offset) {
 412   int size;
 413   if (offset+1 >= _expression.size()) return false;
 414
 415   if (_expression[offset+1] == '(') return true;
 416   else if (_expression[offset+1].isDigit()) return true;
 417   else if (_expression[offset+1] == '-') {
 418     if ((offset+2 < _expression.size()) && (_expression[offset+2].isDigit())) return true;
 419   }
 420   else if (varMarkers.contains(_expression[offset+1])) {
 421     if ((offset+2 < _expression.size()) && (_expression[offset+2].isLetterOrNumber())) return true;
 422   }
 423   else if (getFunction(_expression, offset+1,&size) != -1) {
 424     return true;
 425   }
 426
 427   return false;
 428 }
 429
 430 bool ArithmeticEvaluator::checkAfterPar(const QString& _expression, int offset) {
 431   if (offset >= _expression.size()) return false;
 432   // if ) is the last char of the expression : OK
 433   if (offset == _expression.size()-1) return true;
 434
 435   if (_expression[offset+1] == ')') return true;
 436   else if (_expression[offset+1] == '+') return true;
 437   else if (_expression[offset+1] == '-') return true;
 438   else if (_expression[offset+1] == '*') return true;
 439   else if (_expression[offset+1] == '/') return true;
 440
 441   return false;
 442 }