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

Question

我有以下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)" 这样的输入布尔表达式字符串并将其加载到上面的类中？

Answer 1

TL; DR:如果要查看代码,请跳至答案的第二部分.

我将从表达式构建一个树来解析,然后首先遍历它.您可以参考维基百科关于二元表达式树的文章来了解我的建议.

1. 首先添加省略的可选括号,以便更轻松地完成下一步
2. 当您读取非操作符或括号的任何内容时,请创建LEAF类型节点
3. 当你读到的任何操作(在你的情况not,and,or),创建相应的运营商节点
4. 二元运算符将前一个节点和后一个节点作为子节点,一元运算符只获取下一个节点.

因此,对于您的示例?((A ? B) ? C ? D),算法将如下所示:

?((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作为子节点的新节点.

那时,你的树看起来像这样:

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

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

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方法中,您可以看到我以波兰表示法顺序转换标记列表.它使树的创建更容易,我使用Shunting Yard算法的修改实现:

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, AND, 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) ? C ? D)与值false, true, false, true对A, B, C, D分别产生的结果false.