source: branches/HeuristicLab.Problems.GrammaticalOptimization-gkr/HeuristicLab.Problems.GrammaticalOptimization/PartialExpressionInterpreter.cs @ 12294

using System;
using System.Collections.Generic;
using System.Linq;
using HeuristicLab.Common;

namespace HeuristicLab.Problems.GrammaticalOptimization {
  public class PartialExpressionInterpreter {
    private static readonly double[] emptyErc = { 0, 0, 0, 0, 0, 0, 0, 0, 0, 0 };
    private string sentence;
    private int syIdx;
    private Stack<double> stack = new Stack<double>();
    private Stack<char> opStack = new Stack<char>();
    // interprets sentences from L(G(Expr)):
    // Expr -> Term { ('+' | '-' | '^' ) Term } 
    // Term -> Fact { ('*' | '%') Fact }
    // Fact -> '!' Expr | '(' Expr ')' | Var | const
    // Var -> 'a'..'z'
    // const -> '0' .. '9'

    // uses protected division symbol %
    // constants are Koza-style ephemeral random constants (ERC). for now we only allow up to 10 constants.
    // The constant symbols '0' .. '9' are treated as ERC indices

    public Stack<double> Interpret(string sentence, double[] vars) {
      return Interpret(sentence, vars, emptyErc);
    }

    public Stack<double> Interpret(string sentence, double[] vars, double[] erc) {
      InitLex(sentence);
      stack.Clear(); opStack.Clear();
      Expr(vars, erc);
      return new Stack<double>(stack);
    }


    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 DoubleExtensions.IsAlmost(x, 0) ? 1.0 : 0.0;
    }

    private bool Expr(double[] d, double[] erc) {
      if (!Term(d, erc)) return false;
      var curSy = CurSy();
      while (curSy == '+' || curSy == '-' || curSy == '^') {
        if (curSy == '+') {
          NewSy();
          if (!Term(d, erc)) { stack.Push(-1.0); return false; }
          stack.Push(stack.Pop() + stack.Pop());
        } else if (curSy == '-') {
          NewSy();
          if (!Term(d, erc)) { stack.Push(-2.0); return false; return false; }
          stack.Push(-stack.Pop() + stack.Pop());
        } else {
          NewSy();
          if (!Term(d, erc)) { stack.Push(-3.0); return false; }
          var e = stack.Pop();
          var r = stack.Pop();
          stack.Push(Not(r) * e + r * Not(e)); // xor = (!x AND y) OR (x AND !y)
        }
        curSy = CurSy();
      }
      return true;
    }

    private bool Term(double[] d, double[] erc) {
      if (!Fact(d, erc)) { return false; }
      var curSy = CurSy();
      while (curSy == '*' || curSy == '%') {
        if (curSy == '*') {
          NewSy();
          if (!Fact(d, erc)) { stack.Push(-4.0); return false; }
          stack.Push(stack.Pop() * stack.Pop());
        } else {
          NewSy();
          if (!Fact(d, erc)) { stack.Push(-5.0); return false; }
          var nom = stack.Pop();
          var r = stack.Pop();
          if (HeuristicLab.Common.Extensions.IsAlmost(nom, 0.0)) nom = 1.0;
          stack.Push(r / nom);
        }
        curSy = CurSy();
      }
      return true;
    }

    private bool Fact(double[] d, double[] erc) {
      var curSy = CurSy();
      if (curSy == '!') {
        NewSy();
        if (!Expr(d, erc)) { stack.Push(-7.0); return false; }
        stack.Push(Not(stack.Pop()));
      } else if (curSy == '(') {
        NewSy();
        if (!Expr(d, erc)) { stack.Push(-8.0); return false; }
        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();
        stack.Push(d[o]);
        NewSy();
      } else if (curSy == '/') {
        // /-symbol is used in the expressionextender to represent inverse (1/x). 
        // this is necessary because we also use symbols 0..9 as indices for ERCs
        NewSy();
        if (!Fact(d, erc)) { stack.Push(-9.0); return false; }
        stack.Push(1.0 / stack.Pop());
      } else if (curSy >= '0' && curSy <= '9') {
        int o = (byte)curSy - (byte)'0';
        //int o = Convert.ToByte(CurSy()) - Convert.ToByte('a');
        if (o < 0 || o >= 10) throw new ArgumentException();
        stack.Push(erc[o]);
        NewSy();
      } else {
        return false;
      }
      return true;
    }

  }
}