source: branches/3136_Structural_GP/HeuristicLab.Problems.DataAnalysis.Symbolic/3.4/Importer/InfixExpressionParser.cs @ 18065

Last change on this file since 18065 was 18065, checked in by dpiringe, 9 months ago

#3136

  • modified InfixExpressionParser to fully support SubFunctionSymbol
    • created a SubFunctionTreeNode to store the function arguments
  • modified StructureTemplateView to regenerate the content state
  • first implementation for the main tree build up logic
File size: 22.9 KB
Line 
1#region License Information
2/* HeuristicLab
3 * Copyright (C) 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          = SimpleFact [ '^' SimpleFact ]
45  /// SimpleFact    = '(' Expr ')'
46  ///                 | '{' Expr '}'
47  ///                 | 'LAG' '(' varId ',' ['+' | '-' ] number ')
48  ///                 | funcId '(' ArgList ')'
49  ///                 | VarExpr
50  ///                 | number
51  /// ArgList       = Expr { ',' Expr }
52  /// VarExpr       = varId OptFactorPart
53  /// OptFactorPart = [ ('=' varVal | '[' ['+' | '-' ] number {',' ['+' | '-' ] number } ']' ) ]
54  /// varId         =  ident | ' ident ' | " ident "
55  /// varVal        =  ident | ' ident ' | " ident "
56  /// ident         =  '_' | letter { '_' | letter | digit }
57  /// </summary>
58  public sealed class InfixExpressionParser {
59    private enum TokenType { Operator, Identifier, Number, LeftPar, RightPar, LeftBracket, RightBracket, Comma, Eq, End, NA };
60    private class Token {
61      internal double doubleVal;
62      internal string strVal;
63      internal TokenType TokenType;
64    }
65
66    private class SymbolComparer : IEqualityComparer<ISymbol>, IComparer<ISymbol> {
67      public int Compare(ISymbol x, ISymbol y) {
68        return x.Name.CompareTo(y.Name);
69      }
70
71      public bool Equals(ISymbol x, ISymbol y) {
72        return x.GetType() == y.GetType();
73      }
74
75      public int GetHashCode(ISymbol obj) {
76        return obj.GetType().GetHashCode();
77      }
78    }
79    // format name <-> symbol
80    // the lookup table is also used in the corresponding formatter
81    internal static readonly BidirectionalLookup<string, ISymbol>
82      knownSymbols = new BidirectionalLookup<string, ISymbol>(StringComparer.InvariantCulture, new SymbolComparer());
83
84    private Constant constant = new Constant();
85    private Variable variable = new Variable();
86    private BinaryFactorVariable binaryFactorVar = new BinaryFactorVariable();
87    private FactorVariable factorVar = new FactorVariable();
88
89    private ProgramRootSymbol programRootSymbol = new ProgramRootSymbol();
90    private StartSymbol startSymbol = new StartSymbol();
91
92    static InfixExpressionParser() {
93      // populate bidirectional lookup
94      var dict = new Dictionary<string, ISymbol>
95      {
96        { "+", new Addition()},
97        { "/", new Division()},
98        { "*", new Multiplication()},
99        { "-", new Subtraction()},
100        { "^", new Power() },
101        { "ABS", new Absolute() },
102        { "EXP", new Exponential()},
103        { "LOG", new Logarithm()},
104        { "POW", new Power() },
105        { "ROOT", new Root()},
106        { "SQR", new Square() },
107        { "SQRT", new SquareRoot() },
108        { "CUBE", new Cube() },
109        { "CUBEROOT", new CubeRoot() },
110        { "SIN",new Sine()},
111        { "COS", new Cosine()},
112        { "TAN", new Tangent()},
113        { "TANH", new HyperbolicTangent()},
114        { "AIRYA", new AiryA()},
115        { "AIRYB", new AiryB()},
116        { "BESSEL", new Bessel()},
117        { "COSINT", new CosineIntegral()},
118        { "SININT", new SineIntegral()},
119        { "HYPCOSINT", new HyperbolicCosineIntegral()},
120        { "HYPSININT", new HyperbolicSineIntegral()},
121        { "FRESNELSININT", new FresnelSineIntegral()},
122        { "FRESNELCOSINT", new FresnelCosineIntegral()},
123        { "NORM", new Norm()},
124        { "ERF", new Erf()},
125        { "GAMMA", new Gamma()},
126        { "PSI", new Psi()},
127        { "DAWSON", new Dawson()},
128        { "EXPINT", new ExponentialIntegralEi()},
129        { "AQ", new AnalyticQuotient() },
130        { "MEAN", new Average()},
131        { "IF", new IfThenElse()},
132        { "GT", new GreaterThan()},
133        { "LT", new LessThan()},
134        { "AND", new And()},
135        { "OR", new Or()},
136        { "NOT", new Not()},
137        { "XOR", new Xor()},
138        { "DIFF", new Derivative()},
139        { "LAG", new LaggedVariable() },
140        { "F", new SubFunctionSymbol() }
141      };
142
143
144      foreach (var kvp in dict) {
145        knownSymbols.Add(kvp.Key, kvp.Value);
146      }
147    }
148
149    public ISymbolicExpressionTree Parse(string str) {
150      ISymbolicExpressionTreeNode root = programRootSymbol.CreateTreeNode();
151      ISymbolicExpressionTreeNode start = startSymbol.CreateTreeNode();
152      var allTokens = GetAllTokens(str).ToArray();
153      ISymbolicExpressionTreeNode mainBranch = ParseS(new Queue<Token>(allTokens));
154
155      // only a main branch was given => insert the main branch into the default tree template
156      root.AddSubtree(start);
157      start.AddSubtree(mainBranch);
158      return new SymbolicExpressionTree(root);
159    }
160
161    private IEnumerable<Token> GetAllTokens(string str) {
162      int pos = 0;
163      while (true) {
164        while (pos < str.Length && Char.IsWhiteSpace(str[pos])) pos++;
165        if (pos >= str.Length) {
166          yield return new Token { TokenType = TokenType.End, strVal = "" };
167          yield break;
168        }
169        if (char.IsDigit(str[pos])) {
170          // read number (=> read until white space or operator or comma)
171          var sb = new StringBuilder();
172          sb.Append(str[pos]);
173          pos++;
174          while (pos < str.Length && !char.IsWhiteSpace(str[pos])
175            && (str[pos] != '+' || str[pos - 1] == 'e' || str[pos - 1] == 'E')     // continue reading exponents
176            && (str[pos] != '-' || str[pos - 1] == 'e' || str[pos - 1] == 'E')
177            && str[pos] != '*'
178            && str[pos] != '/'
179            && str[pos] != '^'
180            && str[pos] != ')'
181            && str[pos] != ']'
182            && str[pos] != '}'
183            && str[pos] != ',') {
184            sb.Append(str[pos]);
185            pos++;
186          }
187          double dblVal;
188          if (double.TryParse(sb.ToString(), NumberStyles.Float, CultureInfo.InvariantCulture, out dblVal))
189            yield return new Token { TokenType = TokenType.Number, strVal = sb.ToString(), doubleVal = dblVal };
190          else yield return new Token { TokenType = TokenType.NA, strVal = sb.ToString() };
191        } else if (char.IsLetter(str[pos]) || str[pos] == '_') {
192          // read ident
193          var sb = new StringBuilder();
194          sb.Append(str[pos]);
195          pos++;
196          while (pos < str.Length &&
197            (char.IsLetter(str[pos]) || str[pos] == '_' || char.IsDigit(str[pos]))) {
198            sb.Append(str[pos]);
199            pos++;
200          }
201          yield return new Token { TokenType = TokenType.Identifier, strVal = sb.ToString() };
202        } else if (str[pos] == '"') {
203          // read to next "
204          pos++;
205          var sb = new StringBuilder();
206          while (pos < str.Length && str[pos] != '"') {
207            sb.Append(str[pos]);
208            pos++;
209          }
210          if (pos < str.Length && str[pos] == '"') {
211            pos++; // skip "
212            yield return new Token { TokenType = TokenType.Identifier, strVal = sb.ToString() };
213          } else
214            yield return new Token { TokenType = TokenType.NA };
215
216        } else if (str[pos] == '\'') {
217          // read to next '
218          pos++;
219          var sb = new StringBuilder();
220          while (pos < str.Length && str[pos] != '\'') {
221            sb.Append(str[pos]);
222            pos++;
223          }
224          if (pos < str.Length && str[pos] == '\'') {
225            pos++; // skip '
226            yield return new Token { TokenType = TokenType.Identifier, strVal = sb.ToString() };
227          } else
228            yield return new Token { TokenType = TokenType.NA };
229        } else if (str[pos] == '+') {
230          pos++;
231          yield return new Token { TokenType = TokenType.Operator, strVal = "+" };
232        } else if (str[pos] == '-') {
233          pos++;
234          yield return new Token { TokenType = TokenType.Operator, strVal = "-" };
235        } else if (str[pos] == '/') {
236          pos++;
237          yield return new Token { TokenType = TokenType.Operator, strVal = "/" };
238        } else if (str[pos] == '*') {
239          pos++;
240          yield return new Token { TokenType = TokenType.Operator, strVal = "*" };
241        } else if (str[pos] == '^') {
242          pos++;
243          yield return new Token { TokenType = TokenType.Operator, strVal = "^" };
244        } else if (str[pos] == '(') {
245          pos++;
246          yield return new Token { TokenType = TokenType.LeftPar, strVal = "(" };
247        } else if (str[pos] == ')') {
248          pos++;
249          yield return new Token { TokenType = TokenType.RightPar, strVal = ")" };
250        } else if (str[pos] == '[') {
251          pos++;
252          yield return new Token { TokenType = TokenType.LeftBracket, strVal = "[" };
253        } else if (str[pos] == ']') {
254          pos++;
255          yield return new Token { TokenType = TokenType.RightBracket, strVal = "]" };
256        } else if (str[pos] == '{') {
257          pos++;
258          yield return new Token { TokenType = TokenType.LeftPar, strVal = "{" };
259        } else if (str[pos] == '}') {
260          pos++;
261          yield return new Token { TokenType = TokenType.RightPar, strVal = "}" };
262        } else if (str[pos] == '=') {
263          pos++;
264          yield return new Token { TokenType = TokenType.Eq, strVal = "=" };
265        } else if (str[pos] == ',') {
266          pos++;
267          yield return new Token { TokenType = TokenType.Comma, strVal = "," };
268        } else {
269          throw new ArgumentException("Invalid character: " + str[pos]);
270        }
271      }
272    }
273    /// S             = Expr EOF
274    private ISymbolicExpressionTreeNode ParseS(Queue<Token> tokens) {
275      var expr = ParseExpr(tokens);
276
277      var endTok = tokens.Dequeue();
278      if (endTok.TokenType != TokenType.End)
279        throw new ArgumentException(string.Format("Expected end of expression (got {0})", endTok.strVal));
280
281      return expr;
282    }
283
284    /// Expr          = ['-' | '+'] Term { '+' Term | '-' Term }
285    private ISymbolicExpressionTreeNode ParseExpr(Queue<Token> tokens) {
286      var next = tokens.Peek();
287      var posTerms = new List<ISymbolicExpressionTreeNode>();
288      var negTerms = new List<ISymbolicExpressionTreeNode>();
289      bool negateFirstTerm = false;
290      if (next.TokenType == TokenType.Operator && (next.strVal == "+" || next.strVal == "-")) {
291        tokens.Dequeue();
292        if (next.strVal == "-")
293          negateFirstTerm = true;
294      }
295      var t = ParseTerm(tokens);
296      if (negateFirstTerm) negTerms.Add(t);
297      else posTerms.Add(t);
298
299      next = tokens.Peek();
300      while (next.strVal == "+" || next.strVal == "-") {
301        switch (next.strVal) {
302          case "+": {
303              tokens.Dequeue();
304              var term = ParseTerm(tokens);
305              posTerms.Add(term);
306              break;
307            }
308          case "-": {
309              tokens.Dequeue();
310              var term = ParseTerm(tokens);
311              negTerms.Add(term);
312              break;
313            }
314        }
315        next = tokens.Peek();
316      }
317
318      var sum = GetSymbol("+").CreateTreeNode();
319      foreach (var posTerm in posTerms) sum.AddSubtree(posTerm);
320      if (negTerms.Any()) {
321        if (negTerms.Count == 1) {
322          var sub = GetSymbol("-").CreateTreeNode();
323          sub.AddSubtree(negTerms.Single());
324          sum.AddSubtree(sub);
325        } else {
326          var sumNeg = GetSymbol("+").CreateTreeNode();
327          foreach (var negTerm in negTerms) sumNeg.AddSubtree(negTerm);
328
329          var constNode = (ConstantTreeNode)constant.CreateTreeNode();
330          constNode.Value = -1.0;
331          var prod = GetSymbol("*").CreateTreeNode();
332          prod.AddSubtree(constNode);
333          prod.AddSubtree(sumNeg);
334
335          sum.AddSubtree(prod);
336        }
337      }
338      if (sum.SubtreeCount == 1) return sum.Subtrees.First();
339      else return sum;
340    }
341
342    private ISymbol GetSymbol(string tok) {
343      var symb = knownSymbols.GetByFirst(tok).FirstOrDefault();
344      if (symb == null) throw new ArgumentException(string.Format("Unknown token {0} found.", tok));
345      return symb;
346    }
347
348    /// Term          = Fact { '*' Fact | '/' Fact }
349    private ISymbolicExpressionTreeNode ParseTerm(Queue<Token> tokens) {
350      var factors = new List<ISymbolicExpressionTreeNode>();
351      var firstFactor = ParseFact(tokens);
352      factors.Add(firstFactor);
353
354      var next = tokens.Peek();
355      while (next.strVal == "*" || next.strVal == "/") {
356        switch (next.strVal) {
357          case "*": {
358              tokens.Dequeue();
359              var fact = ParseFact(tokens);
360              factors.Add(fact);
361              break;
362            }
363          case "/": {
364              tokens.Dequeue();
365              var invFact = ParseFact(tokens);
366              var divNode = GetSymbol("/").CreateTreeNode(); // 1/x
367              divNode.AddSubtree(invFact);
368              factors.Add(divNode);
369              break;
370            }
371        }
372
373        next = tokens.Peek();
374      }
375      if (factors.Count == 1) return factors.First();
376      else {
377        var prod = GetSymbol("*").CreateTreeNode();
378        foreach (var f in factors) prod.AddSubtree(f);
379        return prod;
380      }
381    }
382
383    // Fact = SimpleFact ['^' SimpleFact]
384    private ISymbolicExpressionTreeNode ParseFact(Queue<Token> tokens) {
385      var expr = ParseSimpleFact(tokens);
386      var next = tokens.Peek();
387      if (next.TokenType == TokenType.Operator && next.strVal == "^") {
388        tokens.Dequeue(); // skip;
389
390        var p = GetSymbol("^").CreateTreeNode();
391        p.AddSubtree(expr);
392        p.AddSubtree(ParseSimpleFact(tokens));
393        expr = p;
394      }
395      return expr;
396    }
397
398
399    /// SimpleFact   = '(' Expr ')'
400    ///                 | '{' Expr '}'
401    ///                 | 'LAG' '(' varId ',' ['+' | '-' ] number ')'
402    ///                 | funcId '(' ArgList ')
403    ///                 | VarExpr
404    ///                 | number
405    /// ArgList       = Expr { ',' Expr }
406    /// VarExpr       = varId OptFactorPart
407    /// OptFactorPart = [ ('=' varVal | '[' ['+' | '-' ] number {',' ['+' | '-' ] number } ']' ) ]
408    /// varId         =  ident | ' ident ' | " ident "
409    /// varVal        =  ident | ' ident ' | " ident "
410    /// ident         =  '_' | letter { '_' | letter | digit }
411    private ISymbolicExpressionTreeNode ParseSimpleFact(Queue<Token> tokens) {
412      var next = tokens.Peek();
413      if (next.TokenType == TokenType.LeftPar) {
414        var initPar = tokens.Dequeue(); // match par type
415        var expr = ParseExpr(tokens);
416        var rPar = tokens.Dequeue();
417        if (rPar.TokenType != TokenType.RightPar)
418          throw new ArgumentException("expected closing parenthesis");
419        if (initPar.strVal == "(" && rPar.strVal == "}")
420          throw new ArgumentException("expected closing )");
421        if (initPar.strVal == "{" && rPar.strVal == ")")
422          throw new ArgumentException("expected closing }");
423        return expr;
424      } else if (next.TokenType == TokenType.Identifier) {
425        var idTok = tokens.Dequeue();
426        if (tokens.Peek().TokenType == TokenType.LeftPar) {
427          // function identifier or LAG
428          var funcId = idTok.strVal.ToUpperInvariant();
429
430          var funcNode = GetSymbol(funcId).CreateTreeNode();
431          var lPar = tokens.Dequeue();
432          if (lPar.TokenType != TokenType.LeftPar)
433            throw new ArgumentException("expected (");
434
435          // handle 'lag' specifically
436          if (funcNode.Symbol is LaggedVariable) {
437            var varId = tokens.Dequeue();
438            if (varId.TokenType != TokenType.Identifier) throw new ArgumentException("Identifier expected. Format for lagged variables: \"lag(x, -1)\"");
439            var comma = tokens.Dequeue();
440            if (comma.TokenType != TokenType.Comma) throw new ArgumentException("',' expected, Format for lagged variables: \"lag(x, -1)\"");
441            double sign = 1.0;
442            if (tokens.Peek().strVal == "+" || tokens.Peek().strVal == "-") {
443              // read sign
444              var signTok = tokens.Dequeue();
445              if (signTok.strVal == "-") sign = -1.0;
446            }
447            var lagToken = tokens.Dequeue();
448            if (lagToken.TokenType != TokenType.Number) throw new ArgumentException("Number expected, Format for lagged variables: \"lag(x, -1)\"");
449            if (!lagToken.doubleVal.IsAlmost(Math.Round(lagToken.doubleVal)))
450              throw new ArgumentException("Time lags must be integer values");
451            var laggedVarNode = funcNode as LaggedVariableTreeNode;
452            laggedVarNode.VariableName = varId.strVal;
453            laggedVarNode.Lag = (int)Math.Round(sign * lagToken.doubleVal);
454            laggedVarNode.Weight = 1.0;
455          } else if (funcNode.Symbol is SubFunctionSymbol) {
456            var subFunction = funcNode as SubFunctionTreeNode;
457            // input arguments
458            var args = ParseArgList(tokens);
459            IList<string> functionArguments = new List<string>();
460            foreach (var arg in args)
461              if(arg is VariableTreeNode varTreeNode)
462                functionArguments.Add(varTreeNode.VariableName);
463            subFunction.FunctionArguments = functionArguments;
464          } else {
465            // functions
466            var args = ParseArgList(tokens);
467            // check number of arguments
468            if (funcNode.Symbol.MinimumArity > args.Length || funcNode.Symbol.MaximumArity < args.Length) {
469              throw new ArgumentException(string.Format("Symbol {0} requires between {1} and {2} arguments.", funcId,
470                funcNode.Symbol.MinimumArity, funcNode.Symbol.MaximumArity));
471            }
472            foreach (var arg in args) funcNode.AddSubtree(arg);
473          }
474
475          var rPar = tokens.Dequeue();
476          if (rPar.TokenType != TokenType.RightPar)
477            throw new ArgumentException("expected )");
478
479
480          return funcNode;
481        } else {
482          // variable
483          if (tokens.Peek().TokenType == TokenType.Eq) {
484            // binary factor
485            tokens.Dequeue(); // skip Eq
486            var valTok = tokens.Dequeue();
487            if (valTok.TokenType != TokenType.Identifier) throw new ArgumentException("expected identifier");
488            var binFactorNode = (BinaryFactorVariableTreeNode)binaryFactorVar.CreateTreeNode();
489            binFactorNode.Weight = 1.0;
490            binFactorNode.VariableName = idTok.strVal;
491            binFactorNode.VariableValue = valTok.strVal;
492            return binFactorNode;
493          } else if (tokens.Peek().TokenType == TokenType.LeftBracket) {
494            // factor variable
495            var factorVariableNode = (FactorVariableTreeNode)factorVar.CreateTreeNode();
496            factorVariableNode.VariableName = idTok.strVal;
497
498            tokens.Dequeue(); // skip [
499            var weights = new List<double>();
500            // at least one weight is necessary
501            var sign = 1.0;
502            if (tokens.Peek().TokenType == TokenType.Operator) {
503              var opToken = tokens.Dequeue();
504              if (opToken.strVal == "+") sign = 1.0;
505              else if (opToken.strVal == "-") sign = -1.0;
506              else throw new ArgumentException();
507            }
508            if (tokens.Peek().TokenType != TokenType.Number) throw new ArgumentException("number expected");
509            var weightTok = tokens.Dequeue();
510            weights.Add(sign * weightTok.doubleVal);
511            while (tokens.Peek().TokenType == TokenType.Comma) {
512              // skip comma
513              tokens.Dequeue();
514              if (tokens.Peek().TokenType == TokenType.Operator) {
515                var opToken = tokens.Dequeue();
516                if (opToken.strVal == "+") sign = 1.0;
517                else if (opToken.strVal == "-") sign = -1.0;
518                else throw new ArgumentException();
519              }
520              weightTok = tokens.Dequeue();
521              if (weightTok.TokenType != TokenType.Number) throw new ArgumentException("number expected");
522              weights.Add(sign * weightTok.doubleVal);
523            }
524            var rightBracketToken = tokens.Dequeue();
525            if (rightBracketToken.TokenType != TokenType.RightBracket) throw new ArgumentException("closing bracket ] expected");
526            factorVariableNode.Weights = weights.ToArray();
527            return factorVariableNode;
528          } else {
529            // variable
530            var varNode = (VariableTreeNode)variable.CreateTreeNode();
531            varNode.Weight = 1.0;
532            varNode.VariableName = idTok.strVal;
533            return varNode;
534          }
535        }
536      } else if (next.TokenType == TokenType.Number) {
537        var numTok = tokens.Dequeue();
538        var constNode = (ConstantTreeNode)constant.CreateTreeNode();
539        constNode.Value = numTok.doubleVal;
540        return constNode;
541      } else {
542        throw new ArgumentException(string.Format("unexpected token in expression {0}", next.strVal));
543      }
544    }
545
546    // ArgList = Expr { ',' Expr }
547    private ISymbolicExpressionTreeNode[] ParseArgList(Queue<Token> tokens) {
548      var exprList = new List<ISymbolicExpressionTreeNode>();
549      exprList.Add(ParseExpr(tokens));
550      while (tokens.Peek().TokenType != TokenType.RightPar) {
551        var comma = tokens.Dequeue();
552        if (comma.TokenType != TokenType.Comma) throw new ArgumentException("expected ',' ");
553        exprList.Add(ParseExpr(tokens));
554      }
555      return exprList.ToArray();
556    }
557  }
558}
Note: See TracBrowser for help on using the repository browser.