在.NET Core中实现字符串表达式到Calculation表达式树的转换

核心思路 #

采用递归下降解析法处理表达式：

1. 先预处理表达式，移除所有空格，简化后续解析逻辑
2. 递归处理括号：若表达式首尾为括号，优先解析括号内部内容
3. 按运算符优先级（|优先级低于&）找到最外层运算符，拆分表达式为左右两部分
4. 递归解析左右子表达式，最终组装成Calculation树形结构

实现代码 #

using System;

public class Calculation
{
    public bool? CurrentValue { get; set; }
    public Calculation LeftHandValue { get; set; }
    public Calculation RightHandValue { get; set; }
    public Func<bool, bool, bool> Function { get; set; }
}

public static class ExpressionParser
{
    // 示例：将数字转换为bool值，可根据实际需求修改
    private static bool GetBoolValue(int num)
    {
        return num != 0; // 0为false，非0为true
    }

    public static Calculation Parse(string expression)
    {
        // 预处理：移除所有空格
        var cleanedExpr = expression.Replace(" ", "");
        return ParseInternal(cleanedExpr);
    }

    private static Calculation ParseInternal(string expr)
    {
        // 处理括号：如果表达式被括号包裹，解析内部内容
        if (expr.StartsWith("(") && expr.EndsWith(")"))
        {
            return ParseInternal(expr.Substring(1, expr.Length - 2));
        }

        // 先找最外层的|运算符（优先级低，先拆分）
        var opIndex = FindOuterOperator(expr, '|');
        if (opIndex != -1)
        {
            var leftExpr = expr.Substring(0, opIndex);
            var rightExpr = expr.Substring(opIndex + 1);
            return new Calculation
            {
                LeftHandValue = ParseInternal(leftExpr),
                RightHandValue = ParseInternal(rightExpr),
                Function = (a, b) => a || b
            };
        }

        // 再找最外层的&运算符
        opIndex = FindOuterOperator(expr, '&');
        if (opIndex != -1)
        {
            var leftExpr = expr.Substring(0, opIndex);
            var rightExpr = expr.Substring(opIndex + 1);
            return new Calculation
            {
                LeftHandValue = ParseInternal(leftExpr),
                RightHandValue = ParseInternal(rightExpr),
                Function = (a, b) => a && b
            };
        }

        // 没有运算符，说明是数字节点
        if (int.TryParse(expr, out var num))
        {
            return new Calculation { CurrentValue = GetBoolValue(num) };
        }

        throw new ArgumentException($"无效的表达式片段：{expr}");
    }

    // 查找最外层的指定运算符（跳过括号内的内容）
    private static int FindOuterOperator(string expr, char op)
    {
        int bracketDepth = 0;
        for (int i = 0; i < expr.Length; i++)
        {
            switch (expr[i])
            {
                case '(':
                    bracketDepth++;
                    break;
                case ')':
                    bracketDepth--;
                    break;
                case char c when c == op && bracketDepth == 0:
                    return i;
            }
        }
        return -1;
    }
}

// 测试示例
public class Program
{
    public static void Main()
    {
        var expr = "(0 | ( 1 & 2 ))";
        var calc = ExpressionParser.Parse(expr);
        // 可自行添加逻辑验证生成的Calculation结构是否符合预期
    }
}

代码说明 #

1. 预处理步骤：移除表达式中所有空格，避免空格干扰运算符和数字的识别
2. 递归解析：
   • 遇到括号时，直接解析括号内部的子表达式
   • 优先处理|运算符（因为其优先级低于&），确保&运算先被解析为子树
   • 找到最外层运算符后，拆分表达式为左右两部分，递归解析后组装成父节点
3. 数字节点处理：将纯数字字符串转换为bool值，生成仅包含CurrentValue的叶子节点
4. 运算符查找：通过括号深度判断，确保只找到最外层的运算符，避免误拆分括号内的表达式

内容的提问来源于stack exchange，提问作者Mehmet Serkan Ekinci