"""Tools for interacting with Boolean expressions."""
import re
from contextlib import contextmanager
from tt._assertions import (
assert_all_valid_keys,
assert_iterable_contains_all_expr_symbols)
from tt.definitions import (
boolean_variables_factory,
CONSTANT_VALUES,
DELIMITERS,
is_valid_identifier,
OPERATOR_MAPPING,
SYMBOLIC_OPERATOR_MAPPING,
TT_NOT_OP)
from tt.errors import (
AlreadyConstrainedSymbolError,
BadParenPositionError,
EmptyExpressionError,
ExpressionOrderError,
InvalidArgumentTypeError,
InvalidArgumentValueError,
InvalidIdentifierError,
NoEvaluationVariationError,
UnbalancedParenError)
from tt.satisfiability import (
picosat)
from tt.trees import (
BinaryOperatorExpressionTreeNode,
ExpressionTreeNode,
OperandExpressionTreeNode,
UnaryOperatorExpressionTreeNode)
[docs]class BooleanExpression(object):
"""An interface for interacting with a Boolean expression.
Instances of ``BooleanExpression`` are meant to be immutable and can be
instantiated from a few different representations of expressions. The
simplest way to make an expression object is from a string::
>>> from tt import BooleanExpression
>>> BooleanExpression('(A or B) iff (C and D)')
<BooleanExpression "(A or B) iff (C and D)">
If you already have an instance of :class:`ExpressionTreeNode \
<tt.trees.tree_node.ExpressionTreeNode>` laying around, you can make a
new expression object from that, too::
>>> from tt import ExpressionTreeNode
>>> tree_root = ExpressionTreeNode.build_tree(
... ['A', 'B', 'or',
... 'C', 'D', 'and',
... 'iff'])
>>> BooleanExpression(tree_root)
<BooleanExpression "(A or B) iff (C and D)">
Additionally, any sub-tree node can be used to build an expression object.
Continuing from above, let's make a new expression object for each of the
sub-expressions wrapped in parentheses::
>>> BooleanExpression(tree_root.l_child)
<BooleanExpression "A or B">
>>> BooleanExpression(tree_root.r_child)
<BooleanExpression "C and D">
Expressions also implement the equality and inequality operators (``==``
and ``!=``). Equality is determined by the same semantic structure and the
same operand names; the string used to represent the operators in two
expressions is not taken into account. Here's a few examples::
>>> from tt import BooleanExpression as be
>>> be('A or B or C') == be('A or B or C')
True
>>> be('A or B or C') == be('A || B || C')
True
>>> be('A or B or C') == be('A or C or B')
False
:param expr: The expression representation from which this object is
derived.
:type expr: :class:`str <python:str>` or :class:`ExpressionTreeNode \
<tt.trees.tree_node.ExpressionTreeNode>`
:raises BadParenPositionError: If the passed expression contains a
parenthesis in an invalid position.
:raises EmptyExpressionError: If the passed expressions contains nothing
other than whitespace.
:raises ExpressionOrderError: If the expression contains invalid
consecutive operators or operands.
:raises InvalidArgumentTypeError: If ``expr`` is not an acceptable type.
:raises InvalidIdentifierError: If any parsed variable symbols in the
expression are invalid identifiers.
:raises UnbalancedParenError: If any parenthesis pairs remain unbalanced.
It is important to note that aside from :exc:`InvalidArgumentTypeError \
<tt.errors.arguments.InvalidArgumentTypeError>`, all exceptions raised in
expression initialization will be descendants of :exc:`GrammarError \
<tt.errors.grammar.GrammarError>`.
"""
[docs] def __init__(self, expr):
if not isinstance(expr, (str, ExpressionTreeNode)):
raise InvalidArgumentTypeError(
'expr must be a str or ExpressionTreeNode')
self._symbols = []
self._symbol_set = set()
self._tokens = []
self._postfix_tokens = []
if isinstance(expr, str):
self._init_from_str(expr)
elif isinstance(expr, ExpressionTreeNode):
self._init_from_expr_node(expr)
self._symbol_vals_factory = boolean_variables_factory(self._symbols)
self._tree = ExpressionTreeNode.build_tree(self._postfix_tokens)
self._constraints = {}
self._constrained_symbol_set = set()
def _init_from_expr_node(self, expr_node):
"""Initalize this object from an expression node."""
self._raw_expr = ''
with self._symbol_set_includes_constant_values():
self._init_from_expr_node_recursive_helper(expr_node)
def _init_from_expr_node_recursive_helper(self, expr_node, parent=None):
"""Recursive helper for initializing from an expression node.
This method will populate the ``_symbols``, ``_symbol_set``,
``_postfix_tokens``, ``_tokens``, and ``_raw_expr`` attributes of this
object.
"""
if isinstance(expr_node, OperandExpressionTreeNode):
operand_str = expr_node.symbol_name
self._tokens.append(operand_str)
self._postfix_tokens.append(operand_str)
self._raw_expr += operand_str
if operand_str not in self._symbol_set:
self._symbols.append(operand_str)
self._symbol_set.add(operand_str)
elif isinstance(expr_node, UnaryOperatorExpressionTreeNode):
operator_str = expr_node.symbol_name
self._tokens.append(operator_str)
self._raw_expr += operator_str
if operator_str not in SYMBOLIC_OPERATOR_MAPPING:
self._raw_expr += ' '
self._init_from_expr_node_recursive_helper(
expr_node.l_child, parent=expr_node)
self._postfix_tokens.append(operator_str)
elif isinstance(expr_node, BinaryOperatorExpressionTreeNode):
operator_str = expr_node.symbol_name
include_parens = True
if parent is None:
include_parens = False
elif isinstance(parent, BinaryOperatorExpressionTreeNode):
this_operator = OPERATOR_MAPPING[operator_str]
parent_operator = OPERATOR_MAPPING[parent.symbol_name]
if (expr_node is parent.r_child and
this_operator == parent_operator):
include_parens = False
elif (expr_node is parent.l_child and
this_operator == parent_operator and
(parent.r_child.is_really_unary or
this_operator == parent.r_child.operator)):
include_parens = False
if include_parens:
self._tokens.append('(')
self._raw_expr += '('
self._init_from_expr_node_recursive_helper(
expr_node.l_child, parent=expr_node)
self._tokens.append(operator_str)
self._raw_expr += (' ' + operator_str + ' ')
self._init_from_expr_node_recursive_helper(
expr_node.r_child, parent=expr_node)
if include_parens:
self._tokens.append(')')
self._raw_expr += ')'
self._postfix_tokens.append(operator_str)
def _init_from_str(self, raw_expr_str):
"""Initalize this object from a raw expression string."""
self._raw_expr = raw_expr_str.strip()
with self._symbol_set_includes_constant_values():
self._tokenize()
self._to_postfix()
@property
def is_cnf(self):
"""Whether this expression is in conjunctive norma form or not.
:type: :class:`bool <python:bool>`
.. code-block:: python
>>> from tt import BooleanExpression
>>> b = BooleanExpression('(A or ~B) and (~C or D or E) and F')
>>> b.is_cnf
True
>>> b = BooleanExpression('A nand B')
>>> b.is_cnf
False
"""
return self._tree.is_cnf
@property
def is_dnf(self):
"""Whether this expression is in conjunctive normal form or not.
:type: :class:`bool <python:bool>`
.. code-block:: python
>>> from tt import BooleanExpression
>>> b = BooleanExpression('(A and B) or (~C and D)')
>>> b.is_dnf
True
>>> b = BooleanExpression('(op1 or !op2) and (op3 or op4)')
>>> b.is_dnf
False
"""
return self._tree.is_dnf
@property
def raw_expr(self):
"""The raw string expression, parsed upon initialization.
This is what you pass into the ``BooleanExpression`` constructor; it is
kept on the object as an attribute for convenience.
:type: :class:`str <python:str>`
.. code-block:: python
>>> from tt import BooleanExpression
>>> b = BooleanExpression('A nand B')
>>> b.raw_expr
'A nand B'
"""
return self._raw_expr
@property
def symbols(self):
"""The list of unique symbols present in this expression.
The order of the symbols in this list matches the order of symbol
appearance in the original expression.
:type: List[:class:`str <python:str>`]
.. code-block:: python
>>> from tt import BooleanExpression
>>> b = BooleanExpression('A xor (B or C)')
>>> b.symbols
['A', 'B', 'C']
"""
return self._symbols
@property
def tokens(self):
"""The parsed, non-whitespace tokens of an expression.
:type: List[:class:`str <python:str>`]
.. code-block:: python
>>> from tt import BooleanExpression
>>> b = BooleanExpression('A xor (B or C)')
>>> b.tokens
['A', 'xor', '(', 'B', 'or', 'C', ')']
"""
return self._tokens
@property
def postfix_tokens(self):
"""Similar to the ``tokens`` attribute, but in postfix order.
:type: List[:class:`str <python:str>`]
.. code-block:: python
>>> from tt import BooleanExpression
>>> b = BooleanExpression('A xor (B or C)')
>>> b.postfix_tokens
['A', 'B', 'C', 'or', 'xor']
"""
return self._postfix_tokens
@property
def tree(self):
"""The tree node representing the root of the tree of this expression.
:type: :class:`ExpressionTreeNode \
<tt.trees.tree_node.ExpressionTreeNode>`
.. code-block:: python
>>> from tt import BooleanExpression
>>> b = BooleanExpression('A xor (B or C)')
>>> print(b.tree)
xor
`----A
`----or
`----B
`----C
"""
return self._tree
[docs] def __eq__(self, other):
if isinstance(other, BooleanExpression):
return self._tree == other._tree
else:
return NotImplemented
[docs] def __ne__(self, other):
return not (self == other)
[docs] def __str__(self):
return self._raw_expr
[docs] def __repr__(self):
return '<BooleanExpression "{}">'.format(self._raw_expr)
[docs] @contextmanager
def constrain(self, **kwargs):
"""A context manager to impose satisfiability constraints.
This is the interface for adding assumptions to the satisfiability
solving functionality provided through the :func:`sat_one` and
:func:`sat_all` methods.
It should be noted that this context manager is only designed to work
with the satisfiability-related functionality of this class.
Constrained symbol values will not have an effect on non-sat methods of
this class. For example::
>>> from tt import BooleanExpression
>>> b = BooleanExpression('(A or B) and (C or D)')
>>> with b.constrain(A=1):
... b.evaluate(A=0, B=1, C=1, D=0)
...
True
This context manager returns a reference to the same object upon which
it is called. This behavior is designed with the following use case in
mind::
>>> from tt import BooleanExpression
>>> with BooleanExpression('A or B').constrain(A=1, B=0) as b:
... b.sat_one()
...
<BooleanValues [A=1, B=0]>
:param kwargs: Keys are names of symbols in this expression; the
specified value for each of these keys will be added to the
``constraints`` attribute of this object for the duration of the
context manager.
:returns: A reference to the same object that called this method
(i.e., ``self`` in the context of this method).
:rtype: :class:`BooleanExpression`
:raises AlreadyConstrainedSymbolError: If trying to constrain this
expression with multiple context managers.
:raises ExtraSymbolError: If a symbol not in this expression is passed
through ``kwargs``.
:raises InvalidArgumentValueError: If no contraints are specified
(i.e., ``kwargs`` is empty).
:raises InvalidBooleanValueError: If any values from ``kwargs`` are not
valid Boolean inputs.
"""
if not kwargs:
raise InvalidArgumentValueError(
'Must specify at least one constraint')
assert_all_valid_keys(kwargs, self._symbol_set)
kwarg_key_set = set(kwargs.keys())
conflicts = self._constrained_symbol_set & kwarg_key_set
if conflicts:
symbols_str = ', '.join('"{}"'.format(s) for s in
sorted(conflicts))
raise AlreadyConstrainedSymbolError(
'Symbol' + (' ' if len(conflicts) == 1 else 's ') +
symbols_str + ' cannot be constrained multiple times')
self._constraints.update(kwargs)
self._constrained_symbol_set |= kwarg_key_set
yield self
self._constrained_symbol_set -= kwarg_key_set
self._constraints = {}
[docs] def sat_one(self):
"""Find a combination of inputs that satisfies this expression.
Under the hood, this method is using the functionality exposed in tt's
:mod:`satisfiability.picosat <tt.satisfiability.picosat>` module.
Here's a simple example of satisfying an expression::
>>> from tt import BooleanExpression
>>> b = BooleanExpression('A xor 1')
>>> b.sat_one()
<BooleanValues [A=0]>
Don't forget about the utility provided by the :func:`constrain`
context manager::
>>> b = BooleanExpression('(A nand B) iff C')
>>> with b.constrain(A=1, C=1):
... b.sat_one()
...
<BooleanValues [A=1, B=0, C=1]>
Finally, here's an example when the expression cannot be satisfied::
>>> with BooleanExpression('A xor 1').constrain(A=1) as b:
... b.sat_one() is None
...
True
:returns: :func:`namedtuple <python:collections.namedtuple>`-like
object representing a satisfying set of values (see
:func:`boolean_variables_factory \
<tt.definitions.operands.boolean_variables_factory>` for more
information about the type of object returned); ``None``
will be returned if no satisfiable set of inputs exists.
:rtype: :func:`namedtuple <python:collections.namedtuple>`-like object
or ``None``
:raises NoEvaluationVariationError: If this is an expression of only
constants.
"""
if not self._symbols:
raise NoEvaluationVariationError(
'Cannot attempt to satisfy an expression of only constants')
if not (self._symbol_set - self._constrained_symbol_set):
# shortcut if all symbols are constrained
if self.evaluate_unchecked(**self._constraints):
return self._symbol_vals_factory(**self._constraints)
else:
return None
clauses, assumptions, symbol_to_index_map, index_to_symbol_map = \
self._to_picosat_clauses_assumptions_and_symbol_mappings()
if not assumptions:
# cannot pass empty list of assumptions to picosat
assumptions = None
picosat_result = picosat.sat_one(clauses, assumptions=assumptions)
if picosat_result is None:
return None
result_dict = self._picosat_result_as_dict(
picosat_result, symbol_to_index_map, index_to_symbol_map)
return self._symbol_vals_factory(**result_dict)
[docs] def sat_all(self):
"""Find all combinations of inputs that satisfy this expression.
Under the hood, this method is using the functionality exposed in tt's
:mod:`satisfiability.picosat <tt.satisfiability.picosat>` module.
Here's a simple example of iterating through a few SAT solutions::
>>> from tt import BooleanExpression
>>> b = BooleanExpression('(A xor B) and (C xor D)')
>>> for solution in b.sat_all():
... print(solution)
...
A=1, B=0, C=1, D=0
A=1, B=0, C=0, D=1
A=0, B=1, C=0, D=1
A=0, B=1, C=1, D=0
We can also constrain away a few of those solutions::
>>> with b.constrain(A=1, C=0):
... for solution in b.sat_all():
... print(solution)
...
A=1, B=0, C=0, D=1
:returns: An iterator of
:func:`namedtuple <python:collections.namedtuple>`-like objects
representing satisfying combinations of inputs; if no satisfying
solutions exist, the iterator will be empty.
:rtype: Iterator[:func:`namedtuple <python:collections.namedtuple>`
-like objects]
:raises NoEvaluationVariationError: If this is an expression of only
constants.
"""
if not self._symbols:
raise NoEvaluationVariationError(
'Cannot attempt to satisfy an expression of only constants')
if not (self._symbol_set - self._constrained_symbol_set):
# shortcut if all symbols are constrained
if self.evaluate_unchecked(**self._constraints):
yield self._symbol_vals_factory(**self._constraints)
else:
# empty iterator
while False:
yield None
return
clauses, assumptions, symbol_to_index_map, index_to_symbol_map = \
self._to_picosat_clauses_assumptions_and_symbol_mappings()
if not assumptions:
# cannot pass empty list of assumptions to picosat
assumptions = None
for picosat_sol in picosat.sat_all(clauses, assumptions=assumptions):
result_dict = self._picosat_result_as_dict(
picosat_sol, symbol_to_index_map, index_to_symbol_map)
yield self._symbol_vals_factory(**result_dict)
def _picosat_result_as_dict(self, results, symbol_to_index_map,
index_to_symbol_map):
"""Convert a PicoSAT result into a BooleanValues tuple."""
result_dict = {}
signed_symbol_indices = (index for index in results if abs(index) in
index_to_symbol_map)
for index in signed_symbol_indices:
symbol_name = index_to_symbol_map[abs(index)]
result_dict[symbol_name] = index > 0
return result_dict
def _to_picosat_clauses_assumptions_and_symbol_mappings(self):
"""Return a PicoSAT-compatible representation and helpful metadata."""
cnf_tree = self.tree if self.is_cnf else self.tree.to_cnf()
index = 1
symbol_to_index_map = {}
index_to_symbol_map = {}
clauses = []
assumptions = []
for clause_root in cnf_tree.iter_cnf_clauses():
clause_indices = []
for node in clause_root.iter_dnf_clauses():
is_negated = isinstance(node, UnaryOperatorExpressionTreeNode)
symbol_str = (node.l_child.symbol_name if is_negated else
node.symbol_name)
if symbol_str in symbol_to_index_map:
pos = symbol_to_index_map[symbol_str]
if is_negated:
clause_indices.append(-pos)
else:
clause_indices.append(pos)
elif symbol_str == '0':
clause_indices.append(index)
if is_negated:
assumptions.append(index)
else:
assumptions.append(-index)
index += 1
elif symbol_str == '1':
clause_indices.append(index)
if is_negated:
assumptions.append(-index)
else:
assumptions.append(index)
index += 1
else:
symbol_to_index_map[symbol_str] = index
index_to_symbol_map[index] = symbol_str
if is_negated:
clause_indices.append(-index)
else:
clause_indices.append(index)
index += 1
clauses.append(clause_indices)
for symbol_str, assumed_val in self._constraints.items():
index = symbol_to_index_map[symbol_str]
if assumed_val:
assumptions.append(index)
else:
assumptions.append(-index)
return clauses, assumptions, symbol_to_index_map, index_to_symbol_map
[docs] def evaluate(self, **kwargs):
"""Evaluate the Boolean expression for the passed keyword arguments.
This is a checked wrapper around the :func:`evaluate_unchecked`
function.
:param kwargs: Keys are names of symbols in this expression; the
specified value for each of these keys will be substituted into the
expression for evaluation.
:returns: The result of evaluating the expression.
:rtype: :class:`bool <python:bool>`
:raises ExtraSymbolError: If a symbol not in this expression is passed
through ``kwargs``.
:raises MissingSymbolError: If any symbols in this expression are not
passed through ``kwargs``.
:raises InvalidBooleanValueError: If any values from ``kwargs`` are not
valid Boolean inputs.
:raises InvalidIdentifierError: If any symbol names are invalid
identifiers.
Usage::
>>> from tt import BooleanExpression
>>> b = BooleanExpression('A or B')
>>> b.evaluate(A=0, B=0)
False
>>> b.evaluate(A=1, B=0)
True
"""
assert_all_valid_keys(kwargs, self._symbol_set)
assert_iterable_contains_all_expr_symbols(
kwargs.keys(), self._symbol_set)
return self.evaluate_unchecked(**kwargs)
[docs] def evaluate_unchecked(self, **kwargs):
"""Evaluate the Boolean expression without checking the input.
This is used for evaluation by the :func:`evaluate` method, which
validates the input ``kwargs`` before passing them to this method.
:param kwargs: Keys are names of symbols in this expression; the
specified value for each of these keys will be substituted into the
expression for evaluation.
:returns: The Boolean result of evaluating the expression.
:rtype: :class:`bool <python:bool>`
"""
truthy = self._tree.evaluate(kwargs)
return bool(truthy)
[docs] def iter_clauses(self):
"""Iterate over the clauses in this expression.
An expression must be in conjunctive normal form (CNF) or disjunctive
normal form (DNF) in order to iterate over its clauses. Here's a simple
example::
>>> from tt import BooleanExpression
>>> b = BooleanExpression('(~A or B) and (C or D) and (~E or ~F)')
>>> for clause in b.iter_clauses():
... clause
...
<BooleanExpression "~A or B">
<BooleanExpression "C or D">
<BooleanExpression "~E or ~F">
In the case of an ambiguous expression form (between CNF and DNF), the
clauses will be interpreted to be in CNF form. For example::
>>> b = BooleanExpression('A and ~B and C')
>>> b.is_cnf
True
>>> b.is_dnf
True
>>> print(', '.join(str(clause) for clause in b.iter_clauses()))
A, ~B, C
If you want to enforce a specific CNF or DNF interpretation of the
clauses, take a look at :func:`iter_cnf_clauses` and
:func:`iter_dnf_clauses`.
:returns: An iterator of expression objects, each representing a
separate clause of this expression.
:rtype: Iterator[:class:`BooleanExpression`]
:raises RequiresNormalFormError: If this expression is not in
conjunctive or disjunctive normal form.
"""
for node in self._tree.iter_clauses():
yield BooleanExpression(node)
[docs] def iter_cnf_clauses(self):
"""Iterate over the CNF clauses in this expression.
.. code-block:: python
>>> from tt import BooleanExpression
>>> b = BooleanExpression('(A or B) and ~C')
>>> for clause in b.iter_cnf_clauses():
... print(clause)
...
A or B
~C
:returns: An iterator of expression objects, each representing a
separate CNF clause of this expression.
:rtype: Iterator[:class:`BooleanExpression`]
:raises RequiresNormalFormError: If this expression is not in
conjunctive normal form.
"""
for node in self._tree.iter_cnf_clauses():
yield BooleanExpression(node)
[docs] def iter_dnf_clauses(self):
"""Iterate over the DNF clauses in this expression.
.. code-block:: python
>>> from tt import BooleanExpression
>>> b = BooleanExpression('(A and ~B) or (C and D and E)')
>>> for clause in b.iter_dnf_clauses():
... print(clause)
...
A and ~B
C and D and E
:returns: An iterator of expression objects, each representing a
separate DNF clause of this expression.
:rtype: Iterator[:class:`BooleanExpression`]
:raises RequiresNormalFormError: If this expression is not in
disjunctive normal form.
"""
for node in self._tree.iter_dnf_clauses():
yield BooleanExpression(node)
def _tokenize(self):
"""Make the first pass through the expression, tokenizing it.
This method is a helper for initializing an expression object from a
string and will populate the ``_symbols``, ``_symbol_set``, and
``_tokens`` attributes of this object.
:raises GrammarError: If a malformed expression is received.
"""
operator_strs = [k for k in OPERATOR_MAPPING.keys()]
is_symbolic = {op: not op[0].isalpha() for op in operator_strs}
operator_search_list = sorted(operator_strs, key=len, reverse=True)
delimiters = DELIMITERS | set(k[0] for k, v in is_symbolic.items()
if v)
EXPECTING_OPERAND = 1
EXPECTING_OPERATOR = 2
grammar_state = EXPECTING_OPERAND
idx = 0
open_paren_count = 0
num_chars = len(self._raw_expr)
while idx < num_chars:
c = self._raw_expr[idx].strip()
if not c:
# do nothing
idx += 1
elif c == '(':
if grammar_state != EXPECTING_OPERAND:
raise BadParenPositionError('Unexpected parenthesis',
self._raw_expr, idx)
open_paren_count += 1
self._tokens.append(c)
idx += 1
elif c == ')':
if grammar_state != EXPECTING_OPERATOR:
raise BadParenPositionError('Unexpected parenthesis',
self._raw_expr, idx)
elif not open_paren_count:
raise UnbalancedParenError('Unbalanced parenthesis',
self._raw_expr, idx)
open_paren_count -= 1
self._tokens.append(c)
idx += 1
else:
is_operator = False
num_chars_remaining = num_chars - idx
matching_operators = [
operator for operator in operator_search_list
if len(operator) <= num_chars_remaining and
self._raw_expr[idx:(idx+len(operator))] == operator]
if matching_operators:
match = matching_operators[0]
match_length = len(match)
next_c_pos = idx + match_length
next_c = (None if next_c_pos >= num_chars else
self._raw_expr[idx + match_length])
if next_c is None:
# trailing operator
raise ExpressionOrderError(
'Unexpected operator "{}"'.format(match),
self._raw_expr, idx)
if next_c in delimiters or is_symbolic[match]:
if OPERATOR_MAPPING[match] == TT_NOT_OP:
if grammar_state != EXPECTING_OPERAND:
raise ExpressionOrderError(
'Unexpected unary operator "{}"'.format(
match), self._raw_expr, idx)
else:
if grammar_state != EXPECTING_OPERATOR:
raise ExpressionOrderError(
'Unexpected binary operator "{}"'.format(
match), self._raw_expr, idx)
grammar_state = EXPECTING_OPERAND
is_operator = True
self._tokens.append(match)
idx += match_length
if not is_operator:
if grammar_state != EXPECTING_OPERAND:
raise ExpressionOrderError('Unexpected operand',
self._raw_expr, idx)
operand_end_idx = idx + 1
while (operand_end_idx < num_chars and
self._raw_expr[operand_end_idx] not in delimiters):
operand_end_idx += 1
operand = self._raw_expr[idx:operand_end_idx]
if (operand not in CONSTANT_VALUES and
not is_valid_identifier(operand)):
raise InvalidIdentifierError(
'Invalid operand name "{}"'.format(operand),
self._raw_expr, idx)
self._tokens.append(operand)
if operand not in self._symbol_set:
self._symbols.append(operand)
self._symbol_set.add(operand)
idx = operand_end_idx
grammar_state = EXPECTING_OPERATOR
if open_paren_count:
left_paren_positions = [m.start() for m in
re.finditer(r'\(', self._raw_expr)]
raise UnbalancedParenError(
'Unbalanced left parenthesis', self._raw_expr,
left_paren_positions[open_paren_count-1])
if not self._tokens:
raise EmptyExpressionError('Empty expression is invalid')
def _to_postfix(self):
"""Populate the ``_postfix_tokens`` attribute."""
stack = []
for token in self._tokens:
if token in self._symbol_set:
self._postfix_tokens.append(token)
elif token == '(':
stack.append(token)
elif token in OPERATOR_MAPPING.keys():
if not stack:
stack.append(token)
else:
while (stack and stack[-1] != '(' and
OPERATOR_MAPPING[stack[-1]].precedence >
OPERATOR_MAPPING[token].precedence):
self._postfix_tokens.append(stack.pop())
stack.append(token)
elif token == ')':
while stack and stack[-1] != '(':
self._postfix_tokens.append(stack.pop())
stack.pop()
for token in reversed(stack):
self._postfix_tokens.append(token)
@contextmanager
def _symbol_set_includes_constant_values(self):
"""Context manager to include CONSTANT_VALUES in _symbol_set."""
self._symbol_set |= CONSTANT_VALUES
yield
self._symbol_set -= CONSTANT_VALUES