4

I'm trying to represent boolean expressions in sum of products form(SOP) in Python with only lists.

For example, I have boolean expression

ABC+DE(FG+IH)

I need to find a list equivalent of the expression above, so by reading the list or nested list and following certain rules to read the list, the program/programmer reading the list will be able to convert it back to the boolean expression.

One way I thought of doing this is constructing nested lists. Two rules to follow:

  1. elements in the same list are ANDed together
  2. lists are parallel to each other, therfore ORed together.

So for the example above, it will translate to:

[[A,B,C],[D,E,[[F,G],[I,H]]]]

But this set of rules conflicts itself in some cases. For example, given [[E,F],[D,C]], it can either mean EF+DC or EFDC, as [E,F] and [D,C] are in the same list so they should be anded, but lists are parallel so they should be ORed too.

I feel like I need to set some precedence between the 2 rules above, or add another rule to make it more clear.

Any thoughts or suggestions are welcome. Also it's not homework, just something for fun. Thanks in advance!!

4

5 回答 5

5

Why lists and not trees? 

OR = 0
AND = 1

class OpNode:
   def __init__(self, op, left, right):
       self.op = op
       self.left = left
       self.right = right

class LeafNode:
    def __init__(self, name, value):
       self.name = name
       self.value = value

A = LeafNode("A", True)
B = LeafNode("B", True)

exp = OpNode(OR, A, OpNode(AND, B, 
                                OpNode(OR, 
                                          LeafNode("C", False), 
                                          LeafNode("D", True))))

exp would be the equivalent of A+B(C+D)

于 2012-07-13T20:47:23.050 回答
5

You could go the LISPy route and have the first item in each list be the operator. For example, the expression you gave

ABC+DE(FG+IH)

would become

['or', ['and', A, B, C], ['and', D, E, ['or', ['and', F, G], ['and', I, H]]]]

Which is pretty readable, considering. Cheers!

于 2012-07-13T21:13:16.203 回答
2

You could have the outermost list mean "OR all direct entries", then swap the meaning of nested lists between OR and AND direct entries. If you count levels of nesting from the outermost being 1 then the terms in odd levels of nesting should be OR'd and the terms in even levels of nesting should be AND'd together.

So ABC+DE(FG+IH)

Becomes [[A,B,C],[D,E,[[F,G],[I,H]]]]

Here's some Python code:

It returns an expression from the list form:

def to_bool(lst, depth=0, or_them=True):
    if type(lst) == str:
        return lst
    else:
        partial = ( '+' if or_them else ''
                  ).join( to_bool(x, depth+1, not or_them) for x in lst)
        if or_them and depth > 0:
            # Mixture of variables and sublists so parenthesize
            return '(' + partial + ')'
        else:
            return partial

def main():
    A,B,C,D,E,F,G,H,I = 'ABCDEFGHI'
    e = [[A,B,C],[D,E,[[F,G],[I,H]]]]
    print('The list form of the boolean expression:', e)
    print('The boolean expression:', to_bool(e))


if __name__ == '__main__':
    main()

Its output:

The list form of the boolean expression: [['A', 'B', 'C'], ['D', 'E', [['F', 'G'], ['I', 'H']]]]
The boolean expression: ABC+DE(FG+IH)
于 2012-07-13T22:40:37.613 回答
1

I think that you can add an additional rule that when the basic elements beside the comma are lists, then they are ORed together. Hence, you will not get this conflicted interpretation.

Therefore [A,B] has both elements as singletons, so they and ANDed, but [[A,B],[C,D]] has ANDs between singletons and ORs between lists, resulting in AB+CD.

In a way, that means that your rule #2 has precedence over rule #1.

于 2012-07-13T20:49:34.587 回答
0

Use lists for AND, tuples for OR.

于 2012-07-13T20:51:18.440 回答