C#のExpression(式木)を使って文字列で与えられた条件文をラムダ式に変換する

やること

本体の関数はCreateExpressionで、下記のようなことを行っている

• 一番外側のWhitespaceは除外
• 式全体が括弧で囲まれている場合、不要な括弧なので除外
• 一番優先度の低い演算子を探して、本体の演算子とする
  • 括弧で囲まれた位置にある演算子は無視（左辺、右辺のExpressionを作成するときに一番外側の括弧になってたときに初めて本体になれる）
• 本体の演算子がなかった場合は単項演算子のため、単項演算子としてExpressionを作成する（CreateUnaryExpression）
• 本体の演算子の左辺、右辺を切り取ってExpressionを作成する（再帰的にCreateExpressionを実行）
• 本体の演算子、左辺、右辺を二項演算子の各項としてExpressionを作成する

何も見ずにやったので最適なやり方ではないと思うけど、割といい線行ってるんじゃないかなという感じ

補記

Spanを使ってなるべくstringを作成しないように気を付けていたが、
Unityだと.NET Standard 2.0を使っていて、int.Parse関数にSpanのオーバーロードが無かったり（.NET 5.0だとある）、dictionaryから値を取るときにstringにしないといけなかったりしたため、結局stringになってしまっている。。。
Expression.***でExpressionを生成するときにallocationしている量に比べると少ない（Expression生成の1割程度）ので無視することにしよう
「((1 + 1) * 3 > a)」を1回Expressionにすると1kBぐらいallocationされてるが、多いのか少ないのか:thinking_face:

ソースコード

    private void Start()
    {
        var statement = "((1 + 1) * 3 > a)";
        var expression = CreateExpression(statement.AsSpan());
        Debug.Log(Expression.Lambda<Func<Dictionary<string, object>, bool>>(expression, dicParameterExpression).Compile().Invoke(dictionary));
    }

    private const char startbracket = '(';
    private const char endbracket = ')';
    private const char whitespace = ' ';

    //式木の中で使いたい変数はdictionaryに入れておく
    private Dictionary<string, object> dictionary = new Dictionary<string, object>()
    {
        {"a", 6 },
        {"b", 2 },
        {"c", 3 },
        {"flag", true },
    };

    private static readonly ParameterExpression dicParameterExpression = Expression.Parameter(typeof(Dictionary<string, object>), "dic");

    //使用できる演算子（優先度順に並べる）
    private static readonly List<(char[] operatorChars, ExpressionType type, Type parameterType)> sortedBinaryOperatorList = new List<(char[], ExpressionType, Type)>()
    {
        (new char[]{'*'}, ExpressionType.Multiply, typeof(int)),
        (new char[]{'+'}, ExpressionType.Add, typeof(int)),
        (new char[]{'>'}, ExpressionType.GreaterThan, typeof(int)),
        (new char[]{'&'}, ExpressionType.AndAlso, typeof(bool)),
        (new char[]{'|'}, ExpressionType.OrElse, typeof(bool)),
    };


    /// <summary>
    /// sourceStatementからExpressionを作成
    /// </summary>
    public Expression CreateExpression(ReadOnlySpan<char> sourceStatement)
    {
        var statement = sourceStatement;

        //statementの両端のWhitespaceと括弧は除外しておく
        statement = TrimWhiteSpace(statement);
        while(statement[0] == startbracket && statement[statement.Length - 1] == endbracket)
            statement = statement.Slice(1, statement.Length - 2);
        statement = TrimWhiteSpace(statement);

        //statementを1文字ずつ順番に見ていき、本体となる演算子を探す
        int bracketDepth = 0;
        var useBinaryOperatorIndex = -1;
        var operatorStartIndex = -1;
        for(var i = 0;i < statement.Length;i++)
        {
            var tmpStatement = statement.Slice(i, statement.Length - i);

            //括弧の深さを保持する
            if (tmpStatement[0] == startbracket)
            {
                bracketDepth++;
                continue;
            }
            else if (tmpStatement[0] == endbracket)
            {
                bracketDepth--;
                continue;
            }

            //括弧の中だった場合は飛ばす
            if (bracketDepth != 0)
                continue;
            //Whitespaceだった場合は飛ばす
            if (tmpStatement[0] == whitespace)
                continue;

            //次のWhitespaceまでで区切った区間を取得
            var whitespaceIndex = tmpStatement.IndexOf(whitespace);
            if (whitespaceIndex > 0)
                tmpStatement = tmpStatement.Slice(0, whitespaceIndex);

            //一番優先度の低い演算子がこのstatementの本体になる
            for(var operatorIndex = Math.Max(0, useBinaryOperatorIndex); operatorIndex < sortedBinaryOperatorList.Count; operatorIndex++)
            {
                var tmpOperator = sortedBinaryOperatorList[operatorIndex];
                if(tmpStatement.Length == tmpOperator.operatorChars.Length && tmpStatement.Contains(tmpOperator.operatorChars, StringComparison.Ordinal))
                {
                    useBinaryOperatorIndex = operatorIndex;
                    operatorStartIndex = i;
                }
            }
        }

        if (useBinaryOperatorIndex < 0 || operatorStartIndex < 0)
        {
            //単項だった場合
            return CreateUnaryExpression(statement);
        }

        //本体となる演算子の左右のExpressionを作成する
        var useOperator = sortedBinaryOperatorList[useBinaryOperatorIndex];
        var leftStatement = statement.Slice(0, operatorStartIndex);
        var leftExpression = CreateExpression(leftStatement);
        var rightStatement = statement.Slice(operatorStartIndex + useOperator.operatorChars.Length);
        var rightExpression = CreateExpression(rightStatement);

        //本体の演算子でExpressionを作成
        leftExpression = Expression.Convert(leftExpression, useOperator.parameterType);
        rightExpression = Expression.Convert(rightExpression, useOperator.parameterType);
        return Expression.MakeBinary(useOperator.type, leftExpression, rightExpression);
    }

    /// <summary>
    /// 単項式のExpressionを作成
    /// </summary>
    public Expression CreateUnaryExpression(ReadOnlySpan<char> sourceStatement)
    {
        var statement = TrimWhiteSpace(sourceStatement);

        //否定演算子の場合、後ろをExprsssionにしてから否定演算子を付ける
        const char notOperator = '!';
        var isNot = false;
        if (sourceStatement[0] == notOperator)
        {
            isNot = true;
            statement = sourceStatement.Slice(1);
        }

        //statementの中身に応じてExpressionを作成
        Expression expression = null;
        var statementString = statement.ToString();
        if (statement[0] == startbracket && statement[statement.Length - 1] == endbracket)
        {
            //statementが括弧で囲まれている場合は中身は式の可能性がある
            expression = CreateExpression(statement);
        }
        else if(int.TryParse(statementString, out var num))
        {
            //intにParseできた場合
            expression = Expression.Constant(num);
        }
        else
        {
            //それ以外の場合、statementの文字列をキーとしてdictionaryの要素を取得する
            expression = Expression.Property(dicParameterExpression, "Item", Expression.Constant(statementString));
        }

        //否定演算子がついていた場合はExpression.Notを足す
        if (isNot)
            expression = Expression.Not(Expression.Convert(expression, typeof(bool)));

        if (expression == null)
        {
            Debug.LogError($"Expression is null! statement:\"{statement.ToString()}\"");
        }

        return expression;
    }
    public ReadOnlySpan<char> TrimWhiteSpace(ReadOnlySpan<char> statement)
    {
        return statement.TrimStart(whitespace).TrimEnd(whitespace);
    }