Выполнить строку как участок кода в C#

#c_sharp #строки #синтаксический_анализ

Имеется одномерный массив типа decimal. 

Задача: Перебрать все возможные соотношения значений массива с целью поиска максимально
релевантного. Функция определения релевантности есть. Единственное, что приходит в
голову - создавать и рандомно менять ("мутировать") "генетический код" соотношения. 

Пример: необходимо x[1] + x[5] * x[7] / x[3] представлять в виде 001A005C007D003,
где трехзначные числа - номер элемента массива, а символы A,B,C,D - соответственно
+,-,* и /. Это позволит отбрасывать наименее релевантные соотношения и запускать в
"мутацию" более релевантные.

Вопрос: понятно, что сформировать строку исполняемого кода из такого "генетического
кода" (простите за тавтологию) нетрудно, но мы получим просто переменную типа string,
и как ее потом выполнить прямо в программе? И возможно ли это?
    

Ответы

Ответ 1

Хей, давно что-то никто не писал парсеров.
Давайте-ка разомнёмся и напишем.

Итак, для начала структура данных, которая описывает части выражения. Это стандартная
реализация discriminated union:

class Node { }
class Index : Node { public int Value { get; set; } }
class BinaryOperation : Node
{
    public Node Left { get; set; }
    public Node Right { get; set; }
    public int Precedence { get; set; }
    public string Name { get; set; }
}


Теперь, лексер. Поскольку я ленивый, то для токенов не буду создавать отдельную структуру
данных, а просто использую Node и его варианты. Лексер у нас получится очень простой:

// вспомогательная таблица операций и их приоритетов
Dictionary Operations = new Dictionary()
{
    ['A'] = ("+", 1),
    ['B'] = ("-", 1),
    ['C'] = ("*", 2),
    ['D'] = ("/", 2)
};

// сам лексер
IEnumerable Tokenize(string s)
{
    int i = 0;
    while (i < s.Length)
    {
        switch (s[i])
        {
        // это операция? создаём узел операции
        case char c when Operations.ContainsKey(c):
            (var name, var prec) = Operations[c];
            yield return new BinaryOperation() { Precedence = prec, Name = name };
            i++;
            break;
        // это число, создаём узел индекса
        case char c when char.IsDigit(c):
            if (i + 2 >= s.Length || !int.TryParse(s.Substring(i, 3), out var num))
                throw new FormatException();
            yield return new Index() { Value = num };
            i += 3;
            break;
        default:
            throw new FormatException();
        }
    }
}


С лексером всё.

Дальше, парсер. Для построения синтаксического дерева из арифметического выражения
воспользуемся классическим алгоритмом сортировочной станции.

Node Scan(string s)
{
    Stack output = new Stack();
    Stack operations = new Stack();

    void Shift()
    {
        var op = operations.Pop();
        op.Right = output.Pop();
        op.Left = output.Pop();
        output.Push(op);
    }

    foreach (var token in Tokenize(s))
    {
        switch (token)
        {
        case Index i:
            output.Push(i);
            break;
        case BinaryOperation bin:
            while (operations.Count > 0 && operations.Peek().Precedence >= bin.Precedence)
                Shift();
            operations.Push(bin);
            break;
        }
    }
    while (operations.Count > 0)
        Shift();
    return output.Single();
}


Отлично, теперь бекэнд нашего компилятора. Скомпилируем Node в LINQ Expression, чтобы
потом скомпилировать в нормальную функцию. Здесь тоже никаких проблем. Единственная
хитрость — нам нужен «общий» параметр p.

using System.Linq;
using System.Linq.Expressions;




Expression> Build(Node n)
{
    var p = Expression.Parameter(typeof(int[]), "arr");
    return BuildRec(n);

    Expression> BuildRec(Node node)
    {
        switch (node)
        {
        case Index idx:
            return Expression.Lambda>(
                        Expression.ArrayAccess(p, Expression.Constant(idx.Value)), p);
        case BinaryOperation bin:
            var l = BuildRec(bin.Left);
            var r = BuildRec(bin.Right);
            var op = GetOp(bin.Name);
            return Expression.Lambda>(op(l.Body, r.Body), p);
        default:
            throw new ArgumentException();
        }
    }

    Func GetOp(string name)
    {
        switch (name)
        {
        case "+": return Expression.Add;
        case "-": return Expression.Subtract;
        case "*": return Expression.Multiply;
        case "/": return Expression.Divide;
        default: throw new ArgumentException();
        }
    }
}


