Expression.cpp 13.6 KB
Newer Older
1
2
3
4
#include <iostream>
#include <locale>
#include <sstream>

5
6
7
8
#include "MantidAPI/Expression.h"

#include <Poco/StringTokenizer.h>

9
10
namespace Mantid {
namespace API {
11
12
13

typedef Poco::StringTokenizer tokenizer;

14
15
const std::string DEFAULT_OPS_STR[] = {";", ",", "=", "== != > < <= >=",
                                       "&& || ^^", "+ -", "* /", "^"};
16

17
Expression::Expression() {
18
19

  m_operators.reset(new Operators());
20
21
22
  // Define binary operators. Put them in the reverse precedence order (from
  // lower to higher prec.)
  std::vector<std::string> ops(DEFAULT_OPS_STR, DEFAULT_OPS_STR + 8);
23
24
25
26
27
28
29
30
31
32
33
34

  add_operators(ops);

  // Define unary operators
  std::set<std::string> unary;
  unary.insert("+");
  unary.insert("-");

  add_unary(unary);
}

/// contructor
35
Expression::Expression(const std::vector<std::string> &ops) {
36
37
38
39
40
  m_operators.reset(new Operators());
  add_operators(ops);
}

/// contructor
41
42
Expression::Expression(const std::vector<std::string> &binary,
                       const std::set<std::string> &unary) {
43
44
45
46
47
  m_operators.reset(new Operators());
  add_operators(binary);
  add_unary(unary);
}

48
49
50
51
52
53
54
Expression::Expression(const Expression &expr)
    : // m_tokens(expr.m_tokens),
      // m_expr(expr.m_expr),
      m_funct(expr.m_funct),
      m_op(expr.m_op), m_terms(expr.m_terms), m_operators(expr.m_operators) {}
Expression::Expression(const Expression *pexpr)
    : m_operators(pexpr->m_operators) {}
55
56

/// Assignment operator
57
Expression &Expression::operator=(const Expression &expr) {
58
59
60
61
  m_operators = expr.m_operators;
  m_funct = expr.m_funct;
  m_op = expr.m_op;
  m_terms = expr.m_terms;
62
63
  // m_expr = expr.m_expr;
  // m_tokens = expr.m_tokens;
64
65
66
  return *this;
}

67
void Expression::add_operators(const std::vector<std::string> &ops) {
68
69
  m_operators->binary = ops;
  // Fill in the precedence table (m_op_precedence)
70
  for (size_t i = 0; i < m_operators->binary.size(); i++) {
71
    char j = 0;
72
73
    tokenizer tkz(m_operators->binary[i], " ",
                  tokenizer::TOK_IGNORE_EMPTY | tokenizer::TOK_TRIM);
74
    for (auto it = tkz.begin(); it != tkz.end(); it++) {
75
76
77
78
79
      m_operators->precedence[*it] = i + 1;
      m_operators->op_number[*it] = j++;
    }
  }

80
  for (size_t i = 0; i < ops.size(); i++) {
81
    std::string str = ops[i];
82
    for (size_t j = 0; j < str.size(); j++) {
83
      char c = str[j];
84
85
      if (c == ' ')
        continue;
86
87
88
89
90
      m_operators->symbols.insert(c);
    }
  }
}

91
void Expression::add_unary(const std::set<std::string> &ops) {
92
  m_operators->unary = ops;
93
  for (auto it = ops.begin(); it != ops.end();
94
95
       ++it) {
    for (std::string::const_iterator c = it->begin(); c != it->end(); ++c) {
96
97
98
99
100
      m_operators->symbols.insert(*c);
    }
  }
}

101
102
103
104
105
size_t Expression::op_prec(const std::string &op) const {
  std::map<std::string, size_t>::const_iterator i =
      m_operators->precedence.find(op);
  if (i == m_operators->precedence.end())
    return 0;
106
107
108
  return i->second;
}

109
bool Expression::is_unary(const std::string &op) const {
110
  return m_operators->unary.find(op) != m_operators->unary.end();
111
112
}

113
bool Expression::is_op_symbol(const char c) const {
114
  return m_operators->symbols.find(c) != m_operators->symbols.end();
115
116
}

117
void Expression::trim(std::string &str) {
118
119
  size_t i = str.find_first_not_of(" \t\n\r");
  size_t j = str.find_last_not_of(" \t\n\r");
120
  if (i == std::string::npos || j == std::string::npos || j < i) {
121
    str = "";
122
123
  } else {
    str = str.substr(i, j - i + 1);
124
125
126
  }
}

127
void Expression::parse(const std::string &str) {
128
129
130
  m_expr = str;
  trim(m_expr);

131
132
133
134
135
  if (m_expr.size() > 1 && m_expr[0] == '(' &&
      m_expr[m_expr.size() - 1] == ')') {
    if (m_expr.find('(', 1) == std::string::npos) {
      m_expr.erase(0, 1);
      m_expr.erase(m_expr.size() - 1, 1);
136
137
138
139
140
141
      trim(m_expr);
    }
  }

  tokenize();

142
  if (m_tokens.size() == 0) {
143
144
145
146
147
    setFunct(m_expr);
    return;
  }

  std::string op = GetOp(0);
148
  // size_t prec = m_operators->precedence[op];
149
  size_t prec = op_prec(op);
150
151
  tokenizer tkz(m_operators->binary[prec - 1], " ",
                tokenizer::TOK_IGNORE_EMPTY | tokenizer::TOK_TRIM);
152
153
154

  setFunct(*tkz.begin());

155
  for (size_t i = 0; i <= m_tokens.size(); i++) {
156
    m_terms.push_back(Expression(this));
157
    Expression &t = m_terms.back();
158
    if (i)
159
      t.m_op = GetOp(i - 1);
160
161
162
163
164
165
    t.parse(GetToken(i));
  }
  m_expr = "";
  m_tokens.clear();
}

166
void Expression::tokenize() {
167
168
  m_tokens.clear();

Peterson, Peter's avatar
Peterson, Peter committed
169
  size_t min_prec = 1000;
170
171
172
173
174
175
176
  size_t is = 0;
  size_t is1 = 0;
  unsigned int lvl = 0;
  size_t last = m_expr.size() - 1;
  bool inString = false;
  int skip = 0;
  bool canBeBinary = false;
177
178
  bool isNumber =
      false; // if parser is inside a number (important case is 123.45e+67)
179
180
181
  bool canDotBeAdded = false;
  bool canEBeAdded = false;
  bool canPlusBeAdded = false;
182
  Tokens tokens;
183
  for (size_t i = 0; i < m_expr.size(); i++) {
184
    char c = m_expr[i];
185

186
187
188
189
    if (!inString && skip == 0) {
      if (isNumber) {
        if (c == '.') {
          if (canDotBeAdded) {
190
            canDotBeAdded = false;
191
          } else {
192
193
            isNumber = false;
          }
194
195
        } else if (c == 'e' || c == 'E') {
          if (canEBeAdded) {
196
197
198
            canEBeAdded = false;
            canDotBeAdded = false;
            canPlusBeAdded = true;
199
          } else {
200
201
            isNumber = false;
          }
202
203
        } else if (c == '+' || c == '-') {
          if (canPlusBeAdded) {
204
205
206
            canPlusBeAdded = false;
            canEBeAdded = false;
            canDotBeAdded = false;
207
          } else {
208
209
            isNumber = false;
          }
210
        } else if (!isdigit(c)) {
211
212
          isNumber = false;
        }
213
      } else if (isdigit(c)) {
214
215
216
217
218
        isNumber = true;
        canDotBeAdded = true;
        canEBeAdded = true;
        canPlusBeAdded = false;
      }
219
      if (lvl == 0 && !isNumber && is_op_symbol(c)) // insert new token
220
      {
221
        if (i == last) {
222
          break;
223
          // throw std::runtime_error("Expression: syntax error");
224
225
        }

226
        if (is_op_symbol(m_expr[i + 1])) {
227
          is1 = i + 2;
228
        } else {
229
230
231
          is1 = i + 1;
        }

232
        if (is1 > last) {
233
234
235
          throw std::runtime_error("Expression: syntax error");
        }

236
237
        std::string op = m_expr.substr(i, is1 - i);
        size_t prec = canBeBinary ? m_operators->precedence[op] : 0;
238
239
240
241
242
        if (!prec) // operator does not exist
        {
          std::ostringstream mess;
          bool error = true;
          // check if it's a binary and a unary operators together
243
244
          if (op.size() == 2) {
            if (is_unary(op)) {
245
246
247
248
              is1 -= 2;
              skip = 2;
              prec = min_prec + 1; // do not add token
              error = false;
249
            } else {
250
              is1 -= 1;
251
              std::string uop = op.substr(1, 1);
252
              op = op[0];
253
254
255
256
              if (is_op_symbol(m_expr[is1 + 1])) {
                uop += m_expr[is1 + 1];
                if (is1 + 2 > last) {
                  mess << "Expression: syntax error at " << is1 + 1;
257
258
259
                  throw std::runtime_error(mess.str());
                }
              }
260
              if (is_unary(uop)) {
261
                prec = m_operators->precedence[op];
262
263
                if (prec) { // we don't want to create a new token with unary
                            // operator. it is processed in SetFunct()
264
265
266
267
268
                  skip = 1;
                  error = false;
                }
              }
            }
269
270
271
          } // op.size == 2
          else if (op.size() == 1) {
            // skip = 1;
272
273
274
            prec = min_prec + 1; // do not add token
            error = false;
          }
275
          if (error) {
276
277
278
279
280
            mess << "Expression: unrecognized operator " << op;
            throw std::runtime_error(mess.str());
          }
        }

281
        if (prec <= min_prec) {
Peterson, Peter's avatar
Peterson, Peter committed
282
          if (prec < min_prec)
283
284
            min_prec = prec;
          Token tok(is, i - 1, is1, prec);
285
286
287
288
289
290
291
292
          tokens.push_back(tok);
          is = is1;
        }

        i = is1 - 1;

        canBeBinary = false;

293
294
      } // insert new token
      else if (c != ' ' && c != '\t' && c != '\r' && c != '\n') {
295
296
297
        canBeBinary = true;
      }

298
299
300
301
302
303
      if (c == '(')
        lvl++;
      if (c == ')') {
        if (lvl)
          lvl--;
        else {
304
305
306
307
          throw std::runtime_error("Unmatched brackets");
        }
      }
    } // !inString || skip
308
309
    else if (skip > 0) {
      skip--;
310
311
    }

312
313
    if (c == '"') {
      if (!inString) {
314
        inString = true;
315
      } else {
316
317
318
319
320
321
        inString = false;
      }
    }

  } // for i

322
  if (tokens.size()) {
323
324
    // remove operators of higher prec
    m_tokens.push_back(Token(tokens[0]));
325
326
327
328
329
    for (size_t i = 0; i < tokens.size(); i++) {
      Token &tok = tokens[i];
      std::string op = m_expr.substr(tok.ie + 1, tok.is1 - tok.ie - 1); //?
      if (m_operators->precedence[op] == min_prec) {
        Token &last_tok = m_tokens.back();
330
        last_tok.ie = tok.ie;
331
332
333
        last_tok.is1 = tok.is1;
        if (i != tokens.size() - 1)
          m_tokens.push_back(Token(tokens[i + 1]));
334
335
336
337
338
      }
    }
  }
}

339
340
341
std::string Expression::GetToken(size_t i) {
  if (m_tokens.size() == 0)
    return m_expr;
342

343
344
345
  if (i < m_tokens.size()) {
    Token &tok = m_tokens[i];
    return m_expr.substr(tok.is, tok.ie - tok.is + 1);
346
347
  }

348
349
  if (i == m_tokens.size()) {
    Token &tok = m_tokens[i - 1];
350
351
352
353
354
355
    return m_expr.substr(tok.is1);
  }

  return "";
}

356
357
358
std::string Expression::GetOp(size_t i) {
  if (m_tokens.size() == 0 || i >= m_tokens.size())
    return "";
359

360
361
  Token &tok = m_tokens[i];
  return m_expr.substr(tok.ie + 1, tok.is1 - tok.ie - 1);
362
363
}

364
void Expression::logPrint(const std::string &pads) const {
365
  std::string myPads = pads + "   ";
366
367
368
  if (m_terms.size()) {
    std::cerr << myPads << m_op << '[' << m_funct << ']' << "(" << '\n';
    for (size_t i = 0; i < m_terms.size(); i++)
369
      m_terms[i].logPrint(myPads);
370
371
372
    std::cerr << myPads << ")" << '\n';
  } else
    std::cerr << myPads << m_op << m_funct << '\n';
373
374
}

375
376
void Expression::setFunct(const std::string &name) {
  if (!op_prec(name)) {
377
    std::string op = "";
378
379
380
    if (name.size() > 1 && is_op_symbol(name[0])) {
      op = name.substr(0, 1);
      if (name.size() > 2 && is_op_symbol(name[1])) {
381
382
383
        op += name[1];
      }
    }
384
    if (!op.empty() && is_unary(op)) {
385
386
387
388
389
390
391
392
393
394
      m_funct = op;
      Expression tmp(this);
      tmp.parse(name.substr(op.size()));
      m_terms.push_back(tmp);
      return;
    }
  }

  m_funct = name;
  trim(m_funct);
395
  if (m_funct.empty()) {
396
397
398
399
400
401
402
    throw std::runtime_error("Expression: Syntax error");
  }

  // Check if the function has arguments
  std::string::size_type i = std::string::npos;

  bool inQuotes = false;
403
404
405
406
  for (std::string::const_iterator c = name.begin(); c != name.end(); ++c) {
    if (*c == '"') {
      if (inQuotes)
        inQuotes = false;
407
408
409
410
411
      else
        inQuotes = true;
      continue;
    }

412
    if (!inQuotes && *c == '(') {
413
414
415
416
417
      i = c - name.begin();
      break;
    }
  }

418
  if (i != std::string::npos) {
419
    std::string::size_type j = name.find_last_of(')');
420
    if (j == std::string::npos || j < i) {
421
422
423
      throw std::runtime_error("Unmatched brackets");
    }

424
    if (j > i + 1) // nonzero argument list
425
    {
426
      std::string args = name.substr(i + 1, j - i - 1); //?
427
      trim(args);
428
      std::string f = name.substr(0, i);
429
430
      Expression tmp(this);
      tmp.parse(args);
431
      if (!tmp.isFunct() || tmp.name() != ",") {
432
        m_terms.push_back(tmp);
433
      } else {
434
435
436
437
438
439
440
441
442
        std::string my_op = m_op;
        *this = tmp;
        m_op = my_op;
      }
      m_funct = f;
    }
  }
}

443
std::string Expression::str() const {
444
445
446
  bool brackets = false;
  std::ostringstream res;
  size_t prec = op_prec(m_funct);
447
  if (size() == 1 && is_unary(m_funct)) { // unary operator
448
    res << m_funct;
449
    if (op_prec(m_terms[0].m_funct) > 0) {
450
451
      brackets = true;
    }
452
  } else if (!prec) { // function with a name
453
454
455
456
    res << m_funct;
    brackets = true;
  }

457
458
459
460
  if (m_terms.size()) {
    if (brackets)
      res << '(';
    for (size_t i = 0; i < m_terms.size(); i++) {
461
      res << m_terms[i].operator_name();
462
      size_t prec1 = op_prec(m_terms[i].m_funct);
463
      bool isItUnary = false;
464
      if (m_terms[i].size() == 1 && is_unary(m_terms[i].m_funct)) {
465
466
467
        prec1 = 0; // unary operator
        isItUnary = true;
      }
468
469
470
471
472
      bool bk = prec > 0 && prec1 > 0 && prec > prec1;
      if (bk)
        res << '(';
      if (isItUnary)
        res << ' ';
473
      res << m_terms[i].str();
474
475
      if (bk)
        res << ')';
476
    }
477
478
    if (brackets)
      res << ')';
479
480
481
482
  }
  return res.str();
}

483
484
485
const Expression &Expression::bracketsRemoved() const {
  const Expression *e = this;
  while (e->name().empty() && e->size() == 1) {
486
487
488
489
490
    e = &e->m_terms[0];
  }
  return *e;
}

491
492
493
/**
 * Return a list of all variable names in this expression
 */
494
std::set<std::string> Expression::getVariables() const {
495
  std::set<std::string> out;
496
  if (!isFunct()) {
497
    std::string s = name();
498
    if (!s.empty() && !isdigit(s[0])) {
499
500
      out.insert(s);
    }
501
  } else {
502
    for (auto e = begin(); e != end(); ++e) {
503
      if (e->isFunct()) {
504
        std::set<std::string> tout = e->getVariables();
505
506
        out.insert(tout.begin(), tout.end());
      } else {
507
        std::string s = e->name();
508
        if (!s.empty() && !isdigit(s[0])) {
509
510
          out.insert(s);
        }
511
512
513
514
515
516
      }
    }
  }
  return out;
}

517
void Expression::rename(const std::string &newName) { m_funct = newName; }
518

519
520
521
void Expression::renameAll(const std::string &oldName,
                           const std::string &newName) {
  if (!isFunct() && name() == oldName) {
522
    rename(newName);
523
  } else {
524
    auto e = m_terms.begin();
525
526
    for (; e != m_terms.end(); ++e) {
      e->renameAll(oldName, newName);
527
528
529
530
    }
  }
}

531
532
533
void Expression::toList(const std::string &sep) {
  if (name() == sep)
    return;
534
535
536
537
538
539
  Expression term(*this);
  m_terms.resize(1);
  m_terms[0] = term;
  setFunct(sep);
}

540
541
} // API
} // Mantid