Free cookie consent management tool by TermsFeed Policy Generator

Changeset 11966 for branches


Ignore:
Timestamp:
02/06/15 19:45:12 (10 years ago)
Author:
gkronber
Message:

worked on expression expander for const opt

Location:
branches/HeuristicLab.Problems.GrammaticalOptimization
Files:
3 edited

Legend:

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

    r11902 r11966  
    11using System;
     2using System.CodeDom;
    23using System.Collections.Generic;
    34using System.Diagnostics;
    45using System.Linq;
     6using System.Security.Cryptography.X509Certificates;
    57using System.Text;
    68using System.Threading.Tasks;
     
    2426    // - transfrom - to + (assumed optimized constants for terms)
    2527
    26 
    27     // most-recently-used caching (with limited capacity) for canonical representations
    28     MostRecentlyUsedCache<string, string> canonicalPhraseCache = new MostRecentlyUsedCache<string, string>(100000);
     28    private string sentence;
     29    private int syIdx;
     30
    2931    public string CanonicalRepresentation(string phrase) {
    30       int pos = 0;
    31       return CanonicalExpr(phrase, ref pos);
    32     }
    33 
    34     private Expr CanonicalExpr(string phrase, ref int pos) {
    35       var terms = new List<Term>();
    36       terms.Add(CanonicalTerm(phrase, ref pos));
    37       var curSy = phrase[pos];
     32      InitLex(phrase);
     33      var e = CanonicalExpr();
     34      return e.ToString();
     35    }
     36
     37
     38    private void InitLex(string sentence) {
     39      this.sentence = sentence;
     40      this.syIdx = 0;
     41    }
     42
     43    private char CurSy() {
     44      if (syIdx >= sentence.Length) return '\0';
     45      return sentence[syIdx];
     46    }
     47    private void NewSy() {
     48      if (syIdx < sentence.Length) syIdx++;
     49    }
     50
     51    // an expression is a list of terms
     52    // a term is an (ordered) list of factors
     53    // a factor is a symbol or an inverted expression
     54    // CanonicalExpression reads multiple terms (expressions) and must merge the terms in the expression (ordering and duplicates)
     55    // CanonicalTerm reads multiple factors and must expand factors whenever it reads a combined factor (expression) it produces an expression
     56    // CanonicalFactor produces an expression
     57
     58
     59    // canonical expression returns either a single term or a set of terms
     60    private Expr CanonicalExpr() {
     61      var terms = new List<Expr>();
     62      terms.Add(CanonicalTerm());
     63      var curSy = CurSy();
    3864      while (curSy == '+' || curSy == '-' || curSy == '^') {
    3965        if (curSy == '+') {
    40           pos++;
    41           terms.Add(CanonicalTerm(phrase, ref pos));
     66          NewSy();
     67          terms.Add(CanonicalTerm());
    4268        } else if (curSy == '-') {
    43           pos++;
    44           terms.Add(CanonicalTerm(phrase, ref pos)); // minus is the same as plus assuming constant opt
     69          NewSy();
     70          terms.Add(CanonicalTerm()); // minus is the same as plus assuming constant opt
    4571        } else {
    46           pos++;
     72          NewSy();
    4773          throw new NotImplementedException();
    4874          // var e = Expr(variables, constants);
    4975          // r = Not(r) * e + r * Not(e); // xor = (!x AND y) OR (x AND !y)
    5076        }
    51         curSy = phrase[pos];
    52       }
    53 
    54       // at this point we might have multiple constants in the list of terms but we only need one of them
    55       var firstConstant = terms.OfType<Variable>().FirstOrDefault(); // if a term is only a variable then it must be a constant (otherwise (for real variables) it would be a product of two constants)
    56       if (firstConstant == null) {
    57         // no constant found => add a constant offset for each full expression
    58         var offset = new Variable();
    59         constants.Add(offset);
    60         terms.Add(offset);
    61       } else {
    62         // there is already a constant => remove all others if there are more
    63         var otherConsts = terms.OfType<Variable>().Where(t => t != firstConstant).ToArray();
    64         foreach (var otherConst in otherConsts) {
    65           terms.Remove(otherConst);
    66           constants.Remove(otherConst);
    67         }
    68       }
    69       return TermBuilder.Sum(terms);
    70     }
    71 
    72     private Term CanonicalTerm(string phrase, ref int pos) {
    73       var factors = new List<Factor>();
    74       var invFactors = new List<Factor>();
    75       var f = CanonicalFact(phrase, ref pos);
     77        curSy = CurSy();
     78      }
     79
     80      return new Expr(terms.SelectMany(t => t.Terms));
     81    }
     82
     83    // canonical term returns either a single term (product of factors) or a set of terms
     84    private Expr CanonicalTerm() {
     85      var factors = new List<Expr>();
     86      var invFactors = new List<Expr>();
     87      var f = CanonicalFact();
    7688      if (f != null) factors.Add(f);
    77       var curSy = phrase[pos];
     89      var curSy = CurSy();
    7890      while (curSy == '*' || curSy == '%') {
    7991        if (curSy == '*') {
    80           pos++;
    81           f = CanonicalFact(phrase, ref pos); // fact might return string.Empty (for constants)
     92          NewSy();
     93          f = CanonicalFact();
    8294          if (f != null) factors.Add(f);
    8395        } else {
    84           pos++;
    85           f = CanonicalFact(phrase, ref pos);
     96          NewSy();
     97          f = CanonicalFact();
     98          f.Invert();
    8699          if (f != null) invFactors.Add(f);
    87100        }
    88         curSy = phrase[pos];
    89       }
    90 
    91       // cancel factors if they are contained in factors and invFactors
    92       foreach (var cancelledF in factors.Intersect(invFactors).ToArray()) {
    93         factors.Remove(cancelledF);
    94         invFactors.Remove(cancelledF);
    95       }
    96       // at this point factors and invFactors might be empty
    97       if (factors.Count == 0 && invFactors.Count == 0) throw new NotImplementedException();
    98 
    99       if(factors.Count == 1)
    100       // extend factors if they are composed of terms
    101       // this means that we return a list of terms instead of one single term
    102       // at this point factors can only be a list of additive terms
    103       var extendedFactors = new List<Factor>();
    104 
    105       // order factors (bysize then lexicographically)
    106     }
    107 
    108     private Factor CanonicalFact(string phrase, ref int pos) {
    109       var curSy = phrase[pos];
     101        curSy = CurSy();
     102      }
     103
     104      // cancellation
     105      foreach (var invF in invFactors.ToArray()) {
     106        invF.Invert();
     107        if (factors.Contains(invF)) {
     108          invFactors.Remove(invF);
     109          factors.Remove(invF);
     110          if (factors.Count == 0) factors.Add(new Expr(new Term('1')));
     111        } else invF.Invert();
     112      }
     113
     114      return ExpandFactors(factors, invFactors);
     115    }
     116
     117    private Expr ExpandFactors(List<Expr> factors, List<Expr> invFactors) {
     118      // if (invFactors.Count > 0) throw new NotImplementedException();
     119      Expr currentFact = factors.First(); // new Expr(simpleFactor));
     120      Debug.Assert(!currentFact.Inverse); // the first factor is never an inverted factor
     121      foreach (var fact in factors.Skip(1)) {
     122        currentFact = AllProducts(currentFact, fact);
     123      }
     124      foreach (var invF in invFactors) {
     125        currentFact = AllInvProducts(currentFact, invF);
     126      }
     127      return currentFact;
     128    }
     129
     130    private Expr AllProducts(Expr a, Expr b) {
     131      var aTerms = a.Terms.ToArray();
     132      var bTerms = b.Terms.ToArray();
     133      var combs = from aT in aTerms
     134                  from bT in bTerms
     135                  select new Term(aT.Symbols.Concat(bT.Symbols), aT.InvExpressions.Concat(bT.InvExpressions));
     136      return new Expr(combs);
     137    }
     138
     139    private Expr AllInvProducts(Expr a, Expr b) {
     140      var aTerms = a.Terms.ToArray();
     141      var combs = from aT in aTerms
     142                  select new Term(aT.Symbols, aT.InvExpressions.Concat(new Expr[] { b }));
     143      return new Expr(combs);
     144    }
     145
     146    // canonical fact returns a factor (either a singe variable, or a set of terms)
     147    private Expr CanonicalFact() {
     148      var curSy = CurSy();
    110149      if (curSy == '!') {
    111150        throw new NotSupportedException();
    112151      } else if (curSy == '(') {
    113         pos++;
    114         Expr r = CanonicalExpr(phrase, ref pos);
    115         if (phrase[pos] != ')') throw new ArgumentException();
    116         pos++;
    117         if (r.Kind == ExprKind.SimpleExpr)
    118           return new Factor(r.Term);
    119         else
    120           return new Factor(r.Terms); // a composite factor
     152        NewSy();
     153        Expr r = CanonicalExpr();
     154        if (CurSy() != ')') throw new ArgumentException();
     155        NewSy();
     156        return r;
    121157      } else if (curSy >= 'a' && curSy <= 'z') {
    122         pos++;
    123         return new Factor(curSy.ToString());
     158        NewSy();
     159        return new Expr(new Term(curSy));
    124160        //       } else if (curSy >= '0' && curSy <= '9') {
     161      } else if (curSy >= 'A' && curSy <= 'Z') {
     162        // treat nonterminals in the same way as variables
     163        NewSy();
     164        return new Expr(new Term(curSy));
     165
    125166      } else throw new ArgumentException("found symbol " + curSy);
    126167    }
    127168
    128     #region factor
    129     private enum FactorKind { SimpleFactor, Expr }
    130     private class Factor {
    131       public readonly FactorKind Kind;
    132       public readonly string Value; // only set for Kind == SimpleFactor
    133       public readonly IEnumerable<string> Values; // only set for Kind == Expr
    134 
    135       public Factor(string f) {
    136         this.Kind = FactorKind.SimpleFactor;
    137         this.Value = f;
    138       }
    139       public Factor(IEnumerable<string> factorTerms) {
    140         this.Kind = FactorKind.Expr;
    141         this.Values = factorTerms;
     169    #region term
     170    // term can be merged (essentially an ordered list of factors)
     171    internal class Term : IComparable<Term> {
     172      private readonly SortedList<char, int> factorSymbs; // factor symbol and the number of occurrences
     173      private readonly SortedList<Expr, int> invExpressions;
     174
     175      public IEnumerable<char> Symbols {
     176        get {
     177          return factorSymbs.SelectMany(p => Enumerable.Repeat(p.Key, p.Value));
     178        }
     179      }
     180
     181      public IEnumerable<Expr> InvExpressions {
     182        get {
     183          if (invExpressions == null) return Enumerable.Empty<Expr>();
     184          return invExpressions.Where(p => p.Value > 0).SelectMany(p => Enumerable.Repeat(p.Key, p.Value));
     185        }
     186      }
     187
     188      public Term(char f) {
     189        factorSymbs = new SortedList<char, int>(new FactorComparer());
     190        factorSymbs.Add(f, 1);
     191      }
     192      public Term(IEnumerable<char> factors, IEnumerable<Expr> invFactors) {
     193        factorSymbs = new SortedList<char, int>(new FactorComparer());
     194        invExpressions = new SortedList<Expr, int>();
     195        foreach (var f in factors) {
     196          if (factorSymbs.ContainsKey(f)) factorSymbs[f] += 1;
     197          else factorSymbs.Add(f, 1);
     198        }
     199
     200        foreach (var invF in invFactors) {
     201          if (invF.Terms.Count == 1) {
     202            var t = invF.Terms.First();
     203            foreach (var f in factors.Concat(new char[] { '1' })) {
     204              if (t.factorSymbs.ContainsKey(f)) {
     205                t.factorSymbs[f] -= 1;
     206                if (t.factorSymbs[f] == 0) t.factorSymbs.Remove(f);
     207              }
     208            }
     209          }
     210          if (invExpressions.ContainsKey(invF)) invExpressions[invF] += 1;
     211          else invExpressions.Add(invF, 1);
     212        }
     213      }
     214
     215      public int CompareTo(Term other) {
     216        if (ContainsNonTerminal(Symbols) && !ContainsNonTerminal(other.Symbols)) {
     217          return 1;
     218        } else if (!ContainsNonTerminal(Symbols) && ContainsNonTerminal(other.Symbols)) {
     219          return -1;
     220        } else {
     221          var countComp = Symbols.Count().CompareTo(other.Symbols.Count());
     222          if (countComp != 0) return countComp;
     223          return string.Join("", Symbols).CompareTo(string.Join("", other.Symbols));
     224        }
    142225      }
    143226
    144227      public override string ToString() {
    145         if (Kind == FactorKind.SimpleFactor) return Value;
    146         else return string.Join("+", Values);
    147       }
    148       public override bool Equals(object obj) {
    149         var other = obj as Factor;
    150         if (other == null) return false;
    151         if (other.Kind != this.Kind) return false;
    152         if (Kind == FactorKind.SimpleFactor) return this.Value == other.Value;
    153         if (this.Values.Count() != other.Values.Count()) return false;
    154         if (this.Values.Zip(other.Values, Tuple.Create).All(t => t.Item1 == t.Item2)) return true;
    155         return false;
    156       }
    157       public override int GetHashCode() {
    158         var h = 31415;
    159         if (Value != null) h ^= Value.GetHashCode();
    160         foreach (var v in Values) {
    161           h ^= v.GetHashCode();
    162         }
    163         return h;
    164       }
    165     }
    166     #endregion
    167     #region term
    168     private enum TermKind { SimpleTerm, Term }
    169     private class Term {
    170       public readonly TermKind Kind;
    171       public readonly Factor Factor; // only set for Kind == Simple
    172       public readonly IEnumerable<Factor> Factors;
    173 
    174       public Term(Factor f) {
    175         this.Kind = TermKind.SimpleTerm;
    176         this.Factor = f;
    177       }
    178       public Term(IEnumerable<Factor> factors) {
    179         this.Kind = TermKind.Term;
    180         this.Factors = factors;
    181       }
    182 
    183       public override string ToString() {
    184         if (Kind == TermKind.SimpleTerm) return Factor.ToString();
    185         else return string.Join("+", Factors);
     228        if (InvExpressions.Any())
     229          return string.Join("*", Symbols) + "%" + string.Join("%", InvExpressions);
     230        else {
     231          return string.Join("*", Symbols);
     232        }
    186233      }
    187234      public override bool Equals(object obj) {
    188235        var other = obj as Term;
    189236        if (other == null) return false;
    190         if (other.Kind != this.Kind) return false;
    191         if (Kind == TermKind.SimpleTerm) return this.Factor == other.Factor;
    192         if (this.Factors.Count() != other.Factors.Count()) return false;
    193         if (this.Factors.Zip(other.Factors, Tuple.Create).All(t => t.Item1 == t.Item2)) return true;
    194         return false;
     237        if (this.Symbols.Count() != other.Symbols.Count()) return false;
     238        if (this.InvExpressions.Count() != other.InvExpressions.Count()) return false;
     239        if (this.Symbols.Zip(other.Symbols, Tuple.Create).Any(t => t.Item1 != t.Item2)) return false;
     240        if (this.InvExpressions.Zip(other.InvExpressions, Tuple.Create).Any(t => t.Item1 != t.Item2)) return false;
     241        return true;
    195242      }
    196243      public override int GetHashCode() {
    197244        var h = 31415;
    198         if (Factor != null) h ^= Factor.GetHashCode();
    199         foreach (var t in Factors) {
    200           h ^= t.GetHashCode();
     245        foreach (var v in Symbols) {
     246          h ^= v.GetHashCode();
     247        }
     248        foreach (var v in InvExpressions) {
     249          h ^= v.GetHashCode();
    201250        }
    202251        return h;
     
    204253    }
    205254    #endregion
     255
    206256    #region expr
    207     private enum ExprKind { SimpleExpr, Expr }
    208     private class Expr {
    209       public readonly ExprKind Kind;
    210       public readonly string Term; // only set for Kind == SimpleExpr
    211       public readonly IEnumerable<string> Terms; // only set for Kind == Expr
    212 
    213       public Expr(string f) {
    214         this.Kind = ExprKind.SimpleExpr;
    215         this.Term = f;
    216       }
    217       public Expr(IEnumerable<string> exprTerms) {
    218         this.Kind = ExprKind.Expr;
    219         this.Terms = exprTerms;
     257
     258    internal class Expr : IComparable<Expr> {
     259      public readonly SortedSet<Term> Terms; // only set for Kind == Expr
     260      public bool Inverse;
     261      public Expr(Term t) {
     262        Terms = new SortedSet<Term>();
     263        Terms.Add(t);
     264      }
     265      public Expr(IEnumerable<Term> exprTerms) {
     266        Terms = new SortedSet<Term>();
     267        foreach (var t in exprTerms) {
     268          Terms.Add(t);
     269        }
     270      }
     271
     272      public void Merge(Expr other) {
     273        this.Terms.UnionWith(other.Terms);
     274      }
     275
     276      public int CompareTo(Expr other) {
     277        var sizeComp = this.Terms.Count.CompareTo(other.Terms.Count);
     278        if (sizeComp != 0) return sizeComp;
     279        // same size => compare terms
     280        foreach (var pair in Terms.Zip(other.Terms, Tuple.Create)) {
     281          var termComp = pair.Item1.CompareTo(pair.Item2);
     282          if (termComp != 0) return termComp;
     283        }
     284        return 0;
    220285      }
    221286
    222287      public override string ToString() {
    223         if (Kind == ExprKind.SimpleExpr) return Term;
    224         else return string.Join("+", Terms);
     288        if (Inverse && Terms.Count > 1)
     289          return "(" + string.Join("+", Terms) + ")";
     290        else if (Inverse && Terms.Count == 1) {
     291          return Terms.First().ToString().Replace("%", "#").Replace("*", "%").Replace("#", "*");
     292        } else
     293          return string.Join("+", Terms);
    225294      }
    226295      public override bool Equals(object obj) {
    227296        var other = obj as Expr;
    228297        if (other == null) return false;
    229         if (other.Kind != this.Kind) return false;
    230         if (Kind == ExprKind.SimpleExpr) return this.Term == other.Term;
     298        if (this.Inverse != other.Inverse) return false;
    231299        if (this.Terms.Count() != other.Terms.Count()) return false;
    232         if (this.Terms.Zip(other.Terms, Tuple.Create).All(t => t.Item1 == t.Item2)) return true;
    233         return false;
     300        return this.Terms.Intersect(other.Terms).Count() == this.Terms.Count;
    234301      }
    235302      public override int GetHashCode() {
    236303        var h = 31415;
    237         if (Term != null) h ^= Term.GetHashCode();
    238         foreach (var t in Terms) {
    239           h ^= t.GetHashCode();
    240         }
     304        if (Terms != null)
     305          foreach (var t in Terms) {
     306            h ^= t.GetHashCode();
     307          }
    241308        return h;
    242309      }
     310
     311      public void Invert() {
     312        this.Inverse = !Inverse;
     313      }
    243314    }
    244315    #endregion
    245     // private enum TermKind { }
    246     // private class Term {
    247     //   public TermKind Kind;
    248     //   public string FirstFactor; // always set
    249     //   public IEnumerable<string> RemainingFactors; // only set for Kind == Expr
    250     // }
    251 
    252     // cache the canonical form of terms for performance reasons
    253     private Dictionary<string, string> canonicalTermDictionary = new Dictionary<string, string>();
    254     private string CanonicalTerm(string term) {
    255       string canonicalTerm;
    256       if (!canonicalTermDictionary.TryGetValue(term, out canonicalTerm)) {
    257         // add
    258         var chars = term.ToCharArray();
    259         Array.Sort(chars);
    260         var sb = new StringBuilder(chars.Length);
    261         // we want to have the up-case characters last
    262         for (int i = chars.Length - 1; i > 0; i--) {
    263           if (chars[i] != '*') {
    264             sb.Append(chars[i]);
    265             if (chars[i - 1] != '*') sb.Append('*');
    266           }
    267         }
    268         if (chars[0] != '*') sb.Append(chars[0]); // last term
    269         canonicalTerm = sb.ToString();
    270         canonicalTermDictionary.Add(term, canonicalTerm);
    271       }
    272       return canonicalTerm;
     316    internal static bool IsNonTerminal(char symb) {
     317      return symb >= 'A' && symb <= 'Z';
     318    }
     319    internal static bool ContainsNonTerminal(IEnumerable<char> symbs) {
     320      return symbs.Any(IsNonTerminal);
     321    }
     322
     323    internal class FactorComparer : IComparer<char> {
     324      public int Compare(char x, char y) {
     325        if (IsNonTerminal(x) && !IsNonTerminal(y)) {
     326          return 1;
     327        } else if (!IsNonTerminal(x) && IsNonTerminal(y)) {
     328          return -1;
     329        } else if (IsNonTerminal(x) && IsNonTerminal(y)) {
     330          return x.CompareTo(y);
     331        } else {
     332          return x.CompareTo(y);
     333        }
     334      }
    273335    }
    274336  }
  • branches/HeuristicLab.Problems.GrammaticalOptimization/Main/Program.cs

    r11895 r11966  
    2727
    2828      //RunDemo();
    29       RunGpDemo();
    30       // RunGridTest();
     29      // RunGpDemo();
     30      RunGridTest();
    3131      //RunGpGridTest();
    3232    }
    3333
    3434    private static void RunGridTest() {
    35       int maxIterations = 70000; // for poly-10 with 50000 evaluations no successful try with hl yet
     35      int maxIterations = 200000; // for poly-10 with 50000 evaluations no successful try with hl yet
    3636      //var globalRandom = new Random(31415);
    3737      var localRandSeed = 31415;
    38       var reps = 30;
     38      var reps = 20;
    3939
    4040      var policyFactories = new Func<IBanditPolicy>[]
     
    112112      var instanceFactories = new Func<Random, Tuple<IProblem, int>>[]
    113113      {
    114         //(rand) => Tuple.Create((IProblem)new SantaFeAntProblem(), 17),
     114        (rand) => Tuple.Create((IProblem)new SantaFeAntProblem(), 17),
    115115        //(rand) => Tuple.Create((IProblem)new FindPhrasesProblem(rand, 10, numPhrases:5, phraseLen:3, numOptimalPhrases:5, numDecoyPhrases:0, correctReward:1, decoyReward:0, phrasesAsSets:false ), 15),
    116116        //(rand) => Tuple.Create((IProblem)new FindPhrasesProblem(rand, 10, numPhrases:5, phraseLen:3, numOptimalPhrases:5, numDecoyPhrases:0, correctReward:1, decoyReward:0, phrasesAsSets:true ), 15),
     
    121121
    122122      foreach (var instanceFactory in instanceFactories) {
    123         foreach (var useCanonical in new bool[] { true /*, false */}) {
    124           foreach (var randomTries in new int[] { 0 /*, 1, 10 /*, /* 5, 100 /*, 500, 1000 */}) {
     123        foreach (var useCanonical in new bool[] { true, false }) {
     124          foreach (var randomTries in new int[] { 0, 1, 10 /*, /* 5, 100 /*, 500, 1000 */}) {
    125125            foreach (var policyFactory in policyFactories) {
    126126              var myRandomTries = randomTries;
     
    146146                var problem = instance.Item1;
    147147                var maxLen = instance.Item2;
    148                 //var alg = new SequentialSearch(problem, maxLen, myLocalRand, myRandomTries,
    149                 //  new GenericGrammarPolicy(problem, policyFactory(), useCanonical));
    150                 var alg = new SequentialSearch(problem, maxLen, myLocalRand,
    151                   myRandomTries,
    152                   new GenericFunctionApproximationGrammarPolicy(problem,
    153                     useCanonical));
     148                var alg = new SequentialSearch(problem, maxLen, myLocalRand, myRandomTries,
     149                  new GenericGrammarPolicy(problem, policyFactory(), useCanonical));
     150                // var alg = new SequentialSearch(problem, maxLen, myLocalRand,
     151                //   myRandomTries,
     152                //   new GenericFunctionApproximationGrammarPolicy(problem,
     153                //     useCanonical));
    154154                //var alg = new ExhaustiveBreadthFirstSearch(problem, 25);
    155155                //var alg = new AlternativesContextSampler(problem, 25);
  • branches/HeuristicLab.Problems.GrammaticalOptimization/Test/TestCanonicalExpressions.cs

    r11902 r11966  
    6262
    6363      // when using constant opt the negative sign is not necessary because a negative factor can be produced
    64       Assert.AreEqual("a*b+c*b", extender.CanonicalRepresentation("b*(c-a)"));
     64      Assert.AreEqual("a*b+b*c", extender.CanonicalRepresentation("b*(c-a)"));
    6565      Assert.AreEqual("a*b+a*d+b*c+c*d", extender.CanonicalRepresentation("(b-d)*(c-a)"));
    6666    }
     
    7474
    7575      Assert.AreEqual("a*b%(a+b)%(c+d)", extender.CanonicalRepresentation("(b*a)%(d-c)%(a+b)"));
    76       Assert.AreEqual("a*b%(c+d)%(a%e+b%e)", extender.CanonicalRepresentation("((b*a)%(d-c))%((a+b)%e)"));
     76      Assert.AreEqual("a*b%(a%e+b%e)%(c+d)", extender.CanonicalRepresentation("((b*a)%(d-c))%((a+b)%e)"));
    7777      // a*b*e%(c+d)%(a+b)
    7878    }
     
    8080    public void TestDivisionCancellation() {
    8181      var extender = new ExpressionExtender();
    82       Assert.AreEqual("a", extender.CanonicalRepresentation("a%a"));
    83       Assert.AreEqual("a*a", extender.CanonicalRepresentation("a*a%a"));
    84       Assert.AreEqual("1%a", extender.CanonicalRepresentation("(a%a)%a"));
     82      Assert.AreEqual("1", extender.CanonicalRepresentation("a%a"));
     83      Assert.AreEqual("a", extender.CanonicalRepresentation("a*a%a"));
     84      Assert.AreEqual("1%a", extender.CanonicalRepresentation("(a%a)%a")); 
    8585      Assert.AreEqual("1%a", extender.CanonicalRepresentation("a%a%a"));
    8686      Assert.AreEqual("a", extender.CanonicalRepresentation("a%(a%a)"));
     87      Assert.AreEqual("1", extender.CanonicalRepresentation("(a+b)%(b+a)"));
     88      Assert.AreEqual("1%a+1%b", extender.CanonicalRepresentation("(a+b)%(a*b)"));
    8789    }
    8890  }
Note: See TracChangeset for help on using the changeset viewer.