如何解析布尔表达式并将其加载到类中
本文关键字:加载 何解析 布尔表达式 | 更新日期: 2023-09-27 18:21:43
我得到了以下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的结果 - 创建
A
LEAF
节点、AND
节点和B
LEAF
节点。CCD_ 15有CCD_ 16和CCD_ - 创建
OR
节点,它将先前创建的AND
作为子节点,并为C
创建新的LEAF
节点 - 创建
OR
节点,它将先前创建的OR
和D
的新节点作为子节点
在这一点上,你的树看起来是这样的:
NOT
|
OR
/'
OR D
/ '
AND C
/'
A B
然后可以添加一个Node.EEvaluate()方法,该方法根据其类型递归求值(这里可以使用多态性)。例如,它可能看起来像这样:
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;
}
}
}
在这一点上,在主方法中,您可以看到我按波兰符号顺序转换了标记列表。它使树的创建变得更加容易,我为此使用了调车场算法的修改实现:
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
。
现在,我们已经准备好创建表达式树了。Polish Notation的属性允许我们在进行时遍历令牌列表并递归地创建树节点(我们将使用您的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
。
从算法的角度来看,要解析表达式,需要一个堆栈。
我们使用两步算法:
- 乐星
lexing的目的是获取"关键字"、"标识符"answers"分隔符":-关键字是"if",然后是"else"(")"/''"/"等。。。-在您的案例中,标识符是"A"、"B"、"C"等。。。-分隔符是空白、制表、行尾、文件尾等…
词法由使用自动机组成。在lexing中,您将逐个字符地读取输入字符串。当你输入一个与你的关键字、标识符、分隔符兼容的字符时,你就开始了一个字符序列。当你使用分隔符时,你会停止序列,在字典中查找序列是否为关键字(如果不是,则为标识符);然后将tuple[sequence,keyword或identifier/class]放在堆栈上。
我把小关键字"("也可以看作分隔符的情况留给您。
- 解析
语法分析与语法相似。在您的情况下,唯一需要检查的规则是逗号和二进制操作,以及一个简单的标识符。
正式名称:
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传统上是由lexer完成的(就像lex工具一样)
- 传统上,解析是由解析器完成的(就像野牛工具一样)
- 工具允许编写这些函数,更像我在形式表达式中所做的
思想方面是程序编译的基础。编码这些东西会让你进步很多,因为它既困难又基本。