expressions

Tools for working with Boolean expressions.

expressions.bexpr module

Tools for interacting with Boolean expressions.

class tt.expressions.bexpr.BooleanExpression(expr)

Bases: 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 BooleanExpressionTree laying around, you can make a new expression object from that, too:

>>> from tt import BooleanExpressionTree
>>> tree = BooleanExpressionTree(
...     ['A', 'B', 'or',
...      'C', 'D', 'and',
...      'iff'])
>>> BooleanExpression(tree)
<BooleanExpression "(A or B) iff (C and D)">

Additionally, any 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

Parameters:

expr (str, BooleanExpressionTree, or ExpressionTreeNode) – The expression representation from which this object is derived.

Raises:

• BadParenPositionError – If the passed expression contains a parenthesis in an invalid position.
• EmptyExpressionError – If the passed expressions contains nothing other than whitespace.
• ExpressionOrderError – If the expression contains invalid consecutive operators or operands.
• InvalidArgumentTypeError – If expr is not an acceptable type.
• InvalidIdentifierError – If any parsed variable symbols in the expression are invalid identifiers.
• UnbalancedParenError – If any parenthesis pairs remain unbalanced.

It is important to note that aside from InvalidArgumentTypeError, all exceptions raised in expression initialization will be descendants of GrammarError.

evaluate(**kwargs)

Evaluate the Boolean expression for the passed keyword arguments.

This is a checked wrapper around the evaluate_unchecked() function.

Parameters:

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.

Return type:

bool

Raises:

• ExtraSymbolError – If a symbol not in this expression is passed through kwargs.
• MissingSymbolError – If any symbols in this expression are not passed through kwargs.
• InvalidBooleanValueError – If any values from kwargs are not valid Boolean inputs.
• 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

evaluate_unchecked(**kwargs)

Evaluate the Boolean expression without checking the input.

This is used for evaluation by the evaluate() method, which validates the input kwargs before passing them to this method.

Parameters: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. Return type:bool

is_cnf

Whether this expression is in conjunctive norma form or not.

Type:bool

>>> 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

is_dnf

Whether this expression is in conjunctive normal form or not.

Type:bool

>>> 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

iter_clauses()

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 iter_cnf_clauses() and iter_dnf_clauses().

Returns:An iterator of expression objects, each representing a separate clause of this expression. Return type:Iterator[BooleanExpression] Raises:RequiresNormalFormError – If this expression is not in conjunctive or disjunctive normal form.

iter_cnf_clauses()

Iterate over the CNF clauses in this expression.

>>> 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. Return type:Iterator[BooleanExpression] Raises:RequiresNormalFormError – If this expression is not in conjunctive normal form.

iter_dnf_clauses()

Iterate over the DNF clauses in this expression.

>>> 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. Return type:Iterator[BooleanExpression] Raises:RequiresNormalFormError – If this expression is not in disjunctive normal form.

postfix_tokens

Similar to the tokens attribute, but in postfix order.

Type:List[str]

>>> from tt import BooleanExpression
>>> b = BooleanExpression('A xor (B or C)')
>>> b.postfix_tokens
['A', 'B', 'C', 'or', 'xor']

raw_expr

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:str

>>> from tt import BooleanExpression
>>> b = BooleanExpression('A nand B')
>>> b.raw_expr
'A nand B'

symbols

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[str]

>>> from tt import BooleanExpression
>>> b = BooleanExpression('A xor (B or C)')
>>> b.symbols
['A', 'B', 'C']

tokens

The parsed, non-whitespace tokens of an expression.

Type:List[str]

>>> from tt import BooleanExpression
>>> b = BooleanExpression('A xor (B or C)')
>>> b.tokens
['A', 'xor', '(', 'B', 'or', 'C', ')']

tree

The expression tree representing this Boolean expression.

Type:BooleanExpressionTree

>>> from tt import BooleanExpression
>>> b = BooleanExpression('A xor (B or C)')
>>> print(b.tree)
xor
`----A
`----or
     `----B
     `----C