Готово, проверяем!

// входная строка
var s = "001A005C007D003";
// получаем функцию
var node = Scan(s);
var func = Build(node).Compile();
// данные для функции
var array = new[] { 0, 1, 2, 3, 4, 5, 6, 7, 8, 9 };
var result = func(array);


Получаем результат 12, как и ожидалось.

Проверку ошибок добавьте по вкусу.


Ответ 2

Если вы хотите в самом сложном случае использовать базовые арифметические операции,
то нет смысла городить код сложными конструкциями. 

Представим, что у вас есть массив чисел с плавающей точкой и выражение типа 


  x[1] + x[5] * x[7] / x[3]


Для начала можно заменить все переменные значениями из массива 

string SetValues(string expression, double[] array)
{
    var result = expression;
    var regex = new Regex("x\\[(:?[0-9]+)\\]", RegexOptions.Compiled);
    foreach (Match match in regex.Matches(expression))
    {
        var ind = int.Parse(match.Groups[1].Value);     
        result = result.Replace(match.Value, array[ind]
        .ToString(CultureInfo.InvariantCulture));
    }
    return result;
}


Получим что то вроде 


  9.04579045206578 + 3.56569983231169 * 5.23985354939469 / 9.11708742339028


Теперь посчитаем выражение (старый добрый трюк с DataTable)

double Eval(string input)
{   
    return Convert.ToDouble(new DataTable().Compute(input, null));
}


В итоге пользоваться можно этой штукой как то так: 

void Main()
{
    // Генерим массив со случайными числами
    var random = new Random();
    var data = Enumerable.Range(0, 10).Select(x=>random.NextDouble()*10).ToArray();

    // Наше выражение
    var expression = "x[1] + x[5] * x[7] / x[3]";

    // результат, который ожидаем (для проверки)
    var realResult = data[1] + data[5] * data[7] / data[3];

    // Тут заменяем переменные значениями
    var expressionToEvaluate = SetValues(expression, data);

    // Тут наш вычисленный результат
    var result = Eval(expressionToEvaluate);

    // выводим все в консоль 
    Console.WriteLine($"real:{realResult}");
    Console.WriteLine($"calculated:{result}");
    Console.WriteLine($"from {expressionToEvaluate}");
}


Получим в консоли

real: 11,0951011644409
calculated: 11,0951011644409
from 9.04579045206578 + 3.56569983231169 * 5.23985354939469 / 9.11708742339028


Подробнее, что можно себе позволить использовать в выражении, описано тут https://msdn.microsoft.com/ru-ru/library/system.data.datacolumn.expression(v=vs.110).aspx


Ответ 3

Можно воспользоваться пакетом System.Linq.Dynamic:

var fn = DynamicExpression.ParseLambda("2+3").Compile();

Console.WriteLine(fn(null)); // 5


Передачу параметров с известными именами организовать тоже несложно:

class Params 
{
    public int[] x;
}

var fn = DynamicExpression.ParseLambda("x[1] + x[5] * x[7] / x[3]").Compile();

Console.WriteLine(fn(new Params { x = ... } ));


Однако, если вы собираетесь сначала формировать строку, а потом ее исполнять - лучше
так не делайте! Гораздо проще сразу сформировать нужное AST минуя стадию строки (и
System.Linq.Dynamic не понадобится):

var x = Expression.Parameter(typeof(int[]));
var body = Expression.Add(
    Expression.ArrayIndex(x, Expression.Constant(1)),
    Expression.Divide(
        Expression.Multiply(
            Expression.ArrayIndex(x, Expression.Constant(5)),
            Expression.ArrayIndex(x, Expression.Constant(7))
        ),
        Expression.ArrayIndex(x, Expression.Constant(3))
    )
);
var fn = Expression.Lambda>(body, x).Compile();

Console.WriteLine(fn(...));