Free cookie consent management tool by TermsFeed Policy Generator

source: branches/HeuristicLab.BottomUpTreeDistance/HeuristicLab.Tests/SymbolicExpressionImporter.cs @ 11219

Last change on this file since 11219 was 11219, checked in by bburlacu, 10 years ago

#2215: Refactored the tree distance calculators as similarity calculators (extending SingleObjectiveSolutionSimilarityCalculator). Removed ISymbolicExpressionTreeDistanceCalculator interface. Made small performance enhancements to the BottomUpSimilarityCalculator. Added unit tests to check correctness and performance of bottom up similarity. Added SingleObjectivePopulationDiversityAnalyzer in the default operators list along with the BottomUpSimilarityCalculator.

File size: 10.5 KB
Line 
1#region License Information
2/* HeuristicLab
3 * Copyright (C) 2002-2014 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.Diagnostics;
25using System.Globalization;
26using System.Linq;
27using HeuristicLab.Encodings.SymbolicExpressionTreeEncoding;
28
29namespace HeuristicLab.Problems.DataAnalysis.Symbolic.Tests {
30  internal class SymbolicExpressionImporter {
31    private const string VARSTART = "VAR";
32    private const string LAGGEDVARSTART = "LAGVARIABLE";
33    private const string INTEGRALSTART = "INTEG";
34    private const string DEFUNSTART = "DEFUN";
35    private const string ARGSTART = "ARG";
36    private const string INVOKESTART = "CALL";
37    private const string TIMELAGSTART = "LAG";
38    private Dictionary<string, Symbol> knownSymbols = new Dictionary<string, Symbol>()
39      {
40        {"+", new Addition()},
41        {"/", new Division()},
42        {"*", new Multiplication()},
43        {"-", new Subtraction()},
44        {"EXP", new Exponential()},
45        {"LOG", new Logarithm()},
46        {"POW", new Power()},
47        {"ROOT", new Root()},
48        {"SIN",new Sine()},
49        {"COS", new Cosine()},
50        {"TAN", new Tangent()},
51        {"AIRYA", new AiryA()},
52        {"AIRYB", new AiryB()},
53        {"BESSEL", new Bessel()},
54        {"COSINT", new CosineIntegral()},
55        {"SININT", new SineIntegral()},
56        {"HYPCOSINT", new HyperbolicCosineIntegral()},
57        {"HYPSININT", new HyperbolicSineIntegral()},
58        {"FRESNELSININT", new FresnelSineIntegral()},
59        {"FRESNELCOSINT", new FresnelCosineIntegral()},
60        {"NORM", new Norm()},
61        {"ERF", new Erf()},
62        {"GAMMA", new Gamma()},
63        {"PSI", new Psi()},
64        {"DAWSON", new Dawson()},
65        {"EXPINT", new ExponentialIntegralEi()},
66        {"MEAN", new Average()},
67        {"IF", new IfThenElse()},
68        {">", new GreaterThan()},
69        {"<", new LessThan()},
70        {"AND", new And()},
71        {"OR", new Or()},
72        {"NOT", new Not()},
73        {"XOR", new Xor()},
74        {"DIFF", new Derivative()},
75        {"PROG", new ProgramRootSymbol()},
76        {"MAIN", new StartSymbol()},
77      };
78
79    Constant constant = new Constant();
80    Variable variable = new Variable();
81    LaggedVariable laggedVariable = new LaggedVariable();
82    Defun defun = new Defun();
83    TimeLag timeLag = new TimeLag();
84    Integral integral = new Integral();
85
86    ProgramRootSymbol programRootSymbol = new ProgramRootSymbol();
87    StartSymbol startSymbol = new StartSymbol();
88
89    internal ISymbolicExpressionTree Import(string str) {
90      str = str.Replace("(", " ( ").Replace(")", " ) ");
91      ISymbolicExpressionTreeNode root = programRootSymbol.CreateTreeNode();
92      ISymbolicExpressionTreeNode start = startSymbol.CreateTreeNode();
93      ISymbolicExpressionTreeNode mainBranch = ParseSexp(new Queue<Token>(GetTokenStream(str)));
94      if (mainBranch.Symbol is ProgramRootSymbol) {
95        // when a root symbol was parsed => use main branch as root
96        root = mainBranch;
97      } else {
98        // only a main branch was given => insert the main branch into the default tree template
99        root.AddSubtree(start);
100        start.AddSubtree(mainBranch);
101      }
102      return new SymbolicExpressionTree(root);
103    }
104
105    private IEnumerable<Token> GetTokenStream(string str) {
106      return
107             from strToken in str.Split(new string[] { " " }, StringSplitOptions.RemoveEmptyEntries).AsEnumerable()
108             let t = Token.Parse(strToken)
109             where t != null
110             select t;
111    }
112
113    private ISymbolicExpressionTreeNode ParseSexp(Queue<Token> tokens) {
114      if (tokens.Peek().Symbol == TokenSymbol.LPAR) {
115        ISymbolicExpressionTreeNode tree;
116        Expect(Token.LPAR, tokens);
117        if (tokens.Peek().StringValue.StartsWith(VARSTART)) {
118          tree = ParseVariable(tokens);
119        } else if (tokens.Peek().StringValue.StartsWith(LAGGEDVARSTART)) {
120          tree = ParseLaggedVariable(tokens);
121        } else if (tokens.Peek().StringValue.StartsWith(TIMELAGSTART)) {
122          tree = ParseTimeLag(tokens);
123          tree.AddSubtree(ParseSexp(tokens));
124        } else if (tokens.Peek().StringValue.StartsWith(INTEGRALSTART)) {
125          tree = ParseIntegral(tokens);
126          tree.AddSubtree(ParseSexp(tokens));
127        } else if (tokens.Peek().StringValue.StartsWith(DEFUNSTART)) {
128          tree = ParseDefun(tokens);
129          while (!tokens.Peek().Equals(Token.RPAR)) {
130            tree.AddSubtree(ParseSexp(tokens));
131          }
132        } else if (tokens.Peek().StringValue.StartsWith(ARGSTART)) {
133          tree = ParseArgument(tokens);
134        } else if (tokens.Peek().StringValue.StartsWith(INVOKESTART)) {
135          tree = ParseInvoke(tokens);
136          while (!tokens.Peek().Equals(Token.RPAR)) {
137            tree.AddSubtree(ParseSexp(tokens));
138          }
139        } else {
140          Token curToken = tokens.Dequeue();
141          tree = CreateTree(curToken);
142          while (!tokens.Peek().Equals(Token.RPAR)) {
143            tree.AddSubtree(ParseSexp(tokens));
144          }
145        }
146        Expect(Token.RPAR, tokens);
147        return tree;
148      } else if (tokens.Peek().Symbol == TokenSymbol.NUMBER) {
149        ConstantTreeNode t = (ConstantTreeNode)constant.CreateTreeNode();
150        t.Value = tokens.Dequeue().DoubleValue;
151        return t;
152      } else throw new FormatException("Expected function or constant symbol");
153    }
154
155    private ISymbolicExpressionTreeNode ParseInvoke(Queue<Token> tokens) {
156      Token invokeTok = tokens.Dequeue();
157      Debug.Assert(invokeTok.StringValue == "CALL");
158      InvokeFunction invokeSym = new InvokeFunction(tokens.Dequeue().StringValue);
159      ISymbolicExpressionTreeNode invokeNode = invokeSym.CreateTreeNode();
160      return invokeNode;
161    }
162
163    private ISymbolicExpressionTreeNode ParseArgument(Queue<Token> tokens) {
164      Token argTok = tokens.Dequeue();
165      Debug.Assert(argTok.StringValue == "ARG");
166      Argument argument = new Argument((int)tokens.Dequeue().DoubleValue);
167      ISymbolicExpressionTreeNode argNode = argument.CreateTreeNode();
168      return argNode;
169    }
170
171    private ISymbolicExpressionTreeNode ParseDefun(Queue<Token> tokens) {
172      Token defTok = tokens.Dequeue();
173      Debug.Assert(defTok.StringValue == "DEFUN");
174      DefunTreeNode t = (DefunTreeNode)defun.CreateTreeNode();
175      t.FunctionName = tokens.Dequeue().StringValue;
176      return t;
177    }
178
179    private ISymbolicExpressionTreeNode ParseTimeLag(Queue<Token> tokens) {
180      Token varTok = tokens.Dequeue();
181      Debug.Assert(varTok.StringValue == "LAG");
182      LaggedTreeNode t = (LaggedTreeNode)timeLag.CreateTreeNode();
183      t.Lag = (int)tokens.Dequeue().DoubleValue;
184      return t;
185    }
186
187    private ISymbolicExpressionTreeNode ParseIntegral(Queue<Token> tokens) {
188      Token varTok = tokens.Dequeue();
189      Debug.Assert(varTok.StringValue == "INTEGRAL");
190      LaggedTreeNode t = (LaggedTreeNode)integral.CreateTreeNode();
191      t.Lag = (int)tokens.Dequeue().DoubleValue;
192      return t;
193    }
194
195    private ISymbolicExpressionTreeNode ParseVariable(Queue<Token> tokens) {
196      Token varTok = tokens.Dequeue();
197      Debug.Assert(varTok.StringValue == "VARIABLE");
198      VariableTreeNode t = (VariableTreeNode)variable.CreateTreeNode();
199      t.Weight = tokens.Dequeue().DoubleValue;
200      t.VariableName = tokens.Dequeue().StringValue;
201      return t;
202    }
203
204    private ISymbolicExpressionTreeNode ParseLaggedVariable(Queue<Token> tokens) {
205      Token varTok = tokens.Dequeue();
206      Debug.Assert(varTok.StringValue == "LAGVARIABLE");
207      LaggedVariableTreeNode t = (LaggedVariableTreeNode)laggedVariable.CreateTreeNode();
208      t.Weight = tokens.Dequeue().DoubleValue;
209      t.VariableName = tokens.Dequeue().StringValue;
210      t.Lag = (int)tokens.Dequeue().DoubleValue;
211      return t;
212    }
213
214    private ISymbolicExpressionTreeNode CreateTree(Token token) {
215      if (token.Symbol != TokenSymbol.SYMB) throw new FormatException("Expected function symbol, but got: " + token.StringValue);
216      return knownSymbols[token.StringValue].CreateTreeNode();
217    }
218
219    private void Expect(Token token, Queue<Token> tokens) {
220      Token cur = tokens.Dequeue();
221      if (!token.Equals(cur)) throw new FormatException("Expected: " + token.StringValue + ", but got: " + cur.StringValue);
222    }
223  }
224
225  internal enum TokenSymbol { LPAR, RPAR, SYMB, NUMBER };
226  internal class Token {
227    public static readonly Token LPAR = Token.Parse("(");
228    public static readonly Token RPAR = Token.Parse(")");
229
230    public TokenSymbol Symbol { get; set; }
231    public string StringValue { get; set; }
232    public double DoubleValue { get; set; }
233    public Token() { }
234
235    public override bool Equals(object obj) {
236      Token other = (obj as Token);
237      if (other == null) return false;
238      if (other.Symbol != Symbol) return false;
239      return other.StringValue == this.StringValue;
240    }
241
242    public override int GetHashCode() {
243      return Symbol.GetHashCode() & StringValue.GetHashCode();
244    }
245
246    public static Token Parse(string strToken) {
247      strToken = strToken.Trim();
248      Token t = new Token();
249      t.StringValue = strToken.Trim();
250      double temp;
251      if (strToken == "") {
252        t = null;
253      } else if (strToken == "(") {
254        t.Symbol = TokenSymbol.LPAR;
255      } else if (strToken == ")") {
256        t.Symbol = TokenSymbol.RPAR;
257      } else if (double.TryParse(strToken, NumberStyles.Float, CultureInfo.InvariantCulture.NumberFormat, out temp)) {
258        t.Symbol = TokenSymbol.NUMBER;
259        t.DoubleValue = double.Parse(strToken, CultureInfo.InvariantCulture.NumberFormat);
260      } else {
261        t.Symbol = TokenSymbol.SYMB;
262        t.StringValue = t.StringValue.ToUpper();
263      }
264      return t;
265    }
266  }
267}
Note: See TracBrowser for help on using the repository browser.