我有以下 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()));
    }
}

我应该使用什么样的算法来解析等的输入布尔EX pression字符串¬（（A∧B）∨ç∨D）并加载它到上面的类？

What algorithm should I use to parse an input boolean expression string like "￢((A ∧ B) ∨ C ∨ D)" and load it into the above class?

推荐答案

TL; DR：如果你想看到的code，跳到答案的第二部分

TL;DR: If you want to see the code, jump to the second portion of the answer.

我将建立从ex pression树解析，然后第一次遍历的深度。您可以参考有关二进制防爆pression树木的维基百科文章来感受什么，我敢暗示。

I would build a tree from the expression to parse and then traverse it depth first. You can refer to the wikipedia article about Binary Expression Trees to get a feel for what I'm suggesting.

在开始加入省略可选圆括号使下一步更容易 当你读什么，是不是运营商或parenthese，创建叶型节点 当你阅读任何运营商（在你的情况不是，和，或），创建相应的操作员节点 二元运算得到previous和儿童以下节点，单目运算符只能得到下一个。 Start by adding the omitted optional parentheses to make the next step easier When you read anything that is not an operator or a parenthese, create a LEAF type node When you read any operator (in your case not, and, or), create the corresponding operator node Binary operators get the previous and following nodes as children, unary operators only get the next one.

所以，你的例子¬（（A∧B）∨ç∨D），算法会是这样的：

So, for your example ￢((A ∧ B) ∨ C ∨ D), the algorithm would go like this:

¬（（A∧B）∨ç∨D）变成¬（（（A∧B）∨C）∨D）

创建一个不是节点，它会得到下面的开放括号作为一个孩子的结果。 创建 A 叶节点，和节点， B 叶节点。 和的 A 和 B 的孩子。 创建或节点，它具有pviously创造了$ P $ 和作为一个孩子，一个新的叶节点 C 。 创建或节点，它具有previously创建或和一个新节点 D 的孩子。 Create a NOT node, it'll get the result of the following opening paren as a child. Create A LEAF node, AND node and B LEAF node. AND has A and B as children. Create OR node, it has the previously created AND as a child and a new LEAF node for C. Create OR node, it has the previously created OR and a new node for D as children.

在这一点上，你的树看起来是这样的：

At that point, your tree looks like this:

  NOT
   |
  OR
  /\
 OR D
 / \
AND C
/\
A B

您可以再增加一个Node.Evaluate（）方法计算递归基于它的类型（多态可以在这里使用）。例如，它可能看起来是这样的：

You can then add a Node.Evaluate() method that evaluates recursively based on its type (polymorphism could be used here). For example, it could look something like this:

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();
    }
}

等等等等。要获得你的前pression的结果，那么你只需要调用

And so on and so forth. To get the result of your expression, you then only need to call

bool result = Root.Evaluate();

好了，因为它不是一个赋值，这实际上是一个好玩的东西来实现，我继续。一些code，我会张贴在这里不涉及我刚才描述的（和某些部件丢失），但我会离开顶部在我的答案，以供参考（没有在那里是错误的（希望！） ）。

Alright, since it's not an assignment and it's actually a fun thing to implement, I went ahead. Some of the code I'll post here is not related to what I described earlier (and some parts are missing) but I'll leave the top part in my answer for reference (nothing in there is wrong (hopefully!)).

请记住，这是很不理想，而我做出了努力，不会修改您提供BoolExpr类。修改它可以让你减少code量。还有没有错误检查可言。

Keep in mind this is far from optimal and that I made an effort to not modify your provided BoolExpr class. Modifying it could allow you to reduce the amount of code. There's also no error checking at all.

下面是最主要的方法

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();
}

标记化阶段创造了的EX pression所有令牌令牌对象。它有助于保持与实际算法分离解析。下面是执行此令牌类：

The tokenization phase creates a Token object for all tokens of the expression. It helps keep the parsing separated from the actual algorithm. Here's the Token class that performs this:

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方法，你可以看到我改变令牌的列表中波兰表示法秩序。这使得创建的树更容易，而且我用href="http://en.wikipedia.org/wiki/Shunting-yard_algorithm">调车场算法的