Boolean Expression (Grammar) Parser in C++

Boolean expression (grammar) parser in c++

Here is an implementation based on Boost Spirit.

Because Boost Spirit generates recursive descent parsers based on expression templates, honouring the 'idiosyncratic' (sic) precedence rules (as mentioned by others) is quite tedious. Therefore the grammar lacks a certain elegance.

Abstract Data Type

I defined a tree data structure using Boost Variant's recursive variant support, note the definition of expr:

struct op_or  {}; // tag
struct op_and {}; // tag
struct op_xor {}; // tag
struct op_not {}; // tag

typedef std::string var;
template <typename tag> struct binop;
template <typename tag> struct unop;

typedef boost::variant<var, 
        boost::recursive_wrapper<unop <op_not> >, 
        boost::recursive_wrapper<binop<op_and> >,
        boost::recursive_wrapper<binop<op_xor> >,
        boost::recursive_wrapper<binop<op_or> >
        > expr;

(full source below)

Grammar Rules

The following is the (slightly tedious) grammar definition, as mentioned.

Although I don't consider this grammar optimal, it is quite readable, and we have ourselves a statically compiled parser with strongly typed AST datatype in roughly 50 lines of code. Things could be considerably worse.

template <typename It, typename Skipper = qi::space_type>
    struct parser : qi::grammar<It, expr(), Skipper>
{
    parser() : parser::base_type(expr_)
    {
        using namespace qi;
        expr_  = or_.alias();

        not_ = ("not" > simple       ) [ _val = phx::construct<unop <op_not>>(_1)     ] | simple [ _val = _1 ];
#ifdef RIGHT_ASSOCIATIVE
        or_  = (xor_ >> "or"  >> or_ ) [ _val = phx::construct<binop<op_or >>(_1, _2) ] | xor_   [ _val = _1 ];
        xor_ = (and_ >> "xor" >> xor_) [ _val = phx::construct<binop<op_xor>>(_1, _2) ] | and_   [ _val = _1 ];
        and_ = (not_ >> "and" >> and_) [ _val = phx::construct<binop<op_and>>(_1, _2) ] | not_   [ _val = _1 ];
#else
        or_  = xor_ [ _val = _1 ] >> *("or"  >> xor_ [ _val = phx::construct<binop<op_or>> (_val, _1) ]);
        xor_ = and_ [ _val = _1 ] >> *("xor" >> and_ [ _val = phx::construct<binop<op_xor>>(_val, _1) ]);
        and_ = not_ [ _val = _1 ] >> *("and" >> not_ [ _val = phx::construct<binop<op_and>>(_val, _1) ]);
#endif

        simple = (('(' > expr_ > ')') | var_);
        var_ = qi::lexeme[ +alpha ];
    }

  private:
    qi::rule<It, var() , Skipper> var_;
    qi::rule<It, expr(), Skipper> not_, and_, xor_, or_, simple, expr_;
};

Note: I've left the old rule definitions that would result in right-associativity in the binary operators for reference, but left-associativity is the more natural, and therefore taken by default

Operating on the syntax tree

Obviously, you'd want to evaluate the expressions. For now, I decided to stop at just printing, so I don't have to do the lookup table for named variables :)

Traversing a recursive variant may look cryptic at first, but the boost::static_visitor<> is surprisingly simple once you get the hang of it:

struct printer : boost::static_visitor<void>
{
    printer(std::ostream& os) : _os(os) {}
    std::ostream& _os;

    //
    void operator()(const var& v) const { _os << v; }

    void operator()(const binop<op_and>& b) const { print(" & ", b.oper1, b.oper2); }
    void operator()(const binop<op_or >& b) const { print(" | ", b.oper1, b.oper2); }
    void operator()(const binop<op_xor>& b) const { print(" ^ ", b.oper1, b.oper2); }

    void print(const std::string& op, const expr& l, const expr& r) const
    {
        _os << "(";
            boost::apply_visitor(*this, l);
            _os << op;
            boost::apply_visitor(*this, r);
        _os << ")";
    }

