trees

Tools for working with Boolean expression trees.

trees.expr_tree module

An expression tree implementation for Boolean expressions.

class tt.trees.expr_tree.BooleanExpressionTree(postfix_tokens)

Bases: object

An expression tree for Boolean expressions.

This class expects any input it receives to be well-formed; any tokenized lists you pass it directly (instead of from the attribute of the BooleanExpression class) will not be checked. Like expressions, expression trees cannot be empty.

Parameters:

postfix_tokens (List[str]) – A list of tokens in postfix order, representing the structure of the tree; the validity/order of this list is not checked.

Raises:

• InvalidArgumentTypeError – If postfix_tokens is not a list or contains non-str elements.
• InvalidArgumentValueError – If postfix_tokens is an empty list.

Here’s a look at the basic functionality:

>>> from tt import BooleanExpressionTree
>>> tree = BooleanExpressionTree(['A', 'B', 'or',
...                               'C', 'D', 'E', 'or', 'or',
...                               'and'])
>>> print(tree)
and
`----or
|    `----A
|    `----B
`----or
     `----C
     `----or
          `----D
          `----E
>>> tree.is_cnf
True

When printing trees, it is important to note that the ordering of children will always be left and then right. Let’s illustrate this by continuing our above example:

>>> print(tree.root.l_child)
or
`----A
`----B
>>> print(tree.root.r_child)
or
`----C
`----or
     `----D
     `----E

evaluate(input_dict)

Evaluate the expression held in this tree for specified inputs.

Parameters:input_dict (Dict{str: truthy}) – A dict mapping string variable names to the values for which they should be evaluated. This variable is not check for validity in any way; you should perform validation before passing values here. Returns:The result of the expression tree evaluation. Return type:bool

While you would normally evaluate expressions through the interface provided by the BooleanExpression class, this interface is still exposed for your use if you want to avoid any overhead introduced by the extra layer of abstraction. For example:

>>> from tt import BooleanExpressionTree
>>> bet = BooleanExpressionTree(['A', 'B', 'xor'])
>>> bet.evaluate({'A': 1, 'B': 0})
True
>>> bet.evaluate({'A': 1, 'B': 1})
False

is_cnf

Whether this tree is in conjunctive normal form.

Type:bool

Here are a few examples:

>>> from tt import BooleanExpressionTree as bet
>>> b = bet(['A', 'B', 'xor'])
>>> print(b)
xor
`----A
`----B
>>> b.is_cnf
False
>>> b = bet(['A', 'B', 'or',
...          'C', 'B', 'E', 'or', 'or',
...          'D', 'A', 'C', 'or', 'or',
...          'and', 'and'])
>>> print(b)
and
`----or
|    `----A
|    `----B
`----and
     `----or
     |    `----C
     |    `----or
     |         `----B
     |         `----E
     `----or
          `----D
          `----or
               `----A
               `----C
>>> b.is_cnf
True

is_dnf

Whether this tree is in disjunctive normal form.

Type:bool

Here a few examples::

>>> from tt import BooleanExpressionTree as bet
>>> b = bet(['A', 'B', 'or',
...          'C', 'D', 'or',
...          'and'])
>>> print(b)
and
`----or
|    `----A
|    `----B
`----or
     `----C
     `----D
>>> b.is_dnf
False
>>> b.is_cnf
True
>>> b = bet(['A', 'B', 'C', 'and', 'and',
...          'D', 'E', 'F', 'G', 'and', 'and', 'and',
...          'H', 'I', 'and',
...          'or', 'or'])
>>> print(b)
or
`----and
|    `----A
|    `----and
|         `----B
|         `----C
`----or
     `----and
     |    `----D
     |    `----and
     |         `----E
     |         `----and
     |              `----F
     |              `----G
     `----and
          `----H
          `----I
>>> b.is_dnf
True

postfix_tokens

The tokens, in postfix order, from which this tree was built.

Type:List[str]

root

The root of the tree.

Type:ExpressionTreeNode

trees.tree_node module

A node, and related classes, for use in expression trees.

class tt.trees.tree_node.BinaryOperatorExpressionTreeNode(operator_str, l_child, r_child)

Bases: tt.trees.tree_node.ExpressionTreeNode

An expression tree node for binary operators.

operator

The actual operator object wrapped in this node.

Type:BooleanOperator

