Source code for tt.trees.expr_tree
"""An expression tree implementation for Boolean expressions."""
from ..definitions import OPERATOR_MAPPING, TT_NOT_OP
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.
"""
def __init__(self, postfix_tokens):
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; this is ``None`` for an empty tree.
:type: :class:`ExpressionTreeNode\
<tt.trees.tree_node.ExpressionTreeNode>`
"""
return self._root
[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.
:type input_dict: Dict{:class:`str <python:str>`: truthy}
:returns: The result of the expression tree evaluation.
:rtype: :class:`bool <python:bool>`
.. note::
This function does not check to ensure the validity of the
``input_dict`` argument in any way.
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.
"""
if not self.postfix_tokens:
self._root = None
return
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:
node = BinaryOperatorExpressionTreeNode(
token, stack.pop(), stack.pop())
else:
node = OperandExpressionTreeNode(token)
stack.append(node)
self._root = stack.pop()
def __str__(self):
if self._root is None:
return 'Empty!'
else:
return str(self._root)[:-1]