Free cookie consent management tool by TermsFeed Policy Generator

# source:branches/HeuristicLab.Problems.GrammaticalOptimization/HeuristicLab.Problems.GrammaticalOptimization/Problems/ExpressionInterpreter.cs@11832

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

linear value function approximation and good results for poly-10 benchmark

File size: 4.0 KB
Line
1using System;
2using System.Collections.Generic;
4using System.Linq;
5using System.Runtime.CompilerServices;
6using System.Runtime.Remoting.Messaging;
7using System.Text;
9using HeuristicLab.Common;
10
11namespace HeuristicLab.Problems.GrammaticalOptimization {
12  public class ExpressionInterpreter {
13    private static readonly double[] emptyErc = { 0, 0, 0, 0, 0, 0, 0, 0, 0, 0 };
14
15    private string sentence;
16    private int syIdx;
17    // interprets sentences from L(G(Expr)):
18    // Expr -> Term { ('+' | '-' | '^' ) Term }
19    // Term -> Fact { ('*' | '/') Fact }
20    // Fact -> '!' Expr | '(' Expr ')' | Var | const
21    // Var -> 'a'..'z'
22    // const -> '0' .. '9'
23
24    // constants are Koza-style ephemeral random constants (ERC). for now we only allow up to 10 constants.
25    // The constant symbols '0' .. '9' are treated as ERC indices
26
27    // for boolean problems the symbol * representes the AND operator, the symbol + represents the OR operator, ! = NOT, ^ = XOR
28
29    public bool Interpret(string sentence, bool[] vars) {
30      return Interpret(sentence, vars, emptyErc);
31    }
32
33    public bool Interpret(string sentence, bool[] vars, double[] erc) {
34      InitLex(sentence);
35      var d = new double[vars.Length];
36      for (int i = 0; i < vars.Length; i++) d[i] = vars[i] ? 1.0 : 0.0;
37      return !(Expr(d, erc).IsAlmost(0));
38    }
39
40    public double Interpret(string sentence, double[] vars) {
41      return Interpret(sentence, vars, emptyErc);
42    }
43
44    public double Interpret(string sentence, double[] vars, double[] erc) {
45      InitLex(sentence);
46      return Expr(vars, erc);
47    }
48
49
50    private void InitLex(string sentence) {
51      this.sentence = sentence;
52      this.syIdx = 0;
53    }
54
55    private char CurSy() {
56      if (syIdx >= sentence.Length) return '\0';
57      return sentence[syIdx];
58    }
59    private void NewSy() {
60      if (syIdx < sentence.Length) syIdx++;
61    }
62
63    // helper for xor
64    private double Not(double x) {
65      return x.IsAlmost(0) ? 1.0 : 0.0;
66    }
67
68    private double Expr(double[] d, double[] erc) {
69      var r = 0.0;
70      r = Term(d, erc);
71      var curSy = CurSy();
72      while (curSy == '+' || curSy == '-' || curSy == '^') {
73        if (curSy == '+') {
74          NewSy();
75          r += Expr(d, erc);
76        } else if (curSy == '-') {
77          NewSy();
78          r -= Expr(d, erc);
79        } else {
80          NewSy();
81          var e = Expr(d, erc);
82          r = Not(r) * e + r * Not(e); // xor = (!x AND y) OR (x AND !y)
83        }
84        curSy = CurSy();
85      }
86      return r;
87    }
88
89    private double Term(double[] d, double[] erc) {
90      var r = 0.0;
91      r = Fact(d, erc);
92      var curSy = CurSy();
93      while (curSy == '*' || curSy == '/') {
94        if (curSy == '*') {
95          NewSy();
96          r *= Term(d, erc);
97        } else {
98          NewSy();
99          r /= Term(d, erc);
100        }
101        curSy = CurSy();
102      }
103      return r;
104    }
105
106    private double Fact(double[] d, double[] erc) {
107      double r = 0.0;
108      var curSy = CurSy();
109      if (curSy == '!') {
110        NewSy();
111        r = Not(Expr(d, erc));
112      } else if (curSy == '(') {
113        NewSy();
114        r = Expr(d, erc);
115        if (CurSy() != ')') throw new ArgumentException();
116        NewSy();
117      } else if (curSy >= 'a' && curSy <= 'z') {
118        int o = (byte)curSy - (byte)'a';
119        //int o = Convert.ToByte(CurSy()) - Convert.ToByte('a');
120        if (o < 0 || o >= d.Length) throw new ArgumentException();
121        r = d[o];
122        NewSy();
123      } else /* if (curSy >= '0' && curSy <= '9') */ {
124        int o = (byte)curSy - (byte)'0';
125        //int o = Convert.ToByte(CurSy()) - Convert.ToByte('a');
126        if (o < 0 || o >= 10) throw new ArgumentException();
127        r = erc[o];
128        NewSy();
129      }
130      //} else throw new ArgumentException();
131      return r;
132    }
133
134  }
135}
Note: See TracBrowser for help on using the repository browser.