如何解析布尔表达式并将其加载到类中? [英] How to parse a boolean expression and load it into a class?

查看：19
本文介绍了如何解析布尔表达式并将其加载到类中?的处理方法，对大家解决问题具有一定的参考价值，需要的朋友们下面随着小编来一起学习吧！

问题描述

我有以下 BoolExpr 类:

class BoolExpr
{
    public enum BOP { LEAF, AND, OR, NOT };

    //
    //  inner state
    //

    private BOP    _op;
    private BoolExpr _left;
    private BoolExpr _right;
    private String   _lit;

    //
    //  private constructor
    //

    private BoolExpr(BOP op, BoolExpr left, BoolExpr right)
    {
        _op = op;
        _left  = left;
        _right = right;
        _lit = null;
    }

    private BoolExpr(String literal)
    {
        _op = BOP.LEAF;
        _left  = null;
        _right = null;
        _lit = literal;
    }

    //
    //  accessor
    //

    public BOP Op
    {
        get { return _op;  }
        set { _op = value; }
    }

    public BoolExpr Left
    {
        get { return _left;  }
        set { _left = value; }
    }

    public BoolExpr Right
    {
        get { return _right;  }
        set { _right = value; }
    }

    public String Lit
    {
        get { return _lit; }
        set { _lit = value; }
    }

    //
    //  public factory
    //

    public static BoolExpr CreateAnd(BoolExpr left, BoolExpr right)
    {
        return new BoolExpr(BOP.AND, left, right);
    }

    public static BoolExpr CreateNot(BoolExpr child)
    {
        return new BoolExpr(BOP.NOT, child, null);
    }

    public static BoolExpr CreateOr(BoolExpr left, BoolExpr right)
    {
        return new BoolExpr(BOP.OR, left, right);
    }

    public static BoolExpr CreateBoolVar(String str)
    {
        return new BoolExpr(str);
    }

    public BoolExpr(BoolExpr other)
    {
        // No share any object on purpose
        _op = other._op;
        _left  = other._left  == null ? null : new BoolExpr(other._left);
        _right = other._right == null ? null : new BoolExpr(other._right);
        _lit = new StringBuilder(other._lit).ToString();
    }

    //
    //  state checker
    //

    Boolean IsLeaf()
    {
        return (_op == BOP.LEAF);
    }

    Boolean IsAtomic()
    {
        return (IsLeaf() || (_op == BOP.NOT && _left.IsLeaf()));
    }
}

我应该使用什么算法来解析输入的布尔表达式字符串，如￢((A ∧ B) ∨ C ∨ D)"并将其加载到上述类中?

What algorithm should I use to parse an input boolean expression string like "￢((A ∧ B) ∨ C ∨ D)" and load it into the above class?

推荐答案

TL;DR:如果您想查看代码，请跳到答案的第二部分.

TL;DR: If you want to see the code, jump to the second portion of the answer.

我会根据表达式构建一棵树进行解析，然后首先遍历它的深度.您可以参考维基百科关于二元表达式树的文章，以了解我的建议.

I would build a tree from the expression to parse and then traverse it depth first. You can refer to the wikipedia article about Binary Expression Trees to get a feel for what I'm suggesting.

  1. 首先添加省略的可选括号以使下一步更容易
  2. 当你读到任何不是运算符或括号的东西时，创建一个 LEAF 类型的节点
  3. 当您读取任何运算符(在您的情况下为not、and、or)时，创建相应的运算符节点
  4. 二元运算符将前后节点作为子节点，一元运算符只能获得下一个.
  1. Start by adding the omitted optional parentheses to make the next step easier
  2. When you read anything that is not an operator or a parenthese, create a LEAF type node
  3. When you read any operator (in your case not, and, or), create the corresponding operator node
  4. Binary operators get the previous and following nodes as children, unary operators only get the next one.

因此，对于您的示例 ￢((A ∧ B) ∨ C ∨ D)，算法将如下所示:

So, for your example ￢((A ∧ B) ∨ C ∨ D), the algorithm would go like this:

