Class CNFConverter
java.lang.Object
net.sf.jsqlparser.util.cnfexpression.CNFConverter
This class handles the conversion from a normal expression tree into
the CNF form.
Here is the definition of CNF form:
https://en.wikipedia.org/wiki/Conjunctive_normal_form
Basically it will follow these steps:
To help understanding, I will generate an example:
Here is the original tree:
OR
/ \
OR NOT
/ \ |
NOT H AND
| / \
NOT G OR
| / \
F H NOT
|
OR
/ \
AND L
/ \
( ) ( )
| |
J K
1. rebuild the tree by replacing the "and" and "or" operators
(which are binary) into their counterparts node that could hold
multiple elements. Also, leave out the parenthesis node between the
conditional operators to make the tree uniform.
After the transform, the result should be like this:
OR(M)
/ \
OR(M) NOT
/ \ |
NOT H AND(M)
| / \
NOT G OR(M)
| / \
F H NOT
|
OR(M)
/ \
AND(M) L
/ \
J K
2. push the not operators into the bottom of the expression. That
means the not operator will be the root of the expression tree
where no "and" or "or" exists. Be sure use the De Morgan's law
and double not law.
How to use De Morgan law:
For example, here is the original expression tree:
NOT
|
AND(M)
/ \
G H
After we use the De Morgan law, the result should be like this:
OR(M)
/ \
NOT NOT
| |
G H
After the transform, the result should be like this:
OR(M)
/ \
OR(M) OR(M)
/ \ / \
F H NOT AND(M)
| / \
G NOT OR(M)
| / \
H AND(M) L
/ \
J K
3. gather all the adjacent "and" or "or" operator together.
After doing that, the expression tree will be presented as:
all the and expression will be in either odd or even levels,
this will be the same for the or operator.
After the transform, the expression tree should be like this:
OR(M)
/ / \ \
F H NOT AND(M)
| / \
G NOT OR(M)
| / \
H AND(M) L
/ \
J K
4. push the and operator upwards until the root is an and
operator and all the children are or operators with multiple
components. At this time we get the result: an expression in CNF form.
How do we push and up? Use distribution law!
For example, here is the way to push the and up and merge them.
OR
/ \
AND L
/ \
J K
In the normal form, it could be: (J AND K) OR L.
If we apply the distribution law, we will get the result like this:
(J OR L) AND (K OR L), the tree form of this should be like:
AND
/ \
OR OR
/ \ / \
J L K L
So after we push the AND at the deepest level up and merge it with the
existing add, we get this result.
OR(M)
/ / \ \
F H NOT AND(M)
| / | \
G NOT OR(M) OR(M)
| / \ / \
H J L K L
Now let us push the and up and we will get the result like this:
AND(M)
/ | \
OR(M) OR(M) OR(M)
/ / \ \ / / | \ \ / / | \ \
F H NOT NOT F H NOT J L F H NOT K L
| | | |
G H G G
5. The last step, convert the Multiple Expression back to the binary
form. Note the final tree shall be left-inclined.
The final expression tree shall be like this:
AND
/ \
AND ( )
/ \ |
( ) ( ) part1
| |
OR part2
/ \
OR NOT
/ \ |
OR NOT H
/ \ |
F H G
part1: OR
/ \
OR L
/ \
OR K
/ \
OR NOT
/ \ |
F H G
part2: OR
/ \
OR L
/ \
OR J
/ \
OR NOT
/ \ |
F H G
-
Nested Class Summary
Nested Classes -
Field Summary
FieldsModifier and TypeFieldDescriptionprivate Expression
private Expression
private boolean
private Expression
private Expression
private Expression
-
Constructor Summary
Constructors -
Method Summary
Modifier and TypeMethodDescriptionprivate void
This is the final step of the CNF conversion: now we have the Expression tree that has one multiple and expression with a list of multiple or expression as the child.private Expression
convert
(Expression express) this method takes an expression tree and converts that into a CNF form.static Expression
convertToCNF
(Expression expr) private void
gather()
This method serves as dealing with the third step.private void
handleNot
(int index) This function mainly deals with pushing not operators down.private void
pushAnd
(Stack<CNFConverter.Mule> stack) This helper function is used to deal with pushing and up: generally, pop the top element out of the stack, use BFS to traverse the tree and push and up.private void
First, BFS the tree and gather all the or operators and their parents into a stack.private void
pushNot
(int index) This method is the helper function to push not operators down.private void
This method is used to deal with pushing not operators down.private void
reorder
(Expression express) this is the first step that rebuild the expression tree.
-
Field Details
-
root
-
dummy
-
temp1
-
temp2
-
child
-
isUsed
private boolean isUsed
-
-
Constructor Details
-
CNFConverter
public CNFConverter()
-
-
Method Details
-
convertToCNF
-
convert
this method takes an expression tree and converts that into a CNF form. Notice the 5 steps shown above will turn into 5 different methods. For the sake of testing, I set them public. return the converted expression.- Parameters:
express
- the original expression tree.- Throws:
IllegalStateException
-
reorder
this is the first step that rebuild the expression tree. Use the standard specified in the above class. Traverse the original tree recursively and rebuild the tree from that.- Parameters:
express
- the original expression tree.
-
pushNotDown
private void pushNotDown()This method is used to deal with pushing not operators down. Since it needs an extra parameter, I will create a new method to handle this. -
pushNot
private void pushNot(int index) This method is the helper function to push not operators down. traverse the tree thoroughly, when we meet the not operator. We only need to consider these three operators: MultiAndOperator, MultiOrOperator, NotOperator. Handle them in a seperate way. when we finish the traverse, the expression tree will have all the not operators pushed as downwards as they could. In the method, I use two global variables: temp1 and temp2 to traverse the expression tree. Notice that temp2 will always be the parent of temp1.- Parameters:
index
- the index of the children appeared in parents array.
-
handleNot
private void handleNot(int index) This function mainly deals with pushing not operators down. check the child. If it is not a logic operator(and or or). stop at that point. Else use De Morgan law to push not downwards.- Parameters:
index
- the index of the children appeared in parents array.
-
gather
private void gather()This method serves as dealing with the third step. It is used to put all the adjacent same multi operators together. BFS the tree and do it node by node. In the end we will get the tree where all the same multi operators store in the same odd level of the tree or in the same even level of the tree. -
pushAndUp
private void pushAndUp()First, BFS the tree and gather all the or operators and their parents into a stack. Next, pop them out and push the and operators under the or operators upwards(if there are). Do this level by level, which means during each level we will call the gather() method to make the tree uniform. When we move out of the stack. The expression tree shall be in CNF form. -
pushAnd
This helper function is used to deal with pushing and up: generally, pop the top element out of the stack, use BFS to traverse the tree and push and up. It will case the expression tree to have the and as the new root and multiple or as the children. Push them on the queue and repeat the same process until the newly generated or operator does not have any and operators in it(which means no elements will be added into the queue). when one level is finished, regroup the tree. Do this until the stack is empty, the result will be the expression in CNF form.- Parameters:
stack
- the stack stores a list of combined data.
-
changeBack
private void changeBack()This is the final step of the CNF conversion: now we have the Expression tree that has one multiple and expression with a list of multiple or expression as the child. So we need to convert the multiple expression back to the binary counterparts. Note the converted tree is left inclined. Also I attach a parenthesis node before the or expression that is attached to the and expression to make the generated result resembles the CNF form.
-