source: branches/2915-AbsoluteSymbol/HeuristicLab.Problems.DataAnalysis.Symbolic/3.4/Importer/InfixExpressionParser.cs @ 16239

Last change on this file since 16239 was 16239, checked in by gkronber, 10 months ago

#2915 added support for abs(x), cube(x), cuberoot(x), and aq(x) to:

  • formatters,
  • infix parser
  • constant opt (autodiff)
  • simplifier (incomplete)
File size: 20.9 KB
Line 
1#region License Information
2/* HeuristicLab
3 * Copyright (C) 2002-2018 Heuristic and Evolutionary Algorithms Laboratory (HEAL)
4 *
5 * This file is part of HeuristicLab.
6 *
7 * HeuristicLab is free software: you can redistribute it and/or modify
8 * it under the terms of the GNU General Public License as published by
9 * the Free Software Foundation, either version 3 of the License, or
10 * (at your option) any later version.
11 *
12 * HeuristicLab is distributed in the hope that it will be useful,
13 * but WITHOUT ANY WARRANTY; without even the implied warranty of
14 * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
15 * GNU General Public License for more details.
16 *
17 * You should have received a copy of the GNU General Public License
18 * along with HeuristicLab. If not, see <http://www.gnu.org/licenses/>.
19 */
20#endregion
21
22using System;
23using System.Collections.Generic;
24using System.Globalization;
25using System.Linq;
26using System.Text;
27using HeuristicLab.Collections;
28using HeuristicLab.Common;
29using HeuristicLab.Encodings.SymbolicExpressionTreeEncoding;
30
31namespace HeuristicLab.Problems.DataAnalysis.Symbolic {
32  /// <summary>
33  /// Parses mathematical expressions in infix form. E.g. x1 * (3.0 * x2 + x3)
34  /// Identifier format (functions or variables): '_' | letter { '_' | letter | digit }
35  /// Variables names and variable values can be set under quotes "" or '' because variable names might contain spaces.
36  ///   Variable = ident | " ident " | ' ident '
37  /// It is also possible to use functions e.g. log("x1") or real-valued constants e.g. 3.1415 .
38  /// Variable names are case sensitive. Function names are not case sensitive.
39  ///
40  ///
41  /// S             = Expr EOF
42  /// Expr          = ['-' | '+'] Term { '+' Term | '-' Term }
43  /// Term          = Fact { '*' Fact | '/' Fact }
44  /// Fact          = '(' Expr ')'
45  ///                 | 'LAG' '(' varId ',' ['+' | '-' ] number ')'
46  ///                 | funcId '(' ArgList ')'
47  ///                 | VarExpr | number
48  /// ArgList       = Expr { ',' Expr }
49  /// VarExpr       = varId OptFactorPart
50  /// OptFactorPart = [ ('=' varVal | '[' ['+' | '-' ] number {',' ['+' | '-' ] number } ']' ) ]
51  /// varId         =  ident | ' ident ' | " ident "
52  /// varVal        =  ident | ' ident ' | " ident "
53  /// ident         =  '_' | letter { '_' | letter | digit }
54  /// </summary>
55  public sealed class InfixExpressionParser {
56    private enum TokenType { Operator, Identifier, Number, LeftPar, RightPar, LeftBracket, RightBracket, Comma, Eq, End, NA };
57    private class Token {
58      internal double doubleVal;
59      internal string strVal;
60      internal TokenType TokenType;
61    }
62
63    private class SymbolNameComparer : IEqualityComparer<ISymbol>, IComparer<ISymbol> {
64      public int Compare(ISymbol x, ISymbol y) {
65        return x.Name.CompareTo(y.Name);
66      }
67
68      public bool Equals(ISymbol x, ISymbol y) {
69        return Compare(x, y) == 0;
70      }
71
72      public int GetHashCode(ISymbol obj) {
73        return obj.Name.GetHashCode();
74      }
75    }
76    // format name <-> symbol
77    // the lookup table is also used in the corresponding formatter
78    internal static readonly BidirectionalLookup<string, ISymbol>
79      knownSymbols = new BidirectionalLookup<string, ISymbol>(StringComparer.InvariantCulture, new SymbolNameComparer());
80
81    private Constant constant = new Constant();
82    private Variable variable = new Variable();
83    private BinaryFactorVariable binaryFactorVar = new BinaryFactorVariable();
84    private FactorVariable factorVar = new FactorVariable();
85
86    private ProgramRootSymbol programRootSymbol = new ProgramRootSymbol();
87    private StartSymbol startSymbol = new StartSymbol();
88
89    static InfixExpressionParser() {
90      // populate bidirectional lookup
91      var dict = new Dictionary<string, ISymbol>
92      {
93        { "+", new Addition()},
94        { "/", new Division()},
95        { "*", new Multiplication()},
96        { "-", new Subtraction()},
97        { "ABS", new Absolute() },
98        { "EXP", new Exponential()},
99        { "LOG", new Logarithm()},
100        { "POW", new Power()},
101        { "ROOT", new Root()},
102        { "SQR", new Square() },
103        { "SQRT", new SquareRoot() },
104        { "CUBE", new Cube() },
105        { "CUBEROOT", new CubeRoot() },
106        { "SIN",new Sine()},
107        { "COS", new Cosine()},
108        { "TAN", new Tangent()},
109        { "AIRYA", new AiryA()},
110        { "AIRYB", new AiryB()},
111        { "BESSEL", new Bessel()},
112        { "COSINT", new CosineIntegral()},
113        { "SININT", new SineIntegral()},
114        { "HYPCOSINT", new HyperbolicCosineIntegral()},
115        { "HYPSININT", new HyperbolicSineIntegral()},
116        { "FRESNELSININT", new FresnelSineIntegral()},
117        { "FRESNELCOSINT", new FresnelCosineIntegral()},
118        { "NORM", new Norm()},
119        { "ERF", new Erf()},
120        { "GAMMA", new Gamma()},
121        { "PSI", new Psi()},
122        { "DAWSON", new Dawson()},
123        { "EXPINT", new ExponentialIntegralEi()},
124        { "AQ", new AnalyticalQuotient() },
125        { "MEAN", new Average()},
126        { "IF", new IfThenElse()},
127        { "GT", new GreaterThan()},
128        { "LT", new LessThan()},
129        { "AND", new And()},
130        { "OR", new Or()},
131        { "NOT", new Not()},
132        { "XOR", new Xor()},
133        { "DIFF", new Derivative()},
134        { "LAG", new LaggedVariable() },
135      };
136
137
138      foreach (var kvp in dict) {
139        knownSymbols.Add(kvp.Key, kvp.Value);
140      }
141    }
142
143    public ISymbolicExpressionTree Parse(string str) {
144      ISymbolicExpressionTreeNode root = programRootSymbol.CreateTreeNode();
145      ISymbolicExpressionTreeNode start = startSymbol.CreateTreeNode();
146      var allTokens = GetAllTokens(str).ToArray();
147      ISymbolicExpressionTreeNode mainBranch = ParseS(new Queue<Token>(allTokens));
148
149      // only a main branch was given => insert the main branch into the default tree template
150      root.AddSubtree(start);
151      start.AddSubtree(mainBranch);
152      return new SymbolicExpressionTree(root);
153    }
154
155    private IEnumerable<Token> GetAllTokens(string str) {
156      int pos = 0;
157      while (true) {
158        while (pos < str.Length && Char.IsWhiteSpace(str[pos])) pos++;
159        if (pos >= str.Length) {
160          yield return new Token { TokenType = TokenType.End, strVal = "" };
161          yield break;
162        }
163        if (char.IsDigit(str[pos])) {
164          // read number (=> read until white space or operator or comma)
165          var sb = new StringBuilder();
166          sb.Append(str[pos]);
167          pos++;
168          while (pos < str.Length && !char.IsWhiteSpace(str[pos])
169            && (str[pos] != '+' || str[pos - 1] == 'e' || str[pos - 1] == 'E')     // continue reading exponents
170            && (str[pos] != '-' || str[pos - 1] == 'e' || str[pos - 1] == 'E')
171            && str[pos] != '*'
172            && str[pos] != '/'
173            && str[pos] != ')'
174            && str[pos] != ']'
175            && str[pos] != ',') {
176            sb.Append(str[pos]);
177            pos++;
178          }
179          double dblVal;
180          if (double.TryParse(sb.ToString(), NumberStyles.Float, CultureInfo.InvariantCulture, out dblVal))
181            yield return new Token { TokenType = TokenType.Number, strVal = sb.ToString(), doubleVal = dblVal };
182          else yield return new Token { TokenType = TokenType.NA, strVal = sb.ToString() };
183        } else if (char.IsLetter(str[pos]) || str[pos] == '_') {
184          // read ident
185          var sb = new StringBuilder();
186          sb.Append(str[pos]);
187          pos++;
188          while (pos < str.Length &&
189            (char.IsLetter(str[pos]) || str[pos] == '_' || char.IsDigit(str[pos]))) {
190            sb.Append(str[pos]);
191            pos++;
192          }
193          yield return new Token { TokenType = TokenType.Identifier, strVal = sb.ToString() };
194        } else if (str[pos] == '"') {
195          // read to next "
196          pos++;
197          var sb = new StringBuilder();
198          while (pos < str.Length && str[pos] != '"') {
199            sb.Append(str[pos]);
200            pos++;
201          }
202          if (pos < str.Length && str[pos] == '"') {
203            pos++; // skip "
204            yield return new Token { TokenType = TokenType.Identifier, strVal = sb.ToString() };
205          } else
206            yield return new Token { TokenType = TokenType.NA };
207
208        } else if (str[pos] == '\'') {
209          // read to next '
210          pos++;
211          var sb = new StringBuilder();
212          while (pos < str.Length && str[pos] != '\'') {
213            sb.Append(str[pos]);
214            pos++;
215          }
216          if (pos < str.Length && str[pos] == '\'') {
217            pos++; // skip '
218            yield return new Token { TokenType = TokenType.Identifier, strVal = sb.ToString() };
219          } else
220            yield return new Token { TokenType = TokenType.NA };
221        } else if (str[pos] == '+') {
222          pos++;
223          yield return new Token { TokenType = TokenType.Operator, strVal = "+" };
224        } else if (str[pos] == '-') {
225          pos++;
226          yield return new Token { TokenType = TokenType.Operator, strVal = "-" };
227        } else if (str[pos] == '/') {
228          pos++;
229          yield return new Token { TokenType = TokenType.Operator, strVal = "/" };
230        } else if (str[pos] == '*') {
231          pos++;
232          yield return new Token { TokenType = TokenType.Operator, strVal = "*" };
233        } else if (str[pos] == '(') {
234          pos++;
235          yield return new Token { TokenType = TokenType.LeftPar, strVal = "(" };
236        } else if (str[pos] == ')') {
237          pos++;
238          yield return new Token { TokenType = TokenType.RightPar, strVal = ")" };
239        } else if (str[pos] == '[') {
240          pos++;
241          yield return new Token { TokenType = TokenType.LeftBracket, strVal = "[" };
242        } else if (str[pos] == ']') {
243          pos++;
244          yield return new Token { TokenType = TokenType.RightBracket, strVal = "]" };
245        } else if (str[pos] == '=') {
246          pos++;
247          yield return new Token { TokenType = TokenType.Eq, strVal = "=" };
248        } else if (str[pos] == ',') {
249          pos++;
250          yield return new Token { TokenType = TokenType.Comma, strVal = "," };
251        } else {
252          throw new ArgumentException("Invalid character: " + str[pos]);
253        }
254      }
255    }
256    /// S             = Expr EOF
257    private ISymbolicExpressionTreeNode ParseS(Queue<Token> tokens) {
258      var expr = ParseExpr(tokens);
259
260      var endTok = tokens.Dequeue();
261      if (endTok.TokenType != TokenType.End)
262        throw new ArgumentException(string.Format("Expected end of expression (got {0})", endTok.strVal));
263
264      return expr;
265    }
266
267    /// Expr          = ['-' | '+'] Term { '+' Term | '-' Term }
268    private ISymbolicExpressionTreeNode ParseExpr(Queue<Token> tokens) {
269      var next = tokens.Peek();
270      var posTerms = new List<ISymbolicExpressionTreeNode>();
271      var negTerms = new List<ISymbolicExpressionTreeNode>();
272      bool negateFirstTerm = false;
273      if (next.TokenType == TokenType.Operator && (next.strVal == "+" || next.strVal == "-")) {
274        tokens.Dequeue();
275        if (next.strVal == "-")
276          negateFirstTerm = true;
277      }
278      var t = ParseTerm(tokens);
279      if (negateFirstTerm) negTerms.Add(t);
280      else posTerms.Add(t);
281
282      next = tokens.Peek();
283      while (next.strVal == "+" || next.strVal == "-") {
284        switch (next.strVal) {
285          case "+": {
286              tokens.Dequeue();
287              var term = ParseTerm(tokens);
288              posTerms.Add(term);
289              break;
290            }
291          case "-": {
292              tokens.Dequeue();
293              var term = ParseTerm(tokens);
294              negTerms.Add(term);
295              break;
296            }
297        }
298        next = tokens.Peek();
299      }
300
301      var sum = GetSymbol("+").CreateTreeNode();
302      foreach (var posTerm in posTerms) sum.AddSubtree(posTerm);
303      if (negTerms.Any()) {
304        if (negTerms.Count == 1) {
305          var sub = GetSymbol("-").CreateTreeNode();
306          sub.AddSubtree(negTerms.Single());
307          sum.AddSubtree(sub);
308        } else {
309          var sumNeg = GetSymbol("+").CreateTreeNode();
310          foreach (var negTerm in negTerms) sumNeg.AddSubtree(negTerm);
311
312          var constNode = (ConstantTreeNode)constant.CreateTreeNode();
313          constNode.Value = -1.0;
314          var prod = GetSymbol("*").CreateTreeNode();
315          prod.AddSubtree(constNode);
316          prod.AddSubtree(sumNeg);
317
318          sum.AddSubtree(prod);
319        }
320      }
321      if (sum.SubtreeCount == 1) return sum.Subtrees.First();
322      else return sum;
323    }
324
325    private ISymbol GetSymbol(string tok) {
326      var symb = knownSymbols.GetByFirst(tok).FirstOrDefault();
327      if (symb == null) throw new ArgumentException(string.Format("Unknown token {0} found.", tok));
328      return symb;
329    }
330
331    /// Term          = Fact { '*' Fact | '/' Fact }
332    private ISymbolicExpressionTreeNode ParseTerm(Queue<Token> tokens) {
333      var factors = new List<ISymbolicExpressionTreeNode>();
334      var firstFactor = ParseFact(tokens);
335      factors.Add(firstFactor);
336
337      var next = tokens.Peek();
338      while (next.strVal == "*" || next.strVal == "/") {
339        switch (next.strVal) {
340          case "*": {
341              tokens.Dequeue();
342              var fact = ParseFact(tokens);
343              factors.Add(fact);
344              break;
345            }
346          case "/": {
347              tokens.Dequeue();
348              var invFact = ParseFact(tokens);
349              var divNode = GetSymbol("/").CreateTreeNode(); // 1/x
350              divNode.AddSubtree(invFact);
351              factors.Add(divNode);
352              break;
353            }
354        }
355
356        next = tokens.Peek();
357      }
358      if (factors.Count == 1) return factors.First();
359      else {
360        var prod = GetSymbol("*").CreateTreeNode();
361        foreach (var f in factors) prod.AddSubtree(f);
362        return prod;
363      }
364    }
365
366    /// Fact          = '(' Expr ')'
367    ///                 | 'LAG' '(' varId ',' ['+' | '-' ] number ')'
368    ///                 | funcId '(' ArgList ')'
369    ///                 | VarExpr | number
370    /// ArgList       = Expr { ',' Expr }
371    /// VarExpr       = varId OptFactorPart
372    /// OptFactorPart = [ ('=' varVal | '[' ['+' | '-' ] number {',' ['+' | '-' ] number } ']' ) ]
373    /// varId         =  ident | ' ident ' | " ident "
374    /// varVal        =  ident | ' ident ' | " ident "
375    /// ident         =  '_' | letter { '_' | letter | digit }
376    private ISymbolicExpressionTreeNode ParseFact(Queue<Token> tokens) {
377      var next = tokens.Peek();
378      if (next.TokenType == TokenType.LeftPar) {
379        tokens.Dequeue();
380        var expr = ParseExpr(tokens);
381        var rPar = tokens.Dequeue();
382        if (rPar.TokenType != TokenType.RightPar)
383          throw new ArgumentException("expected )");
384        return expr;
385      } else if (next.TokenType == TokenType.Identifier) {
386        var idTok = tokens.Dequeue();
387        if (tokens.Peek().TokenType == TokenType.LeftPar) {
388          // function identifier or LAG
389          var funcId = idTok.strVal.ToUpperInvariant();
390
391          var funcNode = GetSymbol(funcId).CreateTreeNode();
392          var lPar = tokens.Dequeue();
393          if (lPar.TokenType != TokenType.LeftPar)
394            throw new ArgumentException("expected (");
395
396          // handle 'lag' specifically
397          if (funcNode.Symbol is LaggedVariable) {
398            var varId = tokens.Dequeue();
399            if (varId.TokenType != TokenType.Identifier) throw new ArgumentException("Identifier expected. Format for lagged variables: \"lag(x, -1)\"");
400            var comma = tokens.Dequeue();
401            if (comma.TokenType != TokenType.Comma) throw new ArgumentException("',' expected, Format for lagged variables: \"lag(x, -1)\"");
402            double sign = 1.0;
403            if (tokens.Peek().strVal == "+" || tokens.Peek().strVal == "-") {
404              // read sign
405              var signTok = tokens.Dequeue();
406              if (signTok.strVal == "-") sign = -1.0;
407            }
408            var lagToken = tokens.Dequeue();
409            if (lagToken.TokenType != TokenType.Number) throw new ArgumentException("Number expected, Format for lagged variables: \"lag(x, -1)\"");
410            if (!lagToken.doubleVal.IsAlmost(Math.Round(lagToken.doubleVal)))
411              throw new ArgumentException("Time lags must be integer values");
412            var laggedVarNode = funcNode as LaggedVariableTreeNode;
413            laggedVarNode.VariableName = varId.strVal;
414            laggedVarNode.Lag = (int)Math.Round(sign * lagToken.doubleVal);
415            laggedVarNode.Weight = 1.0;
416          } else {
417            // functions
418            var args = ParseArgList(tokens);
419            // check number of arguments
420            if (funcNode.Symbol.MinimumArity > args.Length || funcNode.Symbol.MaximumArity < args.Length) {
421              throw new ArgumentException(string.Format("Symbol {0} requires between {1} and  {2} arguments.", funcId,
422                funcNode.Symbol.MinimumArity, funcNode.Symbol.MaximumArity));
423            }
424            foreach (var arg in args) funcNode.AddSubtree(arg);
425          }
426
427          var rPar = tokens.Dequeue();
428          if (rPar.TokenType != TokenType.RightPar)
429            throw new ArgumentException("expected )");
430
431          return funcNode;
432        } else {
433          // variable
434          if (tokens.Peek().TokenType == TokenType.Eq) {
435            // binary factor
436            tokens.Dequeue(); // skip Eq
437            var valTok = tokens.Dequeue();
438            if (valTok.TokenType != TokenType.Identifier) throw new ArgumentException("expected identifier");
439            var binFactorNode = (BinaryFactorVariableTreeNode)binaryFactorVar.CreateTreeNode();
440            binFactorNode.Weight = 1.0;
441            binFactorNode.VariableName = idTok.strVal;
442            binFactorNode.VariableValue = valTok.strVal;
443            return binFactorNode;
444          } else if (tokens.Peek().TokenType == TokenType.LeftBracket) {
445            // factor variable
446            var factorVariableNode = (FactorVariableTreeNode)factorVar.CreateTreeNode();
447            factorVariableNode.VariableName = idTok.strVal;
448
449            tokens.Dequeue(); // skip [
450            var weights = new List<double>();
451            // at least one weight is necessary
452            var sign = 1.0;
453            if (tokens.Peek().TokenType == TokenType.Operator) {
454              var opToken = tokens.Dequeue();
455              if (opToken.strVal == "+") sign = 1.0;
456              else if (opToken.strVal == "-") sign = -1.0;
457              else throw new ArgumentException();
458            }
459            if (tokens.Peek().TokenType != TokenType.Number) throw new ArgumentException("number expected");
460            var weightTok = tokens.Dequeue();
461            weights.Add(sign * weightTok.doubleVal);
462            while (tokens.Peek().TokenType == TokenType.Comma) {
463              // skip comma
464              tokens.Dequeue();
465              if (tokens.Peek().TokenType == TokenType.Operator) {
466                var opToken = tokens.Dequeue();
467                if (opToken.strVal == "+") sign = 1.0;
468                else if (opToken.strVal == "-") sign = -1.0;
469                else throw new ArgumentException();
470              }
471              weightTok = tokens.Dequeue();
472              if (weightTok.TokenType != TokenType.Number) throw new ArgumentException("number expected");
473              weights.Add(sign * weightTok.doubleVal);
474            }
475            var rightBracketToken = tokens.Dequeue();
476            if (rightBracketToken.TokenType != TokenType.RightBracket) throw new ArgumentException("closing bracket ] expected");
477            factorVariableNode.Weights = weights.ToArray();
478            return factorVariableNode;
479          } else {
480            // variable
481            var varNode = (VariableTreeNode)variable.CreateTreeNode();
482            varNode.Weight = 1.0;
483            varNode.VariableName = idTok.strVal;
484            return varNode;
485          }
486        }
487      } else if (next.TokenType == TokenType.Number) {
488        var numTok = tokens.Dequeue();
489        var constNode = (ConstantTreeNode)constant.CreateTreeNode();
490        constNode.Value = numTok.doubleVal;
491        return constNode;
492      } else {
493        throw new ArgumentException(string.Format("unexpected token in expression {0}", next.strVal));
494      }
495    }
496
497    // ArgList = Expr { ',' Expr }
498    private ISymbolicExpressionTreeNode[] ParseArgList(Queue<Token> tokens) {
499      var exprList = new List<ISymbolicExpressionTreeNode>();
500      exprList.Add(ParseExpr(tokens));
501      while (tokens.Peek().TokenType != TokenType.RightPar) {
502        var comma = tokens.Dequeue();
503        if (comma.TokenType != TokenType.Comma) throw new ArgumentException("expected ',' ");
504        exprList.Add(ParseExpr(tokens));
505      }
506      return exprList.ToArray();
507    }
508  }
509}
Note: See TracBrowser for help on using the repository browser.