如何分析一个布尔EX pression并将其加载到一个类？ [英] How to parse a boolean expression and load it into a class?

问题描述

我有以下 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()));
    }
}

我应该使用什么样的算法来解析等的输入布尔EX pression字符串¬（（A∧B）∨ç∨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：如果你想看到的code，跳到答案的第二部分

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

我将建立从ex pression树解析，然后第一次遍历的深度。您可以参考有关二进制防爆pression树木的维基百科文章来感受什么，我敢暗示。

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. 当你读什么，是不是运营商或parenthese，创建叶型节点
3. 当你阅读任何运营商（在你的情况不是，和，或），创建相应的操作员节点
4. 二元运算得到previous和儿童以下节点，单目运算符只能得到下一个。

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）∨ç∨D），算法会是这样的：

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

¬（（A∧B）∨ç∨D）变成¬（（（A∧B）∨C）∨D）

1. 创建一个不是节点，它会得到下面的开放括号作为一个孩子的结果。
2. 创建 A 叶节点，和节点， B 叶节点。 和的 A 和 B 的孩子。
3. 创建或节点，它具有pviously创造了$ P $ 和作为一个孩子，一个新的叶节点 C 。
4. 创建或节点，它具有previously创建或和一个新节点 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();
    }
}

等等等等。要获得你的前pression的结果，那么你只需要调用

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

bool result = Root.Evaluate();

---

好了，因为它不是一个赋值，这实际上是一个好玩的东西来实现，我继续。一些code，我会张贴在这里不涉及我刚才描述的（和某些部件丢失），但我会离开顶部在我的答案，以供参考（没有在那里是错误的（希望！） ）。

---

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类。修改它可以让你减少code量。还有没有错误检查可言。

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

标记化阶段创造了的EX pression所有令牌令牌对象。它有助于保持与实际算法分离解析。下面是执行此令牌类：

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方法，你可以看到我改变令牌的列表中波兰表示法秩序。这使得创建的树更容易，而且我用href="http://en.wikipedia.org/wiki/Shunting-yard_algorithm">调车场算法的

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

这个改造后，我们的记号列表变成 NOT，OR，OR，C，D和A，B 。

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

在这一点上，我们准备建立前pression树。波兰式的性能让我们刚刚走令牌列表和递归创建树节点（我们将使用你的 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;
}

现在我们是金！我们有重新presents前pression所以我们会要求用户输入每个字面值操作数的实际布尔值和评估根节点（这将递归地评估其他地区的前pression树树根据需要）。

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

正如预期的那样，喂养我们的测试EX pression ¬（（A∧B）∨ç∨D），其值假的，真正的，假的，真正的为 A，B，C，D 分别得出的结果假

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.

这篇关于如何分析一个布尔EX pression并将其加载到一个类？的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！