Dynamically evaluating simple boolean logic in Python

I've got some dynamically-generated boolean logic expressions, like:

• (A or B) and (C or D)
• A or (A and B)
• A
• empty - evaluates to True

The placeholders get replaced with booleans. Should I,

1. Convert this information to a Python expression like True or (True or False) and eval it?
2. Create a binary tree where a node is either a bool or Conjunction/Disjunction object and recursively evaluate it?
3. Convert it into nested S-expressions and use a Lisp parser?
4. Something else?

Suggestions welcome.

It shouldn't be difficult at all to write a evaluator that can handle this, for example using pyparsing. You only have a few operations to handle (and, or, and grouping?), so you should be able to parse and evaluate it yourself.

You shouldn't need to explicitly form the binary tree to evaluate the expression.