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

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

#2283: worked on grammatical optimization problem solvers (simple MCTS done)

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