￢((A ∧ B) ∨ C ∨ D) 变成 ￢(((A ∧ B) ∨ C) ∨ D)

  1. 创建一个NOT节点，它会得到下面作为子节点打开paren的结果.
  2. 创建A LEAF 节点、AND 节点和B LEAF 节点.AND 有 A 和 B 作为孩子.
  3. 创建OR节点，它将之前创建的AND作为子节点和一个新的LEAF节点用于C.
  4. 创建OR节点，它有之前创建的OR和一个新的D节点作为子节点.
  1. Create a NOT node, it'll get the result of the following opening paren as a child.
  2. Create A LEAF node, AND node and B LEAF node. AND has A and B as children.
  3. Create OR node, it has the previously created AND as a child and a new LEAF node for C.
  4. Create OR node, it has the previously created OR and a new node for D as children.

此时，您的树看起来像这样:

At that point, your tree looks like this:

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

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

You can then add a Node.Evaluate() method that evaluates recursively based on its type (polymorphism could be used here). For example, it could look something like this:

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();
    }
}

等等等等.要获得表达式的结果，您只需要调用

And so on and so forth. To get the result of your expression, you then only need to call 

bool result = Root.Evaluate();

<小时>

好的，因为这不是一项任务，而且它实际上是一件很有趣的事情，所以我继续了.我将在此处发布的一些代码与我之前描述的内容无关(并且某些部分丢失了)，但我将在我的答案中留下顶部以供参考(其中没有任何错误(希望！)).

Alright, since it's not an assignment and it's actually a fun thing to implement, I went ahead. Some of the code I'll post here is not related to what I described earlier (and some parts are missing) but I'll leave the top part in my answer for reference (nothing in there is wrong (hopefully!)).

请记住，这远非最佳，我努力不修改您提供的 BoolExpr 类.修改它可以让你减少代码量.也根本没有错误检查.

Keep in mind this is far from optimal and that I made an effort to not modify your provided BoolExpr class. Modifying it could allow you to reduce the amount of code. There's also no error checking at all.

这里是主要方法

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();
}

标记化阶段为表达式的所有标记创建一个 Token 对象.它有助于将解析与实际算法分开.这是执行此操作的 Token 类:

The tokenization phase creates a Token object for all tokens of the expression. It helps keep the parsing separated from the actual algorithm. Here's the Token class that performs this:

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

此时，在 main 方法中，您可以看到我按照 波兰表示法 的顺序转换了标记列表.它使树的创建变得更加容易，为此我使用了调车场算法的修改实现:

At that point, in the main method, you can see I transform the list of tokens in Polish Notation order. It makes the creation of the tree much easier and I use a modified implementation of the Shunting Yard Algorithm for this:

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();
}

经过这个转换，我们的token列表变成了NOT, OR, OR, C, D, AND, A, B.

After this transformation, our token list becomes NOT, OR, OR, C, D, AND, A, B.

此时，我们已准备好创建表达式树.波兰表示法的属性允许我们在进行时只遍历令牌列表并递归创建树节点(我们将使用您的 BoolExpr 类):

At this point, we're ready to create the expression tree. The properties of Polish Notation allow us to just walk the Token List and recursively create the tree nodes (we'll use your BoolExpr class) as we go:

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;
}

现在我们是金色的！我们有表示表达式的表达式树，因此我们将询问用户每个文字操作数的实际布尔值并评估根节点(它将根据需要递归评估树的其余部分).

Now we're golden! We have the expression tree that represents the expression so we'll ask the user for the actual boolean values of each literal operand and evaluate the root node (which will recursively evaluate the rest of the tree as needed).

我的 Eval 函数如下，请记住，如果我修改了你的 BoolExpr 类，我会使用一些多态来使这个更简洁.

My Eval function follows, keep in mind I'd use some polymorphism to make this cleaner if I modified your BoolExpr class.

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) ∨ C ∨ D) 提供值 false, true, false, true 用于 A, B, C, D 分别产生结果false.

As expected, feeding our test expression ￢((A ∧ B) ∨ C ∨ D) with values false, true, false, true for A, B, C, D respectively yields the result false.

这篇关于如何解析布尔表达式并将其加载到类中?的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！

查看全文
相关文章
C#/.NET最新文章
热门教程
热门工具
登录 关闭
扫码关注1秒登录
发送“验证码”获取 | 15天全站免登陆