Выполнить строку как участок кода в C#
1,00
р.
Имеется одномерный массив типа decimal.
Задача: Перебрать все возможные соотношения значений массива с целью поиска максимально релевантного. Функция определения релевантности есть. Единственное, что приходит в голову - создавать и рандомно менять ("мутировать") "генетический код" соотношения.
Пример: необходимо x[1] + x[5] * x[7] / x[3] представлять в виде 001A005C007D003, где трехзначные числа - номер элемента массива, а символы A,B,C,D - соответственно +,-,* и /. Это позволит отбрасывать наименее релевантные соотношения и запускать в "мутацию" более релевантные.
Вопрос: понятно, что сформировать строку исполняемого кода из такого "генетического кода" (простите за тавтологию) нетрудно, но мы получим просто переменную типа string, и как ее потом выполнить прямо в программе? И возможно ли это?
Ответ
Хей, давно что-то никто не писал парсеров. Давайте-ка разомнёмся и напишем.
Итак, для начала структура данных, которая описывает части выражения. Это стандартная реализация 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, как и ожидалось.
Проверку ошибок добавьте по вкусу.
Задача: Перебрать все возможные соотношения значений массива с целью поиска максимально релевантного. Функция определения релевантности есть. Единственное, что приходит в голову - создавать и рандомно менять ("мутировать") "генетический код" соотношения.
Пример: необходимо x[1] + x[5] * x[7] / x[3] представлять в виде 001A005C007D003, где трехзначные числа - номер элемента массива, а символы A,B,C,D - соответственно +,-,* и /. Это позволит отбрасывать наименее релевантные соотношения и запускать в "мутацию" более релевантные.
Вопрос: понятно, что сформировать строку исполняемого кода из такого "генетического кода" (простите за тавтологию) нетрудно, но мы получим просто переменную типа string, и как ее потом выполнить прямо в программе? И возможно ли это?
Ответ
Хей, давно что-то никто не писал парсеров. Давайте-ка разомнёмся и напишем.
Итак, для начала структура данных, которая описывает части выражения. Это стандартная реализация 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, как и ожидалось.
Проверку ошибок добавьте по вкусу.
