c# – 如何解析布尔表达式并将其加载到类中？

我将从表达式构建一个树来解析,然后首先遍历它.您可以参考wikipedia article about Binary Expression Trees来了解我的建议.

>首先添加省略的可选括号,使下一步更容易
>当您读取任何不是运算符或父项的内容时,请创建一个LEAF类型的节点
>当您读取任何操作符(在您的情况下,不是和,或)时,创建相应的运算符节点
>二进制运算符将先前和后面的节点作为子节点,一元运算符只得到下一个节点.

所以,对于你的例子?((∧B)∨C∨D),算法将如下：

?((∧B)∨C∨D)成为?(((A∧B)∨C)∨D)

>创建一个NOT节点,它将以小孩的形式获得以下开头圆括号的结果.
>创建LEAF节点,AND节点和B LEAF节点.并有A和B作为孩子.
>创建OR节点,它具有先前创建的AND作为子节点和新的LEAF节点.
>创建OR节点,它具有先前创建的OR和D作为子节点的新节点.

在这一点上,你的树看起来像这样：

NOT
   |
  OR
  /
 OR D
 / 
AND C
/
A B

然后,您可以添加一个根据其类型递归计算的Node.Evaluate()方法(此处可以使用多态).例如,它可能看起来像这样：

class LeafEx {
    bool Evaluate() {
        return Boolean.Parse(this.Lit);
    }
}

class NotEx {
    bool Evaluate() {
        return !Left.Evaluate();
    }
}

class OrEx {
    bool Evaluate() {
        return Left.Evaluate() || Right.Evaluate();
    }
}

等等等等.要得到你的表达式的结果,你只需要调用

bool result = Root.Evaluate();

好的,因为它不是一个任务,而是实际上是一件有趣的事情,我继续前进.我将在这里发布的一些代码与我之前描述的(并且一些部分缺少)不相关,但是我将把我的答案放在最后面,以供参考(没有什么是错误的(希望！)).

记住这是非常不合适的,我努力不修改您提供的BoolExpr类.修改它可以减少代码量.根本没有错误检查.

这是主要的方法

static void Main(string[] args)
{
    //We'll use ! for not,& for and,| for or and remove whitespace
    string expr = @"!((A&B)|C|D)";
    List<Token> tokens = new List<Token>();
    StringReader reader = new StringReader(expr);

    //Tokenize the expression
    Token t = null;
    do
    {
        t = new Token(reader);
        tokens.Add(t);
    } while (t.type != Token.TokenType.EXPR_END);

    //Use a minimal version of the Shunting Yard algorithm to transform the token list to polish notation
    List<Token> polishNotation = TransformToPolishNotation(tokens);

    var enumerator = polishNotation.GetEnumerator();
    enumerator.MoveNext();
    BoolExpr root = Make(ref enumerator);

    //Request boolean values for all literal operands
    foreach (Token tok in polishNotation.Where(token => token.type == Token.TokenType.LITERAL))
    {
        Console.Write("Enter boolean value for {0}: ",tok.value);
        string line = Console.ReadLine();
        booleanValues[tok.value] = Boolean.Parse(line);
        Console.WriteLine();
    }

    //Eval the expression tree
    Console.WriteLine("Eval: {0}",Eval(root));

    Console.ReadLine();
}

令牌化阶段为表达式的所有令牌创建一个令牌对象.它有助于使解析与实际算法分离.这是执行此操作的令牌类：

class Token
{
    static Dictionary<char,KeyValuePair<TokenType,string>> dict = new Dictionary<char,string>>()
    {
        {
            '(',new KeyValuePair<TokenType,string>(TokenType.OPEN_PAREN,"(")
        },{
            ')',string>(TokenType.CLOSE_PAREN,")")
        },{
            '!',string>(TokenType.UNARY_OP,"NOT")
        },{
            '&',string>(TokenType.BINARY_OP,"AND")
        },{
            '|',"OR")
        }
    };

    public enum TokenType
    {
        OPEN_PAREN,CLOSE_PAREN,UNARY_OP,BINARY_OP,LITERAL,EXPR_END
    }

    public TokenType type;
    public string value;

    public Token(StringReader s)
    {
        int c = s.Read();
        if (c == -1)
        {
            type = TokenType.EXPR_END;
            value = "";
            return;
        }

        char ch = (char)c;

        if (dict.ContainsKey(ch))
        {
            type = dict[ch].Key;
            value = dict[ch].Value;
        }
        else
        {
            string str = "";
            str += ch;
            while (s.Peek() != -1 && !dict.ContainsKey((char)s.Peek()))
            {
                str += (char)s.Read();
            }
            type = TokenType.LITERAL;
            value = str;
        }
    }
}

