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 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课程，我会使用一些多态性来使这个更简洁。

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