source: branches/HeuristicLab.Problems.GrammaticalOptimization/HeuristicLab.Problems.GrammaticalOptimization/ExpressionInterpreter.cs @ 11659

Last change on this file since 11659 was 11659, checked in by gkronber, 5 years ago

#2283 initial import of implementation of grammatical optimization problem instances

File size: 2.9 KB
Line 
1using System;
2using System.Collections.Generic;
3using System.Diagnostics.Eventing.Reader;
4using System.Linq;
5using System.Runtime.Remoting.Messaging;
6using System.Text;
7using System.Threading.Tasks;
8
9namespace HeuristicLab.Problems.GrammaticalOptimization {
10  public class ExpressionInterpreter {
11    private string sentence;
12    private int syIdx;
13    // interprets sentences from L(G(Expr)):
14    // Expr -> Term { ('+' | '-' | '^' ) Term }
15    // Term -> Fact { ('*' | '/') Fact }
16    // Fact -> '!' Expr | '(' Expr ')' | Var
17    // Var -> 'a'..'z'
18
19    // for boolean problems the symbol * representes the AND operator, the symbol + represents the OR operator, ! = NOT, ^ = XOR
20
21    public bool Interpret(string sentence, bool[] vars) {
22      InitLex(sentence);
23      var d = new double[vars.Length];
24      for (int i = 0; i < vars.Length; i++) d[i] = vars[i] ? 1.0 : 0.0;
25      return !(Expr(d).IsAlmost(0));
26    }
27
28    public double Interpret(string sentence, double[] vars) {
29      InitLex(sentence);
30      return Expr(vars);
31    }
32
33
34    private void InitLex(string sentence) {
35      this.sentence = sentence;
36      this.syIdx = 0;
37    }
38
39    private char CurSy() {
40      if (syIdx >= sentence.Length) return '\0';
41      return sentence[syIdx];
42    }
43    private void NewSy() {
44      if (syIdx < sentence.Length) syIdx++;
45    }
46
47    // helper for xor
48    private double Not(double x) {
49      return x.IsAlmost(0) ? 1.0 : 0.0;
50    }
51
52    private double Expr(double[] d) {
53      var r = 0.0;
54      r = Term(d);
55      while (CurSy() == '+' || CurSy() == '-' || CurSy() == '^') {
56        if (CurSy() == '+') {
57          NewSy();
58          r += Expr(d);
59        } else if (CurSy() == '-') {
60          NewSy();
61          r -= Expr(d);
62        } else if (CurSy() == '^') {
63          NewSy();
64          var e = Expr(d);
65          r = Not(r) * e + r * Not(e); // xor = (!x AND y) OR (x AND !y)
66        }
67      }
68      return r;
69    }
70
71    private double Term(double[] d) {
72      var r = 0.0;
73      r = Fact(d);
74      while (CurSy() == '*' || CurSy() == '/') {
75        if (CurSy() == '*') {
76          NewSy();
77          r *= Term(d);
78        } else if (CurSy() == '/') {
79          NewSy();
80          r /= Term(d);
81        }
82      }
83      return r;
84    }
85
86    private double Fact(double[] d) {
87      double r = 0.0;
88      if (CurSy() == '!') {
89        NewSy();
90        r = Not(Expr(d));
91      } else if (CurSy() == '(') {
92        NewSy();
93        r = Expr(d);
94        if (CurSy() != ')') throw new ArgumentException();
95        NewSy();
96      } else if (CurSy() >= 'a' && CurSy() <= 'z') {
97        int o = Convert.ToByte(CurSy()) - Convert.ToByte('a');
98        if (o < 0 || o >= d.Length) throw new ArgumentException();
99        r = d[o];
100        NewSy();
101      } else throw new ArgumentException();
102      return r;
103    }
104
105  }
106}
Note: See TracBrowser for help on using the repository browser.