在这一点上,在主要的方法中,可以看到我以Polish Notation顺序转换令牌列表.它使得树的创建更加容易,我使用Shunting Yard Algorithm的修改实现为此：

static List<Token> TransformToPolishNotation(List<Token> infixTokenList)
{
    Queue<Token> outputQueue = new Queue<Token>();
    Stack<Token> stack = new Stack<Token>();

    int index = 0;
    while (infixTokenList.Count > index)
    {
        Token t = infixTokenList[index];

        switch (t.type)
        {
            case Token.TokenType.LITERAL:
                outputQueue.Enqueue(t);
                break;
            case Token.TokenType.BINARY_OP:
            case Token.TokenType.UNARY_OP:
            case Token.TokenType.OPEN_PAREN:
                stack.Push(t);
                break;
            case Token.TokenType.CLOSE_PAREN:
                while (stack.Peek().type != Token.TokenType.OPEN_PAREN)
                {
                    outputQueue.Enqueue(stack.Pop());
                }
                stack.Pop();
                if (stack.Count > 0 && stack.Peek().type == Token.TokenType.UNARY_OP)
                {
                    outputQueue.Enqueue(stack.Pop());
                }
                break;
            default:
                break;
        }

        ++index;
    }
    while (stack.Count > 0)
    {
        outputQueue.Enqueue(stack.Pop());
    }

    return outputQueue.Reverse().ToList();
}

在这个转换之后,我们的令牌列表变成NOT,C,D,A,B

此时,我们已经准备好创建表达式树.波兰符号的属性允许我们走路标签列表,并递归地创建树节点(我们将使用您的BoolExpr类)：

static BoolExpr Make(ref List<Token>.Enumerator polishNotationTokensEnumerator)
{
    if (polishNotationTokensEnumerator.Current.type == Token.TokenType.LITERAL)
    {
        BoolExpr lit = BoolExpr.CreateBoolVar(polishNotationTokensEnumerator.Current.value);
        polishNotationTokensEnumerator.MoveNext();
        return lit;
    }
    else
    {
        if (polishNotationTokensEnumerator.Current.value == "NOT")
        {
            polishNotationTokensEnumerator.MoveNext();
            BoolExpr operand = Make(ref polishNotationTokensEnumerator);
            return BoolExpr.CreateNot(operand);
        }
        else if (polishNotationTokensEnumerator.Current.value == "AND")
        {
            polishNotationTokensEnumerator.MoveNext();
            BoolExpr left = Make(ref polishNotationTokensEnumerator);
            BoolExpr right = Make(ref polishNotationTokensEnumerator);
            return BoolExpr.CreateAnd(left,right);
        }
        else if (polishNotationTokensEnumerator.Current.value == "OR")
        {
            polishNotationTokensEnumerator.MoveNext();
            BoolExpr left = Make(ref polishNotationTokensEnumerator);
            BoolExpr right = Make(ref polishNotationTokensEnumerator);
            return BoolExpr.CreateOr(left,right);
        }
    }
    return null;
}

现在我们金了！我们有表达式树表示表达式,所以我们将要求用户每个文字操作数的实际布尔值,并评估根节点(根据需要递归地评估树的其余部分).

我的Eval功能遵循,请记住,如果我修改了BoolExpr类,我将使用一些多态来使这个更清洁.

static bool Eval(BoolExpr expr)
{
    if (expr.IsLeaf())
    {
        return booleanValues[expr.Lit];
    }

    if (expr.Op == BoolExpr.BOP.NOT)
    {
        return !Eval(expr.Left);
    }

    if (expr.Op == BoolExpr.BOP.OR)
    {
        return Eval(expr.Left) || Eval(expr.Right);
    }

    if (expr.Op == BoolExpr.BOP.AND)
    {
        return Eval(expr.Left) && Eval(expr.Right);
    }

    throw new ArgumentException();
}

如预期的那样,对于A,B,我们的测试表达式?((∧B)∨C∨D)的值分别为false,true,false,为false.