    void operator()(const unop<op_not>& u) const
    {
        _os << "(";
            _os << "!";
            boost::apply_visitor(*this, u.oper1);
        _os << ")";
    }
};

std::ostream& operator<<(std::ostream& os, const expr& e)
{ boost::apply_visitor(printer(os), e); return os; }

Test output:

For the test cases in the code, the following is output, demonstrating correct handling of the precedence rules by adding (redundant) parentheses:

Live On Coliru

result: ((a & b) ^ ((c & d) | (a & b)))
result: ((a & b) ^ ((c & d) | (a & b)))
result: (a & b)
result: (a | b)
result: (a ^ b)
result: (!a)
result: ((!a) & b)
result: (!(a & b))
result: ((a | b) | c)

Note, compare to Live On Coliru, with -DRIGHT_ASSOCIATIVE

Full Code:

Live On Coliru

#include <boost/spirit/include/qi.hpp>
#include <boost/spirit/include/phoenix.hpp>
#include <boost/spirit/include/phoenix_operator.hpp>
#include <boost/variant/recursive_wrapper.hpp>

namespace qi    = boost::spirit::qi;
namespace phx   = boost::phoenix;

struct op_or  {};
struct op_and {};
struct op_xor {};
struct op_not {};

typedef std::string var;
template <typename tag> struct binop;
template <typename tag> struct unop;

typedef boost::variant<var, 
        boost::recursive_wrapper<unop <op_not> >, 
        boost::recursive_wrapper<binop<op_and> >,
        boost::recursive_wrapper<binop<op_xor> >,
        boost::recursive_wrapper<binop<op_or> >
        > expr;

template <typename tag> struct binop 
{ 
    explicit binop(const expr& l, const expr& r) : oper1(l), oper2(r) { }
    expr oper1, oper2; 
};

template <typename tag> struct unop  
{ 
    explicit unop(const expr& o) : oper1(o) { }
    expr oper1; 
};

struct printer : boost::static_visitor<void>
{
    printer(std::ostream& os) : _os(os) {}
    std::ostream& _os;

    //
    void operator()(const var& v) const { _os << v; }

    void operator()(const binop<op_and>& b) const { print(" & ", b.oper1, b.oper2); }
    void operator()(const binop<op_or >& b) const { print(" | ", b.oper1, b.oper2); }
    void operator()(const binop<op_xor>& b) const { print(" ^ ", b.oper1, b.oper2); }

    void print(const std::string& op, const expr& l, const expr& r) const
    {
        _os << "(";
            boost::apply_visitor(*this, l);
            _os << op;
            boost::apply_visitor(*this, r);
        _os << ")";
    }

    void operator()(const unop<op_not>& u) const
    {
        _os << "(";
            _os << "!";
            boost::apply_visitor(*this, u.oper1);
        _os << ")";
    }
};

std::ostream& operator<<(std::ostream& os, const expr& e)
{ boost::apply_visitor(printer(os), e); return os; }

