1  using System.Collections.Generic;


2  using System.Diagnostics;


3  using System.Linq;


4  using HeuristicLab.Algorithms.DataAnalysis.SymRegGrammarEnumeration.GrammarEnumeration;


5  using HeuristicLab.Encodings.SymbolicExpressionTreeEncoding;


6  using HeuristicLab.Problems.DataAnalysis.Symbolic;


7 


8  namespace HeuristicLab.Algorithms.DataAnalysis.SymRegGrammarEnumeration {


9  public class Grammar {


10 


11  public Symbol StartSymbol { get; }


12 


13  public Hasher<int> Hasher { get; }


14 


15  #region Symbols


16 


17  public IReadOnlyDictionary<Symbol, IReadOnlyList<Production>> Productions { get; }


18 


19  public NonterminalSymbol Var;


20  public IReadOnlyList<VariableTerminalSymbol> VarTerminals;


21 


22  public NonterminalSymbol Expr;


23  public NonterminalSymbol Term;


24  public NonterminalSymbol Factor;


25  public NonterminalSymbol LogFactor;


26  public NonterminalSymbol ExpFactor;


27  public NonterminalSymbol SinFactor;


28  public NonterminalSymbol CosFactor;


29 


30  public NonterminalSymbol SimpleExpr;


31  public NonterminalSymbol SimpleTerm;


32 


33  public NonterminalSymbol InvExpr;


34  public NonterminalSymbol InvTerm;


35 


36  public TerminalSymbol Addition;


37  public TerminalSymbol Multiplication;


38  public TerminalSymbol Log;


39  public TerminalSymbol Exp;


40  public TerminalSymbol Sin;


41  public TerminalSymbol Cos;


42  public TerminalSymbol Inv;


43 


44  public TerminalSymbol Const;


45 


46  #endregion


47 


48  #region HL Symbols for Parsing ExpressionTrees


49 


50  private ISymbol constSy;


51  private ISymbol varSy;


52 


53  private ISymbol addSy;


54  private ISymbol mulSy;


55  private ISymbol logSy;


56  private ISymbol expSy;


57  private ISymbol divSy;


58  private ISymbol sinSy;


59  private ISymbol cosSy;


60 


61  private ISymbol rootSy;


62  private ISymbol startSy;


63 


64  private InfixExpressionFormatter infixExpressionFormatter;


65  #endregion


66 


67  public Grammar(string[] variables) {


68  #region Define Symbols


69  Var = new NonterminalSymbol("Var");


70 


71  Expr = new NonterminalSymbol("Expr");


72  Term = new NonterminalSymbol("Term");


73  Factor = new NonterminalSymbol("Factor");


74  LogFactor = new NonterminalSymbol("LogFactor");


75  ExpFactor = new NonterminalSymbol("ExpFactor");


76  SinFactor = new NonterminalSymbol("SinFactor");


77  CosFactor = new NonterminalSymbol("CosFactor");


78 


79  SimpleExpr = new NonterminalSymbol("SimpleExpr");


80  SimpleTerm = new NonterminalSymbol("SimpleTerm");


81 


82  InvExpr = new NonterminalSymbol("InvExpr");


83  InvTerm = new NonterminalSymbol("InvTerm");


84 


85  Addition = new TerminalSymbol("+");


86  Multiplication = new TerminalSymbol("*");


87  Log = new TerminalSymbol("log");


88  Exp = new TerminalSymbol("exp");


89  Sin = new TerminalSymbol("sin");


90  Cos = new TerminalSymbol("cos");


91  Inv = new TerminalSymbol("inv");


92 


93  Const = new TerminalSymbol("c");


94  #endregion


95 


96  #region Production rules


97  StartSymbol = Expr;


98 


99  Dictionary<Symbol, IReadOnlyList<Production>> productions = new Dictionary<Symbol, IReadOnlyList<Production>>();


100 


101  // Map each variable to a separate production rule of the "Var" nonterminal symbol.


102  VarTerminals = variables.Select(v => new VariableTerminalSymbol(v)).ToArray();


103  productions[Var] = VarTerminals.Select(v => new Production(v)).ToArray();


104 


105  productions[Expr] = new[] {


106  new Production(Const, Term, Multiplication, Expr, Addition),


107  new Production(Const, Term, Multiplication, Const, Addition)


108  };


109 


110  productions[Term] = new[] {


111  new Production(Factor, Term, Multiplication),


112  new Production(Factor),


113  new Production(InvExpr, Inv)


114  };


115 


116  productions[Factor] = new[] {


117  new Production(Var),


118  new Production(LogFactor),


119  new Production(ExpFactor),


120  new Production(SinFactor),


121  new Production(CosFactor),


122  };


123 


124  productions[LogFactor] = new[] { new Production(SimpleExpr, Log) };


125  productions[ExpFactor] = new[] { new Production(Const, SimpleTerm, Multiplication, Exp) };


126  productions[SinFactor] = new[] { new Production(SimpleExpr, Sin) };


127  productions[CosFactor] = new[] { new Production(SimpleExpr, Cos) };


128 


129  productions[SimpleExpr] = new[] {


130  new Production(Const, SimpleTerm, Multiplication, SimpleExpr, Addition),


131  new Production(Const, SimpleTerm, Multiplication, Const, Addition)


132  };


133 


134  productions[SimpleTerm] = new[] {


135  new Production(Var, SimpleTerm, Multiplication),


136  new Production(Var)


137  };


138 


139  productions[InvExpr] = new[] {


140  new Production(Const, InvTerm, Multiplication, InvExpr, Addition),


141  new Production(Const, InvTerm, Multiplication, Const, Addition)


142  };


143 


144  productions[InvTerm] = new[] {


145  new Production(Factor, InvTerm, Multiplication),


146  new Production(Factor)


147  };


148 


149  Productions = productions;


150  #endregion


151 


152  #region Parsing to SymbolicExpressionTree


153  var symbolicExpressionGrammar = new TypeCoherentExpressionGrammar();


154  symbolicExpressionGrammar.ConfigureAsDefaultRegressionGrammar();


155 


156  constSy = symbolicExpressionGrammar.Symbols.OfType<Constant>().First();


157  varSy = symbolicExpressionGrammar.Symbols.OfType<Variable>().First();


158  addSy = symbolicExpressionGrammar.Symbols.OfType<Addition>().First();


159  mulSy = symbolicExpressionGrammar.Symbols.OfType<Multiplication>().First();


160  logSy = symbolicExpressionGrammar.Symbols.OfType<Logarithm>().First();


161  expSy = symbolicExpressionGrammar.Symbols.OfType<Exponential>().First();


162  divSy = symbolicExpressionGrammar.Symbols.OfType<Division>().First();


163  sinSy = symbolicExpressionGrammar.Symbols.OfType<Sine>().First();


164  cosSy = symbolicExpressionGrammar.Symbols.OfType<Cosine>().First();


165 


166  rootSy = symbolicExpressionGrammar.Symbols.OfType<ProgramRootSymbol>().First();


167  startSy = symbolicExpressionGrammar.Symbols.OfType<StartSymbol>().First();


168 


169  infixExpressionFormatter = new InfixExpressionFormatter();


170  #endregion


171 


172  Hasher = new IntHasher(this);


173  }


174 


175  #region Parse to SymbolicExpressionTree


176 


177  public string ToInfixString(SymbolString sentence) {


178  Debug.Assert(sentence.Any(), "Trying to evaluate empty sentence!");


179  Debug.Assert(sentence.All(s => s is TerminalSymbol), "Trying to evaluate symbol sequence with nonterminalsymbols!");


180 


181  return infixExpressionFormatter.Format(ParseSymbolicExpressionTree(sentence));


182  }


183 


184  public SymbolicExpressionTree ParseSymbolicExpressionTree(SymbolString sentence) {


185  Debug.Assert(sentence.Any(), "Trying to evaluate empty sentence!");


186  Debug.Assert(sentence.All(s => s is TerminalSymbol), "Trying to evaluate symbol sequence with nonterminalsymbols!");


187 


188  var rootNode = rootSy.CreateTreeNode();


189  var startNode = startSy.CreateTreeNode();


190  rootNode.AddSubtree(startNode);


191 


192  Stack<TerminalSymbol> parseStack = new Stack<TerminalSymbol>(sentence.OfType<TerminalSymbol>());


193  startNode.AddSubtree(ParseSymbolicExpressionTree(parseStack));


194 


195  return new SymbolicExpressionTree(rootNode);


196  }


197 


198  public ISymbolicExpressionTreeNode ParseSymbolicExpressionTree(Stack<TerminalSymbol> parseStack) {


199  TerminalSymbol currentSymbol = parseStack.Pop();


200 


201  ISymbolicExpressionTreeNode parsedSubTree = null;


202 


203  if (currentSymbol == Addition) {


204  parsedSubTree = addSy.CreateTreeNode();


205  ISymbolicExpressionTreeNode rightSubtree = ParseSymbolicExpressionTree(parseStack);


206  if (rightSubtree is ConstantTreeNode) {


207  ((ConstantTreeNode)rightSubtree).Value = 0.0;


208  }


209  parsedSubTree.AddSubtree(rightSubtree); // left part


210 


211  ISymbolicExpressionTreeNode leftSubtree = ParseSymbolicExpressionTree(parseStack);


212  if (leftSubtree is ConstantTreeNode) {


213  ((ConstantTreeNode)leftSubtree).Value = 0.0;


214  }


215  parsedSubTree.AddSubtree(leftSubtree); // right part


216 


217  } else if (currentSymbol == Multiplication) {


218  parsedSubTree = mulSy.CreateTreeNode();


219  parsedSubTree.AddSubtree(ParseSymbolicExpressionTree(parseStack)); // left part


220  parsedSubTree.AddSubtree(ParseSymbolicExpressionTree(parseStack)); // right part


221 


222  } else if (currentSymbol == Log) {


223  parsedSubTree = logSy.CreateTreeNode();


224  parsedSubTree.AddSubtree(ParseSymbolicExpressionTree(parseStack));


225 


226  } else if (currentSymbol == Exp) {


227  parsedSubTree = expSy.CreateTreeNode();


228  parsedSubTree.AddSubtree(ParseSymbolicExpressionTree(parseStack));


229 


230  } else if (currentSymbol == Sin) {


231  parsedSubTree = sinSy.CreateTreeNode();


232  parsedSubTree.AddSubtree(ParseSymbolicExpressionTree(parseStack));


233 


234  } else if (currentSymbol == Cos) {


235  parsedSubTree = cosSy.CreateTreeNode();


236  parsedSubTree.AddSubtree(ParseSymbolicExpressionTree(parseStack));


237 


238  } else if (currentSymbol == Inv) {


239  parsedSubTree = divSy.CreateTreeNode();


240  ConstantTreeNode dividend = (ConstantTreeNode)constSy.CreateTreeNode();


241  dividend.Value = 1.0;


242  parsedSubTree.AddSubtree(dividend);


243  parsedSubTree.AddSubtree(ParseSymbolicExpressionTree(parseStack));


244 


245  } else if (currentSymbol == Const) {


246  ConstantTreeNode constNode = (ConstantTreeNode)constSy.CreateTreeNode();


247  constNode.Value = 1.0;


248  parsedSubTree = constNode;


249 


250  } else if (currentSymbol is VariableTerminalSymbol) {


251  VariableTreeNode varNode = (VariableTreeNode)varSy.CreateTreeNode();


252  varNode.Weight = 1.0;


253  varNode.VariableName = currentSymbol.StringRepresentation;


254  parsedSubTree = varNode;


255  }


256 


257  Debug.Assert(parsedSubTree != null);


258  return parsedSubTree;


259  }


260  #endregion


261  }


262  }

