Free cookie consent management tool by TermsFeed Policy Generator

Ignore:
Timestamp:
02/16/15 09:14:38 (10 years ago)
Author:
gkronber
Message:

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

File:
1 edited

Legend:

Unmodified
Added
Removed
  • branches/HeuristicLab.Problems.GrammaticalOptimization/HeuristicLab.Common/ExpressionExtender.cs

    r11981 r12014  
    1919    // supports the grammar
    2020    // G(E):
    21     //     E -> V | V+E | V-E | V*E | V%E | (E)
     21    //     E -> V | V+E | V-E | V*E | V%E | V/E | (E)
    2222    //     V -> <variables>
    2323    //     ";
    2424
    25     // transformations:
    26     // - transform c*b*a to a*b*c (lexicographic ordering for factors, cached)
    27     // - transfrom - to + (assumed optimized constants for terms)
    28 
     25    // might produce expressions of the form |/x
     26    // the pipe symbol | is used for the constant one (in comparison to other constants)
    2927    private string sentence;
    3028    private int syIdx;
    3129
    3230    public string CanonicalRepresentation(string phrase) {
    33       throw new NotImplementedException();
    3431      InitLex(phrase);
    3532      var e = CanonicalExpr();
    36       return e.ToString();
     33      return e.ToString(); 
    3734    }
    3835
     
    9794          NewSy();
    9895          f = CanonicalFact();
    99           f.Invert();
    100           if (f != null) factors.Add(f);
     96          // if there is only one term we can add multiple inverted simple factors instead of the whole inverted expression
     97          if (!f.IsSimpleFactor && f.Expr.Terms.Count == 1) {
     98            foreach (var invF in f.Expr.Terms.First().Factors) {
     99              if (invF.ToString() == "|") continue;
     100              invF.Invert();
     101              factors.Add(invF);
     102            }
     103          } else {
     104            f.Invert();
     105            if (f != null) factors.Add(f);
     106          }
    101107        }
    102108        curSy = CurSy();
    103109      }
     110
     111      factors = CancelFactors(factors).ToList();
    104112      return ExpandFactors(factors);
    105113    }
    106114
    107     /*
    108     private List<Factor> CancelFactors(Term t) {
    109       var nonInvF = t.Factors.Where(f => !f.IsInverse).ToArray();
    110       var invF = t.Factors.Where(f => f.IsInverse).ToArray();
    111 
    112       var result = new List<Factor>();
    113       foreach (var f in nonInvF) {
    114         if (!invF.Contains(f)) {
    115           result.Add(f);
    116         }
    117       }
    118       if (result.Count == 0) result.Add(new Factor('1'));
    119       return result;
    120     }
    121     */
    122115    // canonical fact returns a factor (either a singe variable, or a set of terms)
    123116    private Factor CanonicalFact() {
     
    144137
    145138    // a list of factors (symbols, or expressions, and possibly inverses are read
    146     // a lis to factors symbols or expressions and possibly inverses are produced
     139    // a list to factors symbols or expressions and possibly inverses are produced
    147140    // all non-inverse expression factors are expanded
    148141    private Expr ExpandFactors(IEnumerable<Factor> factors) {
     
    154147      Expr currentFact = null;
    155148      var firstFactor = factors.First();
    156       if (firstFactor.IsSimpleFactor) currentFact = new Expr(new Term(firstFactor));
     149      if (firstFactor.IsSimpleFactor || firstFactor.IsInverse) currentFact = new Expr(new Term(firstFactor));
    157150      else currentFact = firstFactor.Expr;
    158151
     
    180173      var results = new List<Factor>(factors);
    181174      foreach (var f in factorsArr) {
    182         if (f.ToString() == "1") results.Remove(f);
     175        if (f.ToString() == "|") results.Remove(f);
     176        if (f.ToString() == "|/(|)") results.Remove(f);
    183177        if (f.IsInverse) {
    184178          // find matching
    185179          Factor match;
    186           if (f.IsSimpleFactor) match = factorsArr.FirstOrDefault(other => !other.IsInverse && f.Symbol.Equals(other.Symbol));
    187           else match = factorsArr.FirstOrDefault(other => !other.IsInverse && f.Expr.Equals(other.Expr));
     180          match = factorsArr.FirstOrDefault(other => !other.IsInverse && f.Cancels(other));
    188181          if (match != null) {
     182            results.Remove(f);
     183            var idx = results.IndexOf(match);
     184
    189185            results.Remove(match);
    190             results.Remove(f);
     186            if (!results.Any())
     187              results.Insert(idx, new Factor('|')); // when the factor is the last one then insert a one
     188
     189            // also mark as cancelled in the factorsArr
     190            idx = Array.IndexOf(factorsArr, match);
     191            factorsArr[idx] = new Factor('|');
    191192          }
    192193        }
    193194      }
    194       if (results.Count == 0) results.Add(new Factor('1'));
     195      // remove all unnecessary "1* factors"
     196
     197      if (results.Count == 0) results.Add(new Factor('|'));
    195198      return results;
    196199    }
     
    273276        this.inv = !inv;
    274277      }
     278      public bool Cancels(Factor other) {
     279        if (this.inv == other.inv) return false;
     280        if (this.Expr != null && other.Expr == null) return false;
     281        if (this.Expr == null && other.Expr != null) return false;
     282        if (Expr == null) return this.Symbol.Equals(other.symbol);
     283        else return this.Expr.CompareTo(other.Expr) == 0;
     284      }
    275285
    276286      public int CompareTo(Factor other) {
     
    294304        var s = Expr == null ? symbol.ToString() : "(" + expr.ToString() + ")";
    295305        if (IsInverse) {
    296           return "1/" + s;
     306          return "|/" + s;
    297307        } else return s;
    298308      }
     
    356366        var other = obj as Expr;
    357367        if (other == null) return false;
    358         //if (this.Inverse != other.Inverse) return false;
    359368        if (this.Terms.Count() != other.Terms.Count()) return false;
    360369        return this.Terms.Intersect(other.Terms).Count() == this.Terms.Count;
    361370      }
     371
    362372      public override int GetHashCode() {
    363373        var h = 31415;
     
    388398      return ContainsNonTerminal(term.Factors);
    389399    }
    390 
    391 
    392     /*
    393 
    394     internal class FactorComparer : IComparer<char> {
    395       public int Compare(char x, char y) {
    396         if (IsNonTerminal(x) && !IsNonTerminal(y)) {
    397           return 1;
    398         } else if (!IsNonTerminal(x) && IsNonTerminal(y)) {
    399           return -1;
    400         } else if (IsNonTerminal(x) && IsNonTerminal(y)) {
    401           return x.CompareTo(y);
    402         } else {
    403           return x.CompareTo(y);
    404         }
    405       }
    406     }*/
    407400  }
    408401}
Note: See TracChangeset for help on using the changeset viewer.