Partition a predicate by "OR" logic in Java

Question

How to partition a predicate into several predicates based on the logic OR ( || )? The evaluation of the resulting predicates would be same as the input predicate. The resulting predicates must not contain logic OR ( || ). Any idea/algorithm/java/pseudo code would be helpful.

Sample input outputs:-

Input:  a>b || p>q
Output: a>b, p>q

Input: (a>b || p>q) && x>y
Output: (a>b && x>y), (p<q && x>y)

Input: (a>b || p>q) && (x>y || r>s)
Output: (a>b && x>y), (a>b && r>s), (p>q && x>y), (p>q && r>s)

Input: (a>b || p>q) && (x>y && r>s)
Output: (a>b && x>y && r>s), (p>q && x>y && r>s)

Input: (a>b || p>q) && (x>y && (r>s || m>n))
Output: (a>b && x>y && r>s),(a>b && x>y && m>n),(p>q && x>y && r>s),(p>q && x>y && m>n)

Thanks.

Answer 1

Here's a javascript function that recursively parses input then multiplies terms:

function parsePredicateIntoBinaryTree(predicate) {
    function trimParen(a) {
        return a.trim().replace(/^\(*/, '').replace(/\)*$/, '').trim();
    }
    function multiplyTerms(s, t) {
        return s.reduce(function (c, a) {
            t.forEach(function (b) {
                c.push(a.trim() + ' && ' + b.trim())
            });
            return c;
        }, []);
    }
    predicate = trimParen(predicate);
    var firstAmp = predicate.indexOf('&&')
    var leftTerm = predicate.substring(0, firstAmp);
    var rightTerm = predicate.substring(firstAmp + 2);
    var leftLeaf = leftTerm.indexOf('&&') < 0;
    var rightLeaf = rightTerm.indexOf('&&') < 0;
    if(leftLeaf && rightLeaf)
    {
        var a = trimParen(leftTerm).split('||');
        var b = trimParen(rightTerm).split('||');
        return multiplyTerms(a, b);
    }
    else if(leftLeaf && !rightLeaf)
    {
        var a = trimParen(leftTerm).split('||');
        var b = parsePredicateIntoBinaryTree(rightTerm);
        return multiplyTerms(a, b);
    }
    else if(!leftLeaf && rightLeaf)
    {
        var a = parsePredicateIntoBinaryTree(leftTerm);
        var b = trimParen(rightTerm).split('||');
        return multiplyTerms(a, b);
    }
    else if(!leftLeaf && !rightLeaf)
    {
        var a = parsePredicateIntoBinaryTree(leftTerm);
        var b = parsePredicateIntoBinaryTree(rightTerm);
        return multiplyTerms(a, b);
    }
}
function parsePredicate(predicate){
    console.log('Input:  ' + predicate);
    console.log('Output:  (' + parsePredicateIntoBinaryTree(predicate).join('),(') + ')');
}

parsePredicate('(a>b || p>q && (z<h || y>=e)) && (x>y && (r>s || m>n))');

Input:  (a>b || p>q && (z<h || y>=e)) && (x>y && (r>s || m>n))
Output:  (a>b && z<h && x>y && r>s),(a>b && z<h && x>y && m>n),(a>b && y>=e && x>y && r>s),(a>b && y>=e && x>y && m>n),(p>q && z<h && x>y && r>s),(p>q && z<h && x>y && m>n),(p>q && y>=e && x>y && r>s),(p>q && y>=e && x>y && m>n)

Answer 2

You parse input, e.g. (a>b || p>q) && (x>y && (r>s || m>n)), into a binary expression tree.

           &&
    ||              &&
 >      >      >          ||
a b    p q    x y      >      >
                      r s    m n

Then you locate a || node and clone the tree twice, replacing the || node with each side of the node.

       &&                              &&
 >           &&                   >           &&
a b     >          ||            p q     >          ||
       x y      >      >                x y      >      >
               r s    m n                       r s    m n

Then you do it again, and again, until all || are eliminated.

      &&                      &&                      &&                      &&
 >         &&            >         &&            >         &&            >         &&
a b     >      >        p q     >      >        a b     >      >        p q     >      >
       x y    r s              x y    r s              x y    m n              x y    m n

Finally, you print the result.

a>b && (x>y && r>s)
p>q && (x>y && r>s)
a>b && (x>y && m>n)
p>q && (x>y && m>n)