class tt.trees.tree_node.ExpressionTreeNode(symbol_name, l_child=None, r_child=None)

Bases: object

A base class for expression tree nodes.

This class is extended within tt and is not meant to be used directly.

If you plan to extend it, note that descendants of this class must compute the _is_cnf, _is_dnf, and _is_really_unary boolean attributes within their initialization. Additionally, descendants of this class must implemented the __eq__ magic method (but not __ne__).

apply_de_morgans()

Return a transformed node, with De Morgan’s Law applied.

Since nodes are immutable, the returned node, and all descendants, are new objects.

Returns:An expression tree node with all negated AND and OR operators transformed, following De Morgan’s Law. Return type:ExpressionTreeNode

coalesce_negations()

Return a transformed node, with consecutive negations coalesced.

Since nodes are immutable, the returned node, and all descendants, are new objects.

Returns:An expression tree node with all consecutive negations compressed into the minimal number of equivalent negations (either one or none). Return type:ExpressionTreeNode

distribute_ands()

Return a transformed nodes, with ANDs recursively distributed across ORed sub-expressions.

Since nodes are immutable, the returned node, and all descendants, are new objects.

Returns:An expression tree node with all applicable AND operators distributed across ORed sub-expressions. Return type:ExpressionTreeNode

distribute_ors()

Return a transformed nodes, with ORs recursively distributed across ANDed sub-expressions.

Since nodes are immutable, the returned node, and all descendants, are new objects.

Returns:An expression tree node with all applicable OR operators distributed across ANDed sub-expressions. Return type:ExpressionTreeNode

evaluate(input_dict)

Recursively evaluate this node.

This is an interface that should be defined in sub-classes. Node evaluation does no checking of the validity of inputs; they should be check before being passed here.

Parameters:input_dict (Dict{str: truthy) – A dictionary mapping expression symbols to the value for which they should be subsituted in expression evaluation. Returns:The evaluation of the tree rooted at this node. Return type:bool

is_cnf

Whether the tree rooted at this node is in conjunctive normal form.

Type:bool

is_dnf

Whether the tree rooted at this node is in disjunctive normal form.

Type:bool

is_really_unary

Whether the tree rooted at this node contains no binary operators.

Type:bool

iter_clauses()

Iterate the clauses in the expression tree rooted at this node.

If the normal form of the expression is ambiguous, then precedence will be given to conjunctive normal form.

Returns:Iterator of each CNF or DNF clause, rooted by a tree node, contained within the expression tree rooted at this node. Return type:Iterator[ExpressionTreeNode] Raises:RequiresNormalFormError – If this expression is not in conjunctive or disjunctive normal form.

iter_cnf_clauses()

Iterate the clauses in conjunctive normal form order.

Returns:Iterator of each CNF clause, rooted by a tree node, contained within the expression tree rooted at this node. Return type:Iterator[ExpressionTreeNode] Raises:RequiresNormalFormError – If the expression tree rooted at this node is not in conjunctive normal form.

iter_dnf_clauses()

Iterate the clauses in disjunctive normal form order.

Returns:Iterator of each DNF clause, rooted by a tree node, contained within the expression tree rooted at this node. Return type:Iterator[ExpressionTreeNode] Raises:RequiresNormalFormError – If the expression tree rooted at this node is not in disjunctive normal form.

l_child

This node’s left child; None indicates the absence of a child.

Type:ExpressionTreeNode or None

r_child

This node’s left child; None indicates the absence of a child.

Type:ExpressionTreeNode or None

symbol_name

The string operator/operand name wrapped in this node.

Type:str

to_primitives()

Return a transformed node, containing only NOTs, ANDs, and ORs.

Since nodes are immutable, the returned node, and all descendants, are new objects.

Returns:An expression tree node with all operators transformed to consist only of NOTs, ANDs, and ORs. Return type:ExpressionTreeNode

class tt.trees.tree_node.OperandExpressionTreeNode(operand_str)

Bases: tt.trees.tree_node.ExpressionTreeNode

An expression tree node for operands.

Nodes of this type will always be leaves in an expression tree.

class tt.trees.tree_node.UnaryOperatorExpressionTreeNode(operator_str, l_child)

Bases: tt.trees.tree_node.ExpressionTreeNode

An expression tree node for unary operators.

operator

The actual operator object wrapped in this node.

Type:BooleanOperator