Changeset 12014 for branches/HeuristicLab.Problems.GrammaticalOptimization/HeuristicLab.Common/ExpressionExtender.cs

Timestamp:

02/16/15 09:14:38 (9 years ago)

Author:

gkronber

Message:

#2283: worked on transformation of arithmetic expressions to canonical form

File:

• branches/HeuristicLab.Problems.GrammaticalOptimization/HeuristicLab.Common/ExpressionExtender.cs (modified) (9 diffs)

branches/HeuristicLab.Problems.GrammaticalOptimization/HeuristicLab.Common/ExpressionExtender.cs

@@ -19 +19 @@
     // supports the grammar
     // G(E):
-    //     E -> V | V+E | V-E | V*E | V%E | (E) 
+    //     E -> V | V+E | V-E | V*E | V%E | V/E | (E) 
     //     V -> <variables>
     //     ";
 
-    // transformations: 
-    // - transform c*b*a to a*b*c (lexicographic ordering for factors, cached)
-    // - transfrom - to + (assumed optimized constants for terms)
-
+    // might produce expressions of the form |/x
+    // the pipe symbol | is used for the constant one (in comparison to other constants)
     private string sentence;
     private int syIdx;
 
     public string CanonicalRepresentation(string phrase) {
-      throw new NotImplementedException();
       InitLex(phrase);
       var e = CanonicalExpr();
-      return e.ToString();
+      return e.ToString(); 
     }
 
@@ -97 +94 @@
           NewSy();
           f = CanonicalFact();
-          f.Invert();
-          if (f != null) factors.Add(f);
+          // if there is only one term we can add multiple inverted simple factors instead of the whole inverted expression
+          if (!f.IsSimpleFactor && f.Expr.Terms.Count == 1) {
+            foreach (var invF in f.Expr.Terms.First().Factors) {
+              if (invF.ToString() == "|") continue;
+              invF.Invert();
+              factors.Add(invF);
+            }
+          } else {
+            f.Invert();
+            if (f != null) factors.Add(f);
+          }
         }
         curSy = CurSy();
       }
+
+      factors = CancelFactors(factors).ToList();
       return ExpandFactors(factors);
     }
 
-    /*
-    private List<Factor> CancelFactors(Term t) {
-      var nonInvF = t.Factors.Where(f => !f.IsInverse).ToArray();
-      var invF = t.Factors.Where(f => f.IsInverse).ToArray();
-
-      var result = new List<Factor>();
-      foreach (var f in nonInvF) {
-        if (!invF.Contains(f)) {
-          result.Add(f);
-        }
-      }
-      if (result.Count == 0) result.Add(new Factor('1'));
-      return result;
-    }
-    */
     // canonical fact returns a factor (either a singe variable, or a set of terms)
     private Factor CanonicalFact() {
@@ -144 +137 @@
 
     // a list of factors (symbols, or expressions, and possibly inverses are read
-    // a lis to factors symbols or expressions and possibly inverses are produced
+    // a list to factors symbols or expressions and possibly inverses are produced
     // all non-inverse expression factors are expanded
     private Expr ExpandFactors(IEnumerable<Factor> factors) {
@@ -154 +147 @@
       Expr currentFact = null;
       var firstFactor = factors.First();
-      if (firstFactor.IsSimpleFactor) currentFact = new Expr(new Term(firstFactor));
+      if (firstFactor.IsSimpleFactor || firstFactor.IsInverse) currentFact = new Expr(new Term(firstFactor));
       else currentFact = firstFactor.Expr;
 
@@ -180 +173 @@
       var results = new List<Factor>(factors);
       foreach (var f in factorsArr) {
-        if (f.ToString() == "1") results.Remove(f);
+        if (f.ToString() == "|") results.Remove(f);
+        if (f.ToString() == "|/(|)") results.Remove(f);
         if (f.IsInverse) {
           // find matching
           Factor match;
-          if (f.IsSimpleFactor) match = factorsArr.FirstOrDefault(other => !other.IsInverse && f.Symbol.Equals(other.Symbol));
-          else match = factorsArr.FirstOrDefault(other => !other.IsInverse && f.Expr.Equals(other.Expr));
+          match = factorsArr.FirstOrDefault(other => !other.IsInverse && f.Cancels(other));
           if (match != null) {
+            results.Remove(f);
+            var idx = results.IndexOf(match);
+
             results.Remove(match);
-            results.Remove(f);
+            if (!results.Any())
+              results.Insert(idx, new Factor('|')); // when the factor is the last one then insert a one
+
+            // also mark as cancelled in the factorsArr
+            idx = Array.IndexOf(factorsArr, match);
+            factorsArr[idx] = new Factor('|');
           }
         }
       }
-      if (results.Count == 0) results.Add(new Factor('1'));
+      // remove all unnecessary "1* factors"
+
+      if (results.Count == 0) results.Add(new Factor('|'));
       return results;
     }
@@ -273 +276 @@
         this.inv = !inv;
       }
+      public bool Cancels(Factor other) {
+        if (this.inv == other.inv) return false;
+        if (this.Expr != null && other.Expr == null) return false;
+        if (this.Expr == null && other.Expr != null) return false;
+        if (Expr == null) return this.Symbol.Equals(other.symbol);
+        else return this.Expr.CompareTo(other.Expr) == 0;
+      }
 
       public int CompareTo(Factor other) {
@@ -294 +304 @@
         var s = Expr == null ? symbol.ToString() : "(" + expr.ToString() + ")";
         if (IsInverse) {
-          return "1/" + s;
+          return "|/" + s;
         } else return s;
       }
@@ -356 +366 @@
         var other = obj as Expr;
         if (other == null) return false;
-        //if (this.Inverse != other.Inverse) return false;
         if (this.Terms.Count() != other.Terms.Count()) return false;
         return this.Terms.Intersect(other.Terms).Count() == this.Terms.Count;
       }
+
       public override int GetHashCode() {
         var h = 31415;
@@ -388 +398 @@
       return ContainsNonTerminal(term.Factors);
     }
-
-
-    /*
-
-    internal class FactorComparer : IComparer<char> {
-      public int Compare(char x, char y) {
-        if (IsNonTerminal(x) && !IsNonTerminal(y)) {
-          return 1;
-        } else if (!IsNonTerminal(x) && IsNonTerminal(y)) {
-          return -1;
-        } else if (IsNonTerminal(x) && IsNonTerminal(y)) {
-          return x.CompareTo(y);
-        } else {
-          return x.CompareTo(y);
-        }
-      }
-    }*/
   }
 }