Source code for tt.trees.expr_tree

"""An expression tree implementation for Boolean expressions."""

from tt.definitions import (
    OPERATOR_MAPPING,
    TT_NOT_OP)
from tt.errors import (
    InvalidArgumentTypeError,
    InvalidArgumentValueError)

from .tree_node import (
    BinaryOperatorExpressionTreeNode,
    OperandExpressionTreeNode,
    UnaryOperatorExpressionTreeNode)


[docs]class BooleanExpressionTree(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 :class:`BooleanExpression <tt.expressions.bexpr.BooleanExpression>` class) will not be checked. Like expressions, expression trees cannot be empty. :param postfix_tokens: A list of tokens in postfix order, representing the structure of the tree; the validity/order of this list is not checked. :type postfix_tokens: List[:class:`str <python:str>`] :raises InvalidArgumentTypeError: If ``postfix_tokens`` is not a list or contains non-:class:`str <python:str>` elements. :raises 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 """ def __init__(self, postfix_tokens): if (not isinstance(postfix_tokens, list) or not all(isinstance(elt, str) for elt in postfix_tokens)): raise InvalidArgumentTypeError( 'postfix_tokens must be a list of strings') if not len(postfix_tokens): raise InvalidArgumentValueError('postfix_tokens cannot be empty') self._postfix_tokens = postfix_tokens self._root = None self._build_tree() @property def postfix_tokens(self): """The tokens, in postfix order, from which this tree was built. :type: List[:class:`str <python:str>`] """ return self._postfix_tokens @property def root(self): """The root of the tree. :type: :class:`ExpressionTreeNode\ <tt.trees.tree_node.ExpressionTreeNode>` """ return self._root @property def is_cnf(self): """Whether this tree is in conjunctive normal form. :type: :class:`bool <python: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 """ return self._root.is_cnf @property def is_dnf(self): """Whether this tree is in disjunctive normal form. :type: :class:`bool <python: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 """ return self._root.is_dnf
[docs] def evaluate(self, input_dict): """Evaluate the expression held in this tree for specified inputs. :param input_dict: 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. :type input_dict: Dict{:class:`str <python:str>`: truthy} :returns: The result of the expression tree evaluation. :rtype: :class:`bool <python:bool>` While you would normally evaluate expressions through the interface provided by the :class:`BooleanExpression\ <tt.expressions.bexpr.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 """ return self._root.evaluate(input_dict)
def _build_tree(self): """Iterate over the ``postfix_tokens``, constructing the tree. .. note:: This method will populate this class's ``root`` attribute. """ stack = [] operators = OPERATOR_MAPPING.keys() for token in self.postfix_tokens: if token in operators: if OPERATOR_MAPPING[token] == TT_NOT_OP: node = UnaryOperatorExpressionTreeNode( token, stack.pop()) else: right, left = stack.pop(), stack.pop() node = BinaryOperatorExpressionTreeNode( token, left, right) else: node = OperandExpressionTreeNode(token) stack.append(node) self._root = stack.pop() def __str__(self): return str(self._root)