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

Last change on this file since 16352 was 16352, checked in by gkronber, 9 months ago

#2915: added support for expressions like "x c" as well as support for '{' '}' as alternatives to '(' ')' to the infix parser

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