我有以下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,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()));
}
}
我应该使用什么算法来解析输入布尔表达式字符串,如“¬((∧B)∨C∨D)”,并将其加载到上面的类中？
解决方法
TL; DR：如果要查看代码,请跳转到答案的第二部分.
我将从表达式构建一个树来解析,然后首先遍历它.您可以参考wikipedia article about Binary Expression Trees来了解我的建议.
>首先添加省略的可选括号,使下一步更容易
>当您读取任何不是运算符或父项的内容时,请创建一个LEAF类型的节点
>当您读取任何操作符(在您的情况下,不是和,或)时,创建相应的运算符节点
>二进制运算符将先前和后面的节点作为子节点,一元运算符只得到下一个节点.
所以,对于你的例子¬((∧B)∨C∨D),算法将如下：
¬((∧B)∨C∨D)成为¬(((A∧B)∨C)∨D)
>创建一个NOT节点,它将以小孩的形式获得以下开头圆括号的结果.
>创建LEAF节点,AND节点和B LEAF节点.并有A和B作为孩子.
>创建OR节点,它具有先前创建的AND作为子节点和新的LEAF节点.
>创建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();
}
令牌化阶段为表达式的所有令牌创建一个令牌对象.它有助于使解析与实际算法分离.这是执行此操作的令牌类：
class Token
{
static Dictionary<char,keyvaluePair<TokenType,string>> dict = new Dictionary<char,string>>()
{
{
'(',new keyvaluePair<TokenType,string>(TokenType.OPEN_PAREN,"(")
},{
')',string>(TokenType.CLOSE_PAREN,")")
},{
'!',string>(TokenType.UNARY_OP,"NOT")
},{
'&',string>(TokenType.BINARY_OP,"AND")
},{
'|',"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;
}
}
}
在这一点上,在主要的方法中,可以看到我以Polish Notation顺序转换令牌列表.它使得树的创建更加容易,我使用Shunting Yard Algorithm的修改实现为此：
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,C,D,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,我们的测试表达式¬((∧B)∨C∨D)的值分别为false,true,false,为false.