template <typename It, typename Skipper = qi::space_type>
    struct parser : qi::grammar<It, expr(), Skipper>
{
    parser() : parser::base_type(expr_)
    {
        using namespace qi;

        expr_  = or_.alias();

        not_ = ("not" > simple       ) [ _val = phx::construct<unop <op_not>>(_1)     ] | simple [ _val = _1 ];
#ifdef RIGHT_ASSOCIATIVE
        or_  = (xor_ >> "or"  >> or_ ) [ _val = phx::construct<binop<op_or >>(_1, _2) ] | xor_   [ _val = _1 ];
        xor_ = (and_ >> "xor" >> xor_) [ _val = phx::construct<binop<op_xor>>(_1, _2) ] | and_   [ _val = _1 ];
        and_ = (not_ >> "and" >> and_) [ _val = phx::construct<binop<op_and>>(_1, _2) ] | not_   [ _val = _1 ];
#else
        or_  = xor_ [ _val = _1 ] >> *("or"  >> xor_ [ _val = phx::construct<binop<op_or>> (_val, _1) ]);
        xor_ = and_ [ _val = _1 ] >> *("xor" >> and_ [ _val = phx::construct<binop<op_xor>>(_val, _1) ]);
        and_ = not_ [ _val = _1 ] >> *("and" >> not_ [ _val = phx::construct<binop<op_and>>(_val, _1) ]);
#endif

        simple = (('(' > expr_ > ')') | var_);
        var_ = qi::lexeme[ +alpha ];

        BOOST_SPIRIT_DEBUG_NODE(expr_);
        BOOST_SPIRIT_DEBUG_NODE(or_);
        BOOST_SPIRIT_DEBUG_NODE(xor_);
        BOOST_SPIRIT_DEBUG_NODE(and_);
        BOOST_SPIRIT_DEBUG_NODE(not_);
        BOOST_SPIRIT_DEBUG_NODE(simple);
        BOOST_SPIRIT_DEBUG_NODE(var_);
    }

  private:
    qi::rule<It, var() , Skipper> var_;
    qi::rule<It, expr(), Skipper> not_, and_, xor_, or_, simple, expr_;
};

int main()
{
    for (auto& input : std::list<std::string> {
            // From the OP:
            "(a and b) xor ((c and d) or (a and b));",
            "a and b xor (c and d or a and b);",

            /// Simpler tests:
            "a and b;",
            "a or b;",
            "a xor b;",
            "not a;",
            "not a and b;",
            "not (a and b);",
            "a or b or c;",
            })
    {
        auto f(std::begin(input)), l(std::end(input));
        parser<decltype(f)> p;

        try
        {
            expr result;
            bool ok = qi::phrase_parse(f,l,p > ';',qi::space,result);

            if (!ok)
                std::cerr << "invalid input\n";
            else
                std::cout << "result: " << result << "\n";

        } catch (const qi::expectation_failure<decltype(f)>& e)
        {
            std::cerr << "expectation_failure at '" << std::string(e.first, e.last) << "'\n";
        }

        if (f!=l) std::cerr << "unparsed: '" << std::string(f,l) << "'\n";
    }

    return 0;
}

Bonus:

For bonus points, to get a tree exactly like shown in the OP:

Live On Coliru

static const char indentstep[] = "    ";

struct tree_print : boost::static_visitor<void>
{
    tree_print(std::ostream& os, const std::string& indent=indentstep) : _os(os), _indent(indent) {}
    std::ostream& _os;
    std::string _indent;

    void operator()(const var& v) const { _os << _indent << v << std::endl; }

    void operator()(const binop<op_and>& b) const { print("and ", b.oper1, b.oper2); }
    void operator()(const binop<op_or >& b) const { print("or  ", b.oper2, b.oper1); }
    void operator()(const binop<op_xor>& b) const { print("xor ", b.oper2, b.oper1); }

    void print(const std::string& op, const expr& l, const expr& r) const
    {
        boost::apply_visitor(tree_print(_os, _indent+indentstep), l);
        _os << _indent << op << std::endl;
        boost::apply_visitor(tree_print(_os, _indent+indentstep), r);
    }

    void operator()(const unop<op_not>& u) const
    {
        _os << _indent << "!";
        boost::apply_visitor(tree_print(_os, _indent+indentstep), u.oper1);
    }
};

std::ostream& operator<<(std::ostream& os, const expr& e)
{ 
    boost::apply_visitor(tree_print(os), e); return os; 
}

result:

Creating a separate boolean expression rule for a dynamic language

Conventional wisdom is: Don't try to do semantic analysis in your grammar.

First, it complicates the grammar, even if it is possible, as you have seen. By contrast, the type-checking rules are very simple when performed in a tree walk over the AST.

Second, it is not really possible. Since your language is dynamic, you don't really know what the type of any variable is. So a compile-time check could result in three cases, not two: good, bad, and unknown. That will be even more complicated in the grammar, but only slightly more complicated in the semantic analysis.

