trees
¶
Tools for working with Boolean expression trees.
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)[source]¶ 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)[source]¶ 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
()[source]¶ 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
-
static
build_tree
(postfix_tokens)[source]¶ Build a tree from a list of expression tokens in postfix order.
This method does not check that the tokens are indeed in postfix order; undefined behavior will ensue if you pass tokens in an order other than postfix.
Parameters: postfix_tokens (List[
str
]) – A list of string tokens from which to construct the tree of expression nodes.Returns: The root node of the constructed tree.
Return type: Raises: - InvalidArgumentTypeError – If
postfix_tokens
is not a list of strings. - InvalidArgumentValueError – If
postfix_tokens
is empty.
- InvalidArgumentTypeError – If
-
coalesce_negations
()[source]¶ 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
()[source]¶ 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
()[source]¶ 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)[source]¶ 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
-
iter_clauses
()[source]¶ 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
()[source]¶ 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
()[source]¶ 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
orNone
-
r_child
¶ This node’s left child;
None
indicates the absence of a child.Type: ExpressionTreeNode
orNone
-
to_cnf
()[source]¶ Return a transformed node, in conjunctive normal form.
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
-
to_primitives
()[source]¶ 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)[source]¶ 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)[source]¶ Bases:
tt.trees.tree_node.ExpressionTreeNode
An expression tree node for unary operators.
-
operator
¶ The actual operator object wrapped in this node.
Type: BooleanOperator
-