Free cookie consent management tool by TermsFeed Policy Generator

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

Last change on this file since 11803 was 11803, checked in by gkronber, 8 years ago

#2283 moved problems into a separate folder

File size: 3.0 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      var curSy = CurSy();
57      while (curSy == '+' || curSy == '-' || curSy == '^') {
58        if (curSy == '+') {
59          NewSy();
60          r += Expr(d);
61        } else if (curSy == '-') {
62          NewSy();
63          r -= Expr(d);
64        } else {
65          NewSy();
66          var e = Expr(d);
67          r = Not(r) * e + r * Not(e); // xor = (!x AND y) OR (x AND !y)
68        }
69        curSy = CurSy();
70      }
71      return r;
72    }
73
74    private double Term(double[] d) {
75      var r = 0.0;
76      r = Fact(d);
77      var curSy = CurSy();
78      while (curSy == '*' || curSy == '/') {
79        if (curSy == '*') {
80          NewSy();
81          r *= Term(d);
82        } else {
83          NewSy();
84          r /= Term(d);
85        }
86        curSy = CurSy();
87      }
88      return r;
89    }
90
91    private double Fact(double[] d) {
92      double r = 0.0;
93      var curSy = CurSy();
94      if (curSy == '!') {
95        NewSy();
96        r = Not(Expr(d));
97      } else if (curSy == '(') {
98        NewSy();
99        r = Expr(d);
100        if (CurSy() != ')') throw new ArgumentException();
101        NewSy();
102      } else /* if (curSy >= 'a' && curSy <= 'z') */ {
103        int o = (byte)curSy - (byte)'a';
104        //int o = Convert.ToByte(CurSy()) - Convert.ToByte('a');
105        if (o < 0 || o >= d.Length) throw new ArgumentException();
106        r = d[o];
107        NewSy();
108      }
109      //} else throw new ArgumentException();
110      return r;
111    }
112
113  }
114}
Note: See TracBrowser for help on using the repository browser.