TL;DR：如果您想查看代码，请跳至答案的第二部分。
我将从要解析的表达式构建一棵树，然后深度优先遍历它。您可以参考关于二元表达式树的维基百科文章 http://en.wikipedia.org/wiki/Binary_expression_tree来感受一下我的建议。
- 首先添加省略的可选括号以使下一步更容易
- 当你读到任何不是运算符或括号的内容时，创建一个 LEAF 类型节点
- 当您阅读任何运算符时（在您的情况下
not, and, or),创建对应的算子节点
- 二元运算符将前一个和后一个节点作为子节点，一元运算符仅获取下一个节点。
所以，对于你的例子￢((A ∧ B) ∨ C ∨ D)，算法将如下所示：
￢((A ∧ B) ∨ C ∨ D)变成￢(((A ∧ B) ∨ C) ∨ D)
- 创建一个
NOT节点，它将获得以下左括号作为子节点的结果。
- Create
A LEAF node, AND节点和B LEAF node. AND has A and B作为孩子。
- Create
OR节点，它具有先前创建的AND作为一个孩子和一个新的LEAF节点为C.
- Create
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 方法中，您可以看到我将标记列表转换为波兰表示法 http://en.wikipedia.org/wiki/Polish_notation命令。它使树的创建变得更加容易，我使用了修改后的实现调车场算法 http://en.wikipedia.org/wiki/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, 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 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();
}
正如预期的那样，输入我们的测试表达式￢((A ∧ B) ∨ C ∨ D)有价值观false, true, false, true for A, B, C, D分别产生结果false.