However, depending on the precise nature of your language, it might be possible to choose a middle ground. Generally, some operators -- boolean operators and comparisons --- definitely return boolean values, while some contexts definitely require boolean values. So you could add a boolean_expression non-terminal, used to indicate where results will definitely be boolean and where values must be boolean. Then you could insert into your grammar a single unit production

 boolean_expression: expression

with a semantic action which inserts a runtime check node into the AST.

During semantic analysis, this check can be eliminated if it is determined that it would always succeed or an error produced if it is determined that it would always fail. Otherwise, code will eventually be emitted to do the check.

The advantage of this solution is that the grammar then shows the contexts in which a boolean is required, without suffering from the Byzantine modifications necessary to fully enforce the requirement.

(In the examples below, I only show one boolean operator, one comparison operator, and one arithmetic operator. Obviously a real language would have more of each, but it does not change the presentation at all. I also didn't bother with the prologue, which must include precedence declarations for the operators.)

program : stmt_list
stmt_list:%empty
        | stmt_list stmt
stmt    : assign
        | call
        | empty
        | while
        | '{' stmt_list '}'
assign  : IDENTIFIER '=' expr ';'
call    : expr '(' expr_list ')' ';'
        | expr '(' ')' ';'
empty   : ';'
while   : "while" '(' boolean_expr ')' stmt
expr_list
        : expr
        | expr_list ',' expr
boolean_expr
        : boolean_term
        | boolean_expr "or" boolean_expr
        | expr '<' expr
boolean_term
        : "true" | "false"
        | expr               { /* insert conversion from expr to boolean */ }

expr    : term
        | expr '+' expr
term    : INTEGER
        | IDENTIFIER
        | '(' expr ')'

But it does place some restrictions on the language. In the simplest incarnation as presented above, a boolean value can never be used other than in a boolean context, which prevents boolean values from being first-class values. They can't be used as the right-hand side of an assignment or as an argument in a function call, for example, as is clear from the above grammar.

Also, the above grammar doesn't allow redundant parentheses around boolean expressions.

That's not very satisfactory, but we can do better by separating boolean results from boolean values at the cost of a slight complication in the grammar.

In most languages, boolean values can be created according to defined rules from other values; by convention, a value which is converted to a boolean true is called a "truthy" value. This can be very convenient, although it can also be slightly dangerous if there is too much latitude in the nature of the coercion. [Note 1] To control the damage, we might only allow automatic coercion to boolean in an explicitly boolean context, and never allow a boolean to be automatically coerced to a non-boolean. If you are willing to accept those restrictions, then we can still use the grammar as a tool for documenting boolean contexts and coercions.

In the following, we introduce four non-terminals, all representing some flavour of expression:

expr: a non-boolean expression
boolean_expr: a specifically boolean expression; the corresponding productions list the syntaxes which must have a boolean result.
truthy_expr: either a boolean expression or a non-boolean expression which could be coerced to a boolean expression. This non-terminal is used in places where a boolean value is required. [Note 2]
either_expr: either a boolean expression or a non-boolean expression in a context in which either might appear without coercion (assignments and function arguments, for example).

Note that the last two non-terminals have exactly the same productions, but very different semantics (and thus different semantic actions). Because the contexts in which they might appear are disjoint, no conflict results.

Other than the definition of the above non-terminals and their use in various contexts, the grammar is not much changed:

program : stmt_list
stmt_list:%empty
        | stmt_list stmt
stmt    : assign
        | call
        | empty
        | while
        | '{' stmt_list '}'
assign  : IDENTIFIER '=' either_expr ';'
call    : expr '(' expr_list ')' ';'
        | expr '(' ')' ';'
empty   : ';'
while   : "while" '(' truthy_expr ')' stmt
expr_list
        : either_expr
        | expr_list ',' either_expr

truthy_expr
        : boolean_expr
        | expr               { /* insert conversion from expr to boolean */ }

either_expr
        : boolean_expr
        | expr

boolean_expr
        : boolean_term
        | truthy_expr "or" truthy_expr
        | expr '<' expr
boolean_term
        : "true"
        | "false"
        | '(' boolean_expr ')'

expr    : term
        | expr '+' expr
term    : INTEGER
        | IDENTIFIER
        | '(' expr ')'

If you believe the above is too complicated, then go with the conventional wisdom and avoid semantics interspersed in your grammar. If, on the other hand, you feel that it has expository value and your language is such that the restrictions are acceptable, then adapt it to your purposes.

Notes:

The scheme does not depend on the existence of any "truthy" coercion, but if boolean values are first class, there will be expressions which can only be determined to be boolean at runtime (boolean variables, functions returning boolean values, etc.). Consider the run-time check that a value used in a boolean context is a boolean value to be a form of coercion into truthiness, where only true is true and only false is false, while all other values throw an error.
Personally, I've grown fond of limited automatic boolean coercions. It makes perfect sense to me that a file object be falsy if it is in an error condition, for example, or that a container be truthy if it is non-empty. Restricting these conversions to explicitly boolean contexts, such as the condition in a conditional statement, makes the automatic coercion acceptable to me. But I don't insist on the idea; if you don't like it, ignore the thought.
This isn't a very good name, but truthy_or_falsy_expr seemed too long and boolish_expr seemed too weird. Suggestions are welcome.

Boolean expression parser in lark fails to parse 'a OR b OR c'

I'm not familiar with Lark specifically, but normally if there's no direct way to implement optional repeating, these kinds of grammars are implemented as

    ?exp: term | exp OR term
    ?term: factor | term AND factor

From what I can find in documentation, Lark does support this kind of construct directly, though:

    ?exp: term (OR term)*
    ?term: factor (AND factor)*

These do result in different syntax trees:

# first parser output
Tree(exp, [
    Tree(exp, [
        Tree(symbol, [Token(__ANON_0, 'a')]),
        Token(OR, 'OR'), 
        Tree(symbol, [Token(__ANON_0, 'b')])]),
    Token(OR, 'OR'),
    Tree(symbol, [Token(__ANON_0, 'c')])])
# second parser output
Tree(exp, [
    Tree(symbol, [Token(__ANON_0, 'a')]),
    Token(OR, 'OR'),
    Tree(symbol, [Token(__ANON_0, 'b')]),
    Token(OR, 'OR'),
    Tree(symbol, [Token(__ANON_0, 'c')])])

Boolean and Math Expression Parser

http://www.antlr.org

Antlr grammars can be designed to allow for both parsing and evaluation.

Here's an example: http://www.antlr.org/wiki/display/ANTLR3/Expression+evaluator

How to parse a boolean expression and load it into a class?

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

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.

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.

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

￢((A ∧ B) ∨ C ∨ D) becomes ￢(((A ∧ B) ∨ C) ∨ 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

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

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

bool result = Root.Evaluate();

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!)).

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.

Here's the main method

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

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

At that point, in the main method, you can see I transform the list of tokens in Polish Notation order. It makes the creation of the tree much easier and I use a modified implementation of the Shunting Yard Algorithm for this:

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

After this transformation, our token list becomes NOT, OR, OR, C, D, AND, A, B.

At this point, we're ready to create the expression tree. The properties of Polish Notation allow us to just walk the Token List and recursively create the tree nodes (we'll use your BoolExpr class) as we go:

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

Now we're golden! We have the expression tree that represents the expression so we'll ask the user for the actual boolean values of each literal operand and evaluate the root node (which will recursively evaluate the rest of the tree as needed).

My Eval function follows, keep in mind I'd use some polymorphism to make this cleaner if I modified your 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();
}

As expected, feeding our test expression ￢((A ∧ B) ∨ C ∨ D) with values false, true, false, true for A, B, C, D respectively yields the result false.

Boolean Expression (Grammar) Parser in C++