Data Structure for boolean expressions

[dragonad]

Say I have a Boolean formula:
F = "a and b or (c and b) and (a and b)" (some random expression)

Can anyone suggest a data structure that I could parse this into such that:
1. Knowing the priority of operators I could change F to
F = (a and b) or ((c and b) and (a and b)) (i.e. add parenthesis)
or
F = (a and b) or (c and b and a and b)
and evaluate the formula.
2. I could recognize G = "a and b" is a part of F. So that, I could convert the
formula to:
F = G or ((c and b) and G)
G = a and b
3. I could convert F to either conjunctive normal form or disjunctive normal form
4. I want to apply laws like (negation law, Demorgan's Law, etc.) to convert complex logic expression to desired CNF or DNF.

Any kind of reference is appreciable.

[strongdrink]

I am not sure that I quite understand the question... but...

bool F = ((a && b) || (a && b && c));

[dragonad]

Thanks for the reply. I should have been more clearer in my earlier post.

Okay forget the part where i say i want to evaluate the formula.

Say a user enters the expression: a and b or (c xor b) and (a and b)
What I want is to display to the user the following things:
1. (a and b) or ((c xor b) and (a and b)); (Notice the parenthesis)
2. (a and b) or not(not(c xor b) or not(a and b)); (application of Demorgan's law)
3. G <-> a and b; F <-> G or ((c xor b) and G); (recognizing repeated expressions within expressions)

where <-> is symbol for equivalence.
So, in general i want to manipulate the expressions rather than evaluate them. And I want to know what kind of data structure would help me do that.

[Galik]

dragonad wrote:

Can anyone suggest a data structure that I could parse this into ...

That looks a bit like a binary tree.

[dragonad]

F = "a and b or (c and b) and (a and b)" (some random expression)
3. G <-> a and b; F <-> G or ((c xor b) and G); (recognizing repeated expressions within expressions)

To some extent yes, but I cannot figure out how to recognize repeated expressions.
Thanks for all the help so far.

[aquaz]

I suggest you using a Composite pattern for the boolean expression. A BooleanExpression base class with BinaryBooleanExpression, UnaryBooleanExpression(for not) and VariableBooleanExpression for variables.
And for the manipuation, use the Visitor pattern: a visitor for the output, a visitor for the application of Demorgan's law(which can create or modify the expression inplace).
For the equivalence it's a bit thought, i think you can do it with a visitor in which you store the reference visitor and visit the other, and check type with dynamic_cast