Push negations P68644

We wish to trasform a Boolean expression by pushing all the negations down to the variables. For instance, ¬(a∧ b) should be trasformed to (¬ a∨ ¬ b).

Expressions may contain variables (lowercase letters), conjunctions (’*’), disjunctions (’+’) and negations (’!’). For simplicity, expressions are written in their fully parenthised form. See the examples.

You are given an almost complete program (see attached code code.cc). The main function is already written, as well as a a simple Formula class that represents Boolean expressions using tree nodes. Here is the Node structure of these trees:

Each leaf node contains a variable in its op field. Each non-leaf node contains ’+’ or ’*’ in its op field and pointers to its left and right children. In addition, all nodes have a neg field that indicates whether or not this node is negated.

The only attribute in the Formula class is the root of the tree od nodes.

Your task is just to implement the void push_negations() method of the Formula class.

Do do so, you can add private methods to the class, but you cannot alter the Node structure nor the existing methods, constructors and destructors. The main() function is already written and you do not have to modify it.