com.fr.general.jsqlparser.util.cnfexpression

类 CNFConverter

java.lang.Object

com.fr.general.jsqlparser.util.cnfexpression.CNFConverter

public class CNFConverter
extends java.lang.Object

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

作者:

messfish

构造器概要

构造器

构造器和说明
CNFConverter()

方法概要

方法

限定符和类型	方法和说明
static Expression	convertToCNF(Expression expr) Since the class is only used once, I create this method to make the rest of the methods private.

从类继承的方法 java.lang.Object

clone, equals, finalize, getClass, hashCode, notify, notifyAll, toString, wait, wait, wait

构造器详细资料

CNFConverter

public CNFConverter()

方法详细资料

convertToCNF

public static Expression convertToCNF(Expression expr)

Since the class is only used once, I create this method to make the rest of the methods private.

参数:

expr - the expression that will be converted.

返回:

the converted expression.