如何解析布尔表达式并将其加载到类中？
我有以下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) ”并将其加载到上面的类中？
TL; DR：如果要查看代码，请跳至答案的第二部分。
我将从表达式构建一个树来解析，然后首先遍历它的深度。 您可以参考维基百科有关二进制表达式树的文章来了解我的建议。
- 首先添加省略的可选括号，以使下一步更容易
- 当您读取非操作符或括号的任何内容时，请创建LEAF类型节点
- 当您读取任何运算符（在您的情况下
not，and，or）时，创建相应的运算符节点 - 二元运算符将前一个节点和后一个节点作为子节点，一元运算符只获取下一个节点。
所以，对于你的例子￢((A ∧ B) ∨ C ∨ D) ，算法将如下所示：
￢((A ∧ B) ∨ C ∨ D)变为￢(((A ∧ B) ∨ C) ∨ D)
- 创建一个
NOT节点，它将获得以下开放式paren作为孩子的结果。 - 创建
LEAF节点，AND节点和BLEAF节点。AND有A和B作为孩子。 - 创建
OR节点，它具有先前创建的AND作为子节点和C的新LEAF节点。 - 创建
OR节点，它具有先前创建的OR和D作为子节点的新节点。
那时，你的树看起来像这样：
NOT | OR /\ OR D / \ AND C /\ AB
然后，您可以添加一个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 tokens = new List (); 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 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> dict = new Dictionary>() { { '(', new KeyValuePair(TokenType.OPEN_PAREN, "(") }, { ')', new KeyValuePair(TokenType.CLOSE_PAREN, ")") }, { '!', new KeyValuePair(TokenType.UNARY_OP, "NOT") }, { '&', new KeyValuePair(TokenType.BINARY_OP, "AND") }, { '|', new KeyValuePair(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 TransformToPolishNotation(List infixTokenList) { Queue outputQueue = new Queue (); Stack stack = new Stack (); 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.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分别输入我们的测试表达式￢((A ∧ B) ∨ C ∨ D)值false, true, false, true ，结果为false 。
从算法的角度来看，要解析表达式，您需要一个堆栈。
我们使用两步算法：
- 乐星
lexing的目的是获得“关键字”，“标识符”和“分隔符”： – 关键字是“如果”，那么“其他”（”）”/ \”/’等……您的案例中的标识符是“A”，“B”，“C”等… – 分隔符是空格，制表，行尾，文件结尾等…
Lexing包括使用自动机。 在lexing中，您将通过char读取输入字符串char。 当您输入与您的关键字，标识符，分隔符之一兼容的char时，您将启动一系列char。 当您对分隔符进行编码时，您将停止序列，查看序列的字典是一个关键字（如果不是它是一个标识符）; 然后将元组[sequence，keyword或identifier / class]放在堆栈上。
我留下你作为exercice的小关键字”’的情况，也可以看作分隔符。
- 解析
解析类似于语法。 在您的情况下，唯一要检查的规则是逗号和二进制操作，只是一个简单的标识符。
forms上：
expression:: '(' expression ')' expression /\ expression expression \/ expression identifier
这可以通过递归函数写入。 首先反转你的堆栈，然后：
myParseExpression(stack, myC#ResultObject) { if(stack.top = kewyord.'(' ) then myParseOpenComma(all stack but top, myC#ResultObject) if(stack.top = keyword.'/\') then myParseBinaryAnd(stack, myC#ResultObject) } myParseOpenComma(stack, myC#ResultObject) { ... } myParseBinaryAnd(stack, myC#ResultObject) { myNewRigthPartOfExpr = new C#ResultObject myParseExpression(stack.top, myNewRigthPartOfExpr) remove top of stack; myNewLeftPartOfExpr = new C#ResultObject myParseExpression(stack.top, myNewLeftPartOfExpr) C#ResultObject.add("AND", myNewRigthPartOfExpr, myNewLeftPartOfExpr) } ...
有多个函数可以相互共享递归。 作为练习，尝试添加否定。
- Lexing传统上是由词法分析器（如lex工具）完成的。
- 解析是传统上由解析器（如野牛工具）完成的。
- 工具允许写出those函数，就像我在forms表达式中所做的那样。
这方面是程序编译的基础。 因为它很难而且很基础，因此编写东西会改善你。