c++ - how to convert a propositional logical tree into conjunction normal form (CNF) tree -

i have string string

     s="(=> p (or (and (not b)) (and b (not a))))"; 

and convert output cnf of string,like

( or ( not p ) ( or b ) ) ( or ( not p ) ( or ( not b ) ( not ) ) )

do need make struct treenode keep value?

     struct treenode {             string val;         // data in node.             treenode *left;   // pointer left subtree.             treenode *right;  // pointer right subtree.             //treenode *farther;//should use farther or not in convert cnf?       }; 

how make cnf, conjunctive normal form? please give algorithm detail. point of view, maybe use recursive function better solving problem, still can not think out how use recursion. or have other suggestion solving problem?

let's name function cnf, taking tree , returning tree in cnf.

1. first, replace equivalency p<=>q and(p=>q,q=>p) replace implications p=>q or(q,not(p)).

2. convert negation normal form: move not operations down tree, not operations bind atoms (a, b).

3. then, result of cnf(and(x,y)) simple: and(cnf(x),cnf(y)), cnf-like have ands high in tree.

4. the result of cnf(or(and(x,y),z)) little bit more complicated. here use rule of distribution of disjunction on conjunction, or(and(x,y),z) equivalent and(or(x,z),or(y,z)). in effect, cnf(or(and(x,y),z)) and(or(cnf(x),cnf(z)),or(cnf(y),cnf(z)).

and you're done.