using System; using System.Collections.Generic; using System.Diagnostics.Eventing.Reader; using System.Linq; using System.Runtime.Remoting.Messaging; using System.Text; using System.Threading.Tasks; using HeuristicLab.Common; namespace HeuristicLab.Problems.GrammaticalOptimization { public class ExpressionInterpreter { private string sentence; private int syIdx; // interprets sentences from L(G(Expr)): // Expr -> Term { ('+' | '-' | '^' ) Term } // Term -> Fact { ('*' | '/') Fact } // Fact -> '!' Expr | '(' Expr ')' | Var // Var -> 'a'..'z' // for boolean problems the symbol * representes the AND operator, the symbol + represents the OR operator, ! = NOT, ^ = XOR public bool Interpret(string sentence, bool[] vars) { InitLex(sentence); var d = new double[vars.Length]; for (int i = 0; i < vars.Length; i++) d[i] = vars[i] ? 1.0 : 0.0; return !(Expr(d).IsAlmost(0)); } public double Interpret(string sentence, double[] vars) { InitLex(sentence); return Expr(vars); } private void InitLex(string sentence) { this.sentence = sentence; this.syIdx = 0; } private char CurSy() { if (syIdx >= sentence.Length) return '\0'; return sentence[syIdx]; } private void NewSy() { if (syIdx < sentence.Length) syIdx++; } // helper for xor private double Not(double x) { return x.IsAlmost(0) ? 1.0 : 0.0; } private double Expr(double[] d) { var r = 0.0; r = Term(d); var curSy = CurSy(); while (curSy == '+' || curSy == '-' || curSy == '^') { if (curSy == '+') { NewSy(); r += Expr(d); } else if (curSy == '-') { NewSy(); r -= Expr(d); } else { NewSy(); var e = Expr(d); r = Not(r) * e + r * Not(e); // xor = (!x AND y) OR (x AND !y) } curSy = CurSy(); } return r; } private double Term(double[] d) { var r = 0.0; r = Fact(d); var curSy = CurSy(); while (curSy == '*' || curSy == '/') { if (curSy == '*') { NewSy(); r *= Term(d); } else { NewSy(); r /= Term(d); } curSy = CurSy(); } return r; } private double Fact(double[] d) { double r = 0.0; var curSy = CurSy(); if (curSy == '!') { NewSy(); r = Not(Expr(d)); } else if (curSy == '(') { NewSy(); r = Expr(d); if (CurSy() != ')') throw new ArgumentException(); NewSy(); } else /* if (curSy >= 'a' && curSy <= 'z') */ { int o = (byte)curSy - (byte)'a'; //int o = Convert.ToByte(CurSy()) - Convert.ToByte('a'); if (o < 0 || o >= d.Length) throw new ArgumentException(); r = d[o]; NewSy(); } //} else throw new ArgumentException(); return r; } } }