O
Hey, it's been a while since no one's been writing passers.
Let's talk and write.So, for starters, the data structure that describes the parts of the expression. This is standard implementation https://en.wikipedia.org/wiki/Tagged_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; }
}
Now, Lexer. Because I'm lazy, I'm not gonna create a separate data structure for the tokens, but I'm just using it. Node and his options. Lexer will be very simple:// вспомогательная таблица операций и их приоритетов
Dictionary<char, (string, int)> Operations = new Dictionary<char, (string, int)>()
{
['A'] = ("+", 1),
['B'] = ("-", 1),
['C'] = ("*", 2),
['D'] = ("/", 2)
};
// сам лексер
IEnumerable<Node> 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();
}
}
}
That's it.Next, passer. To build a syntax tree from arithmetic expression, we use classical https://ru.wikipedia.org/wiki/%D0%90%D0%BB%D0%B3%D0%BE%D1%80%D0%B8%D1%82%D0%BC_%D1%81%D0%BE%D1%80%D1%82%D0%B8%D1%80%D0%BE%D0%B2%D0%BE%D1%87%D0%BD%D0%BE%D0%B9_%D1%81%D1%82%D0%B0%D0%BD%D1%86%D0%B8%D0%B8 ♪Node Scan(string s)
{
Stack<Node> output = new Stack<Node>();
Stack<BinaryOperation> operations = new Stack<BinaryOperation>();
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();
}
All right, now we have the bacon of our compiler. Compilation Node in LINQ Expression, to secondly compil normal function. There's no problem here either. The only trick is we need a “common” parameter. p♪using System.Linq;
using System.Linq.Expressions;
Expression<Func<int[], int>> Build(Node n)
{
var p = Expression.Parameter(typeof(int[]), "arr");
return BuildRec(n);
Expression<Func<int[], int>> BuildRec(Node node)
{
switch (node)
{
case Index idx:
return Expression.Lambda<Func<int[], int>>(
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<Func<int[], int>>(op(l.Body, r.Body), p);
default:
throw new ArgumentException();
}
}
Func<Expression, Expression, BinaryExpression> 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();
}
}
}
Ready, check!// входная строка
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);
We get results 12 as expected.Checking the mistakes, add the taste.
