source: trunk/HeuristicLab.Problems.DataAnalysis.Symbolic/3.4/Formatters/InfixExpressionFormatter.cs @ 18172

Last change on this file since 18172 was 18172, checked in by gkronber, 8 months ago

#3145: removed unnecessary parenthesis in InfixExpressionFormatter (and adapted the unit tests slightly)

File size: 12.3 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 HEAL.Attic;
28using HeuristicLab.Common;
29using HeuristicLab.Core;
30using HeuristicLab.Encodings.SymbolicExpressionTreeEncoding;
31
32namespace HeuristicLab.Problems.DataAnalysis.Symbolic {
33  public static class BaseInfixExpressionFormatter {
34    public static void FormatRecursively(ISymbolicExpressionTreeNode node, StringBuilder strBuilder,
35                                          NumberFormatInfo numberFormat, string formatString, List<KeyValuePair<string, double>> parameters = null) {
36      if (node.SubtreeCount > 1) {
37        var token = GetToken(node.Symbol);
38        // operators
39        if (token == "+" || token == "-" || token == "OR" || token == "XOR") {
40          var parenthesisRequired = false;
41          if (node.Parent != null && node.Parent.SubtreeCount > 1) {
42            var parentOp = GetToken(node.Parent.Symbol);
43            if (parentOp != "+" && parentOp != "-" && parentOp != "OR" && parentOp != "XOR")
44              parenthesisRequired = true;
45          }
46          if (parenthesisRequired) strBuilder.Append("(");
47          FormatRecursively(node.Subtrees.First(), strBuilder, numberFormat, formatString, parameters);
48
49          foreach (var subtree in node.Subtrees.Skip(1)) {
50            strBuilder.Append(" ").Append(token).Append(" ");
51            FormatRecursively(subtree, strBuilder, numberFormat, formatString, parameters);
52          }
53
54          if (parenthesisRequired) strBuilder.Append(")");
55        } else if (token == "*" || token == "/" || token == "AND") {
56          FormatRecursively(node.Subtrees.First(), strBuilder, numberFormat, formatString, parameters);
57
58          foreach (var subtree in node.Subtrees.Skip(1)) {
59            strBuilder.Append(" ").Append(token).Append(" ");
60            // a / b * c => a / (b * C)
61            if (subtree.SubtreeCount > 1 && token == "/" && GetToken(subtree.Symbol) == "*") {
62              strBuilder.Append("(");
63              FormatRecursively(subtree, strBuilder, numberFormat, formatString, parameters);
64              strBuilder.Append(")");
65            } else {
66              FormatRecursively(subtree, strBuilder, numberFormat, formatString, parameters);
67            }
68          }
69        } else if (token == "^") {
70          // handle integer powers directly
71          FormatRecursively(node.Subtrees.First(), strBuilder, numberFormat, formatString, parameters);
72
73          var power = node.GetSubtree(1);
74          if (power is INumericTreeNode numNode && Math.Truncate(numNode.Value) == numNode.Value) {
75            strBuilder.Append(" ").Append(token).Append(" ").Append(numNode.Value.ToString(formatString, numberFormat));
76          } else {
77            strBuilder.Append(" ").Append(token).Append(" ");
78            FormatRecursively(power, strBuilder, numberFormat, formatString, parameters);
79          }
80        } else {
81          // function with multiple arguments
82          strBuilder.Append(token).Append("(");
83          FormatRecursively(node.Subtrees.First(), strBuilder, numberFormat, formatString, parameters);
84          foreach (var subtree in node.Subtrees.Skip(1)) {
85            strBuilder.Append(", ");
86            FormatRecursively(subtree, strBuilder, numberFormat, formatString, parameters);
87          }
88
89          strBuilder.Append(")");
90        }
91      } else if (node.SubtreeCount == 1) {
92        var token = GetToken(node.Symbol);
93        if (token == "-" || token == "NOT") {
94          strBuilder.Append(token);
95          FormatRecursively(node.GetSubtree(0), strBuilder, numberFormat, formatString, parameters);
96        } else if (token == "/") {
97          strBuilder.Append("1/");
98          FormatRecursively(node.GetSubtree(0), strBuilder, numberFormat, formatString, parameters);
99        } else if (token == "+" || token == "*") {
100          FormatRecursively(node.GetSubtree(0), strBuilder, numberFormat, formatString, parameters);
101        } else {
102          // function with only one argument
103          strBuilder.Append(token).Append("(");
104          FormatRecursively(node.GetSubtree(0), strBuilder, numberFormat, formatString, parameters);
105          strBuilder.Append(")");
106        }
107      } else {
108        // no subtrees
109        if (node.Symbol is LaggedVariable) {
110          var varNode = node as LaggedVariableTreeNode;
111          if (!varNode.Weight.IsAlmost(1.0)) {
112            AppendNumber(strBuilder, parameters, varNode.Weight, formatString, numberFormat);
113            strBuilder.Append("*");
114          }
115
116          strBuilder.Append("LAG(");
117          AppendVariableName(strBuilder, varNode.VariableName);
118          strBuilder.Append(", ")
119                    .AppendFormat(numberFormat, "{0}", varNode.Lag)
120                    .Append(")");
121        } else if (node.Symbol is Variable) {
122          var varNode = node as VariableTreeNode;
123          if (!varNode.Weight.IsAlmost(1.0)) {
124            AppendNumber(strBuilder, parameters, varNode.Weight, formatString, numberFormat);
125            strBuilder.Append("*");
126          }
127          AppendVariableName(strBuilder, varNode.VariableName);
128        } else if (node.Symbol is FactorVariable) {
129          var factorNode = node as FactorVariableTreeNode;
130          AppendVariableName(strBuilder, factorNode.VariableName);
131
132          strBuilder.Append("[");
133          for (int i = 0; i < factorNode.Weights.Length; i++) {
134            if (i > 0) strBuilder.Append(", ");
135            AppendNumber(strBuilder, parameters, factorNode.Weights[i], formatString, numberFormat);
136          }
137          strBuilder.Append("]");
138        } else if (node.Symbol is BinaryFactorVariable) {
139          var factorNode = node as BinaryFactorVariableTreeNode;
140          if (!factorNode.Weight.IsAlmost(1.0)) {
141            AppendNumber(strBuilder, parameters, factorNode.Weight, formatString, numberFormat);
142            strBuilder.Append("*");
143          }
144          AppendVariableName(strBuilder, factorNode.VariableName);
145          strBuilder.Append(" = ");
146          AppendVariableName(strBuilder, factorNode.VariableValue);
147        } else if (node is INumericTreeNode numNode) {
148          if (parameters == null && numNode.Value < 0) {
149            // negative value
150            strBuilder.Append(numNode.Value.ToString(formatString, numberFormat));
151          } else {
152            AppendNumber(strBuilder, parameters, numNode.Value, formatString, numberFormat);
153          }
154        }
155      }
156    }
157
158    private static void AppendNumber(StringBuilder strBuilder, List<KeyValuePair<string, double>> parameters, double value, string formatString, NumberFormatInfo numberFormat) {
159      if (parameters != null) {
160        string paramKey = $"c_{parameters.Count}";
161        strBuilder.AppendFormat(CultureInfo.InvariantCulture, "{0}", paramKey);
162        parameters.Add(new KeyValuePair<string, double>(paramKey, value));
163      } else {
164        strBuilder.Append(value.ToString(formatString, numberFormat));
165      }
166    }
167
168    private static void AppendVariableName(StringBuilder strBuilder, string name) {
169      if (name.Contains("'"))
170        strBuilder.AppendFormat("\"{0}\"", name);
171      else
172        strBuilder.AppendFormat("'{0}'", name);
173    }
174
175    private static string GetToken(ISymbol symbol) {
176      var tok = InfixExpressionParser.knownSymbols.GetBySecond(symbol).FirstOrDefault();
177      if (tok == null)
178        throw new ArgumentException(string.Format("Unknown symbol {0} found.", symbol.Name));
179      return tok;
180    }
181  }
182
183  /// <summary>
184  /// Formats mathematical expressions in infix form. E.g. x1 * (3.0 * x2 + x3)
185  /// </summary>
186  [StorableType("6FE2C83D-A594-4ABF-B101-5AEAEA6D3E3D")]
187  [Item("Infix Symbolic Expression Tree Formatter",
188    "A string formatter that converts symbolic expression trees to infix expressions.")]
189  public sealed class InfixExpressionFormatter : NamedItem, ISymbolicExpressionTreeStringFormatter {
190    [StorableConstructor]
191    private InfixExpressionFormatter(StorableConstructorFlag _) : base(_) { }
192
193    private InfixExpressionFormatter(InfixExpressionFormatter original, Cloner cloner) : base(original, cloner) { }
194
195    public InfixExpressionFormatter()
196      : base() {
197      Name = ItemName;
198      Description = ItemDescription;
199    }
200
201    public override IDeepCloneable Clone(Cloner cloner) {
202      return new InfixExpressionFormatter(this, cloner);
203    }
204
205    /// <summary>
206    /// Produces an infix expression for a given expression tree.
207    /// </summary>
208    /// <param name="symbolicExpressionTree">The tree representation of the expression.</param>
209    /// <param name="numberFormat">Number format that should be used for parameters (e.g. NumberFormatInfo.InvariantInfo (default)).</param>
210    /// <param name="formatString">The format string for parameters (e.g. \"G4\" to limit to 4 digits, default is \"G\")</param>
211    /// <returns>Infix expression</returns>
212    public string Format(ISymbolicExpressionTree symbolicExpressionTree, NumberFormatInfo numberFormat,
213                         string formatString = "G") {
214      // skip root and start symbols
215      StringBuilder strBuilder = new StringBuilder();
216      BaseInfixExpressionFormatter.FormatRecursively(symbolicExpressionTree.Root.GetSubtree(0).GetSubtree(0),
217        strBuilder, numberFormat, formatString);
218      return strBuilder.ToString();
219    }
220
221    public string Format(ISymbolicExpressionTree symbolicExpressionTree) {
222      return Format(symbolicExpressionTree, NumberFormatInfo.InvariantInfo);
223    }
224  }
225
226  [StorableType("54D917E8-134E-4066-9A60-2737C12D81DC")]
227  [Item("Infix String Formater", "Formatter for symbolic expressions, which produces an infix expression " +
228                                 "as well as a list of all coefficient values")]
229  public sealed class InfixExpressionStringFormatter : NamedItem, ISymbolicExpressionTreeStringFormatter {
230    [StorableConstructor]
231    private InfixExpressionStringFormatter(StorableConstructorFlag _) : base(_) { }
232
233    private InfixExpressionStringFormatter(InfixExpressionStringFormatter original, Cloner cloner) : base(original, cloner) { }
234
235    public InfixExpressionStringFormatter() : base() {
236      Name = ItemName;
237      Description = ItemDescription;
238    }
239
240    public override IDeepCloneable Clone(Cloner cloner) {
241      return new InfixExpressionStringFormatter(this, cloner);
242    }
243
244    public string Format(ISymbolicExpressionTree symbolicExpressionTree) {
245      StringBuilder strBuilder = new StringBuilder();
246      var parameters = new List<KeyValuePair<string, double>>();
247      BaseInfixExpressionFormatter.FormatRecursively(symbolicExpressionTree.Root.GetSubtree(0).GetSubtree(0),
248        strBuilder, NumberFormatInfo.InvariantInfo, "G", parameters);
249      strBuilder.Append($"{Environment.NewLine}{Environment.NewLine}");
250
251      int maxDigits = GetDigits(parameters.Count);
252      int padding = parameters.Max(x => x.Value.ToString("F12", CultureInfo.InvariantCulture).Length);
253      foreach (var param in parameters) {
254        int digits = GetDigits(int.Parse(param.Key.Substring(2)));
255        strBuilder.Append($"{param.Key}{new string(' ', maxDigits - digits)} = " +
256                          string.Format($"{{0,{padding}:F12}}", param.Value, CultureInfo.InvariantCulture) +
257                          Environment.NewLine);
258      }
259
260      return strBuilder.ToString();
261    }
262
263    private int GetDigits(int x) {
264      if (x == 0) return 1;
265      return (int)Math.Floor(Math.Log10(x) + 1);
266    }
267  }
268}
Note: See TracBrowser for help on using the repository browser.