Changeset 18216 for branches/3136_Structural_GP/HeuristicLab.Problems.DataAnalysis.Symbolic/3.4/Formatters

Timestamp:

02/10/22 19:48:12 (2 years ago)

Author:

gkronber

Message:

#3136: merged r18203:18211 from trunk to branch. Merged changes, fixed compile problem ('is not')

Location:

branches/3136_Structural_GP

Files:

• . (modified) (1 prop)
• HeuristicLab.Problems.DataAnalysis.Symbolic (modified) (1 prop)
• HeuristicLab.Problems.DataAnalysis.Symbolic/3.4/Formatters/InfixExpressionFormatter.cs (modified) (6 diffs)

branches/3136_Structural_GP/HeuristicLab.Problems.DataAnalysis.Symbolic/3.4/Formatters/InfixExpressionFormatter.cs

@@ -32 +32 @@
 namespace HeuristicLab.Problems.DataAnalysis.Symbolic {
   public static class BaseInfixExpressionFormatter {
+    /// <summary>
+    ///  Performs some basic re-writing steps to simplify the code for formatting. Tree is changed.
+    ///  Removes single-argument +, * which have no effect
+    ///  Removes SubFunctions (no effect)
+    ///  Replaces variables with coefficients by an explicitly multiplication
+    ///  Replaces single-argument / with 1 / (..)
+    ///  Replaces multi-argument +, *, /, - with nested binary operations
+    ///  Rotates operations to remove necessity to group sub-expressions
+    /// </summary>
+    /// <param name="tree">The tree is changed</param>
+    public static void ConvertToBinaryLeftAssoc(ISymbolicExpressionTree tree) {
+      ConvertToBinaryLeftAssocRec(tree.Root.GetSubtree(0), tree.Root.GetSubtree(0).GetSubtree(0));
+    }
+
+    private static void ConvertToBinaryLeftAssocRec(ISymbolicExpressionTreeNode parent, ISymbolicExpressionTreeNode n) {
+      // recurse post-order
+      foreach (var subtree in n.Subtrees.ToArray()) ConvertToBinaryLeftAssocRec(n, subtree); // ToArray required as n.Subtrees is changed in method
+
+      if (n is VariableTreeNode varTreeNode && varTreeNode.Weight != 1.0) {
+        var mul = new Multiplication().CreateTreeNode();
+        var num = (NumberTreeNode)new Number().CreateTreeNode();
+        num.Value = varTreeNode.Weight;
+        varTreeNode.Weight = 1.0;
+        parent.ReplaceSubtree(n, mul);
+        mul.AddSubtree(num);
+        mul.AddSubtree(varTreeNode);
+      } else if (n.Symbol is SubFunctionSymbol) {
+        parent.ReplaceSubtree(n, n.GetSubtree(0));
+      } else if (n.SubtreeCount == 1 && (n.Symbol is Addition || n.Symbol is Multiplication || n.Symbol is And || n.Symbol is Or || n.Symbol is Xor)) {
+        // single-argument addition or multiplication has no effect -> remove
+        parent.ReplaceSubtree(n, n.GetSubtree(0));
+      } else if (n.SubtreeCount == 1 && (n.Symbol is Division)) {
+        // single-argument division is 1/f(x)
+        n.InsertSubtree(0, new Constant() { Value = 1.0 }.CreateTreeNode());
+      } else if (n.SubtreeCount > 2 && IsLeftAssocOp(n.Symbol)) {
+        // multi-argument +, -, *, / are the same as multiple binary operations (left-associative)
+        var sy = n.Symbol;
+
+        var additionalTrees = n.Subtrees.Skip(2).ToArray();
+        while (n.SubtreeCount > 2) n.RemoveSubtree(2); // keep only the first two arguments
+
+        var childIdx = parent.IndexOfSubtree(n);
+        parent.RemoveSubtree(childIdx);
+        var newChild = n;
+        // build a tree bottom to top, each time adding a subtree on the right
+        for (int i = 0; i < additionalTrees.Length; i++) {
+          var newOp = sy.CreateTreeNode();
+          newOp.AddSubtree(newChild);
+          newOp.AddSubtree(additionalTrees[i]);
+          newChild = newOp;
+        }
+        parent.InsertSubtree(childIdx, newChild);
+      } else if (n.SubtreeCount == 2 && n.GetSubtree(1).SubtreeCount == 2 &&
+                 IsAssocOp(n.Symbol) && IsOperator(n.GetSubtree(1).Symbol) &&
+                 Priority(n.Symbol) == Priority(n.GetSubtree(1).Symbol)) {
+        // f(x) <op> (g(x) <op> h(x))) is the same as  (f(x) <op> g(x)) <op> h(x) for associative <op>
+        // which is the same as f(x) <op> g(x) <op> h(x) for left-associative <op>
+        // The latter version is preferred because we do not need to write the parentheses.
+        // rotation:
+        //     (op1)              (op2)
+        //     /   \              /  \
+        //    a    (op2)       (op1)  c 
+        //         /  \        /  \
+        //        b    c      a    b      
+        var op1 = n;
+        var op2 = n.GetSubtree(1);
+        var b = op2.GetSubtree(0); op2.RemoveSubtree(0);
+        op1.ReplaceSubtree(op2, b);
+        parent.ReplaceSubtree(op1, op2);
+        op2.InsertSubtree(0, op1);
+      }
+    }
     public static void FormatRecursively(ISymbolicExpressionTreeNode node, StringBuilder strBuilder,
                                           NumberFormatInfo numberFormat, string formatString, List<KeyValuePair<string, double>> parameters = null) {
-      if (node.SubtreeCount > 1) {
-        var token = GetToken(node.Symbol);
-        // operators
-        if (token == "+" || token == "-" || token == "OR" || token == "XOR") {
-          var parenthesisRequired = false;
-          if (node.Parent != null && node.Parent.SubtreeCount > 1) {
-            var parentOp = GetToken(node.Parent.Symbol);
-            if (parentOp != "+" && parentOp != "-" && parentOp != "OR" && parentOp != "XOR")
-              parenthesisRequired = true;
-          }
+      // This method assumes that the tree has been converted to binary and left-assoc form (see ConvertToBinaryLeftAssocRec). 
+      if (node.SubtreeCount == 0) {
+        // no subtrees
+        if (node.Symbol is Variable) {
+          var varNode = node as VariableTreeNode;
+          if (varNode.Weight != 1.0) { throw new NotSupportedException("Infix formatter does not support variables with coefficients."); }
+          AppendVariableName(strBuilder, varNode.VariableName);
+        } else if (node is INumericTreeNode numNode) {
+          var parenthesisRequired = RequiresParenthesis(node.Parent, node);
           if (parenthesisRequired) strBuilder.Append("(");
-          FormatRecursively(node.Subtrees.First(), strBuilder, numberFormat, formatString, parameters);
-
-          foreach (var subtree in node.Subtrees.Skip(1)) {
-            strBuilder.Append(" ").Append(token).Append(" ");
-            FormatRecursively(subtree, strBuilder, numberFormat, formatString, parameters);
-          }
-
+
+          AppendNumber(strBuilder, parameters, numNode.Value, formatString, numberFormat);
           if (parenthesisRequired) strBuilder.Append(")");
-        } else if (token == "*" || token == "/" || token == "AND") {
-          FormatRecursively(node.Subtrees.First(), strBuilder, numberFormat, formatString, parameters);
-
-          foreach (var subtree in node.Subtrees.Skip(1)) {
-            strBuilder.Append(" ").Append(token).Append(" ");
-            // a / b * c => a / (b * C)
-            if (subtree.SubtreeCount > 1 && token == "/" && GetToken(subtree.Symbol) == "*") {
-              strBuilder.Append("(");
-              FormatRecursively(subtree, strBuilder, numberFormat, formatString, parameters);
-              strBuilder.Append(")");
-            } else {
-              FormatRecursively(subtree, strBuilder, numberFormat, formatString, parameters);
-            }
-          }
-        } else if (token == "^") {
-          // handle integer powers directly
-          FormatRecursively(node.Subtrees.First(), strBuilder, numberFormat, formatString, parameters);
-
-          var power = node.GetSubtree(1);
-          if (power is INumericTreeNode numNode && Math.Truncate(numNode.Value) == numNode.Value) {
-            strBuilder.Append(" ").Append(token).Append(" ").Append(numNode.Value.ToString(formatString, numberFormat));
-          } else {
-            strBuilder.Append(" ").Append(token).Append(" ");
-            FormatRecursively(power, strBuilder, numberFormat, formatString, parameters);
-          }
-        } else {
-          // function with multiple arguments
-          strBuilder.Append(token).Append("(");
-          FormatRecursively(node.Subtrees.First(), strBuilder, numberFormat, formatString, parameters);
-          foreach (var subtree in node.Subtrees.Skip(1)) {
-            strBuilder.Append(", ");
-            FormatRecursively(subtree, strBuilder, numberFormat, formatString, parameters);
-          }
-
-          strBuilder.Append(")");
-        }
-      } else if (node.Symbol is SubFunctionSymbol) {
-        FormatRecursively(node.GetSubtree(0), strBuilder, numberFormat, formatString, parameters);
-      } else if (node.SubtreeCount == 1) {
-        var token = GetToken(node.Symbol);
-        if (token == "-" || token == "NOT") {
-          strBuilder.Append(token);
-          FormatRecursively(node.GetSubtree(0), strBuilder, numberFormat, formatString, parameters);
-        } else if (token == "/") {
-          strBuilder.Append("1/");
-          FormatRecursively(node.GetSubtree(0), strBuilder, numberFormat, formatString, parameters);
-        } else if (token == "+" || token == "*") {
-          FormatRecursively(node.GetSubtree(0), strBuilder, numberFormat, formatString, parameters);
-        } else {
-          // function with only one argument
-          strBuilder.Append(token).Append("(");
-          FormatRecursively(node.GetSubtree(0), strBuilder, numberFormat, formatString, parameters);
-          strBuilder.Append(")");
-        }
-      } else {
-        // no subtrees
-        if (node.Symbol is LaggedVariable) {
+        } else if (node.Symbol is LaggedVariable) {
           var varNode = node as LaggedVariableTreeNode;
           if (!varNode.Weight.IsAlmost(1.0)) {
@@ -121 +131 @@
                     .AppendFormat(numberFormat, "{0}", varNode.Lag)
                     .Append(")");
-        } else if (node.Symbol is Variable) {
-          var varNode = node as VariableTreeNode;
-          if (!varNode.Weight.IsAlmost(1.0)) {
-            AppendNumber(strBuilder, parameters, varNode.Weight, formatString, numberFormat);
-            strBuilder.Append("*");
-          }
-          AppendVariableName(strBuilder, varNode.VariableName);
         } else if (node.Symbol is FactorVariable) {
           var factorNode = node as FactorVariableTreeNode;
@@ -147 +150 @@
           strBuilder.Append(" = ");
           AppendVariableName(strBuilder, factorNode.VariableValue);
-        } else if (node is INumericTreeNode numNode) {
-          if (parameters == null && numNode.Value < 0) {
-            // negative value
-            strBuilder.Append(numNode.Value.ToString(formatString, numberFormat));
-          } else {
-            AppendNumber(strBuilder, parameters, numNode.Value, formatString, numberFormat);
-          }
         }
-      }
+      } else if (node.SubtreeCount == 1) {
+        // only functions and single-argument subtraction (=negation) or NOT are possible here.
+        var token = GetToken(node.Symbol);
+        // the only operators that are allowed with a single argument
+        if (node.Symbol is Subtraction || node.Symbol is Not) {
+          if (RequiresParenthesis(node.Parent, node)) {
+            strBuilder.Append("(");
+          }
+          strBuilder.Append(token);
+          FormatRecursively(node.GetSubtree(0), strBuilder, numberFormat, formatString, parameters);
+          if (RequiresParenthesis(node.Parent, node)) {
+            strBuilder.Append(")");
+          }
+        } else if (IsOperator(node.Symbol)) {
+          throw new FormatException("Single-argument version of " + node.Symbol.Name + " is not supported.");
+        } else {
+          // function with only one argument
+          strBuilder.Append(token);
+          strBuilder.Append("(");
+          FormatRecursively(node.GetSubtree(0), strBuilder, numberFormat, formatString, parameters);
+          strBuilder.Append(")");
+        }
+      } else if (node.SubtreeCount > 1) {
+        var token = GetToken(node.Symbol);
+        // operators
+        if (IsOperator(node.Symbol)) {
+          var parenthesisRequired = RequiresParenthesis(node.Parent, node);
+          if (parenthesisRequired) strBuilder.Append("(");
+          FormatRecursively(node.Subtrees.First(), strBuilder, numberFormat, formatString, parameters);
+
+          foreach (var subtree in node.Subtrees.Skip(1)) {
+            strBuilder.Append(" ").Append(token).Append(" ");
+            FormatRecursively(subtree, strBuilder, numberFormat, formatString, parameters);
+          }
+
+          if (parenthesisRequired) strBuilder.Append(")");
+        } else {
+          // function with multiple arguments (AQ)
+
+          strBuilder.Append(token);
+          strBuilder.Append("(");
+
+          FormatRecursively(node.Subtrees.First(), strBuilder, numberFormat, formatString, parameters);
+          foreach (var subtree in node.Subtrees.Skip(1)) {
+            strBuilder.Append(", ");
+            FormatRecursively(subtree, strBuilder, numberFormat, formatString, parameters);
+          }
+          strBuilder.Append(")");
+        }
+      }
+    }
+
+    private static int Priority(ISymbol symbol) {
+      if (symbol is Addition || symbol is Subtraction || symbol is Or || symbol is Xor) return 1;
+      if (symbol is Division || symbol is Multiplication || symbol is And) return 2;
+      if (symbol is Power || symbol is Not) return 3;
+      throw new NotSupportedException();
+    }
+
+    private static bool RequiresParenthesis(ISymbolicExpressionTreeNode parent, ISymbolicExpressionTreeNode child) {
+      if (child.SubtreeCount > 2 && IsOperator(child.Symbol)) throw new NotSupportedException("Infix formatter does not support operators with more than two children.");
+
+      // Basically: We need a parenthesis for child if the parent symbol binds stronger than child symbol.
+      if (parent.Symbol == null || parent.Symbol is ProgramRootSymbol || parent.Symbol is StartSymbol) return false;
+      if (IsFunction(parent.Symbol)) return false;
+      if (parent.SubtreeCount == 1 && (parent.Symbol is Subtraction)) return true;
+      if (child.SubtreeCount == 0) return false;
+      var parentPrio = Priority(parent.Symbol);
+      var childPrio = Priority(child.Symbol);
+      if (parentPrio > childPrio) return true;
+      else if (parentPrio == childPrio) {
+        if (IsLeftAssocOp(child.Symbol)) return parent.GetSubtree(0) != child; // (..) required only for right child for left-assoc op
+        if (IsRightAssocOp(child.Symbol)) return parent.GetSubtree(1) != child;
+      }
+      return false;
+    }
+
+    private static bool IsFunction(ISymbol symbol) {
+      // functions are formatted in prefix form e.g. sin(...)
+      return !IsOperator(symbol) && !IsLeaf(symbol);
+    }
+
+    private static bool IsLeaf(ISymbol symbol) {
+      return symbol.MaximumArity == 0;
+    }
+
+    private static bool IsOperator(ISymbol symbol) {
+      return IsLeftAssocOp(symbol) || IsRightAssocOp(symbol);
+    }
+
+    private static bool IsAssocOp(ISymbol symbol) {
+      // (a <op> b) <op> c = a <op> (b <op> c)
+      return symbol is Addition ||
+        symbol is Multiplication ||
+        symbol is And ||
+        symbol is Or ||
+        symbol is Xor;
+    }
+
+    private static bool IsLeftAssocOp(ISymbol symbol) {
+      // a <op> b <op> c = (a <op> b) <op> c
+      return symbol is Addition ||
+        symbol is Subtraction ||
+        symbol is Multiplication ||
+        symbol is Division ||
+        symbol is And ||
+        symbol is Or ||
+        symbol is Xor;
+    }
+
+    private static bool IsRightAssocOp(ISymbol symbol) {
+      // a <op> b <op> c = a <op> (b <op> c)
+      // Negation (single-argument subtraction) is also right-assoc, but we do not have a separate symbol for negation.
+      return symbol is Not ||
+             symbol is Power; // x^y^z = x^(y^z) (as in Fortran or Mathematica)
     }
 
@@ -216 +326 @@
       // skip root and start symbols
       StringBuilder strBuilder = new StringBuilder();
-      BaseInfixExpressionFormatter.FormatRecursively(symbolicExpressionTree.Root.GetSubtree(0).GetSubtree(0),
+      var cleanTree = (ISymbolicExpressionTree)symbolicExpressionTree.Clone();
+      BaseInfixExpressionFormatter.ConvertToBinaryLeftAssoc(cleanTree);
+      BaseInfixExpressionFormatter.FormatRecursively(cleanTree.Root.GetSubtree(0).GetSubtree(0),
         strBuilder, numberFormat, formatString);
       return strBuilder.ToString();
@@ -227 +339 @@
 
   [StorableType("54D917E8-134E-4066-9A60-2737C12D81DC")]
-  [Item("Infix String Formater", "Formatter for symbolic expressions, which produces an infix expression " +
+  [Item("Infix String Formatter", "Formatter for symbolic expressions, which produces an infix expression " +
                                  "as well as a list of all coefficient values")]
   public sealed class InfixExpressionStringFormatter : NamedItem, ISymbolicExpressionTreeStringFormatter {
@@ -247 +359 @@
       StringBuilder strBuilder = new StringBuilder();
       var parameters = new List<KeyValuePair<string, double>>();
-      BaseInfixExpressionFormatter.FormatRecursively(symbolicExpressionTree.Root.GetSubtree(0).GetSubtree(0),
+      var cleanTree = (ISymbolicExpressionTree)symbolicExpressionTree.Clone();
+      BaseInfixExpressionFormatter.ConvertToBinaryLeftAssoc(cleanTree);
+      BaseInfixExpressionFormatter.FormatRecursively(cleanTree.Root.GetSubtree(0).GetSubtree(0),
         strBuilder, NumberFormatInfo.InvariantInfo, "G", parameters);
       strBuilder.Append($"{Environment.NewLine}{Environment.NewLine}");