Binary Expression Tree

BinaryExpressionTree (BinaryTree)

A binary expression tree is a binary tree used to parse mathematical expressions. Operators are contained within the internal nodes of the tree, whereas the operands occupy the leaves. By using such a parse tree, complex mathematical expressions with numerous operators and operands can be easily evaluated, as the expression is divided into smaller parts made up of only two operands and a single operator.

Instantiate a binary expression tree object

>>> tree = BinaryExpressionTree()

Evaluate expressions, when tree parsing is based on infix notation

>>> tree.evaluate("(2+2-23)", BinaryExpressionTree.Notation.Infix)
-19.0
>>> tree.evaluate("((434+42-2)*(43+4-2))", BinaryExpressionTree.Notation.Infix)
21330.0

Evaluate expressions, when tree parsing is based on prefix notation

>>> tree.evaluate("(2+2-23)", BinaryExpressionTree.Notation.Prefix)
-19.0
>>> tree.evaluate("((434+42-2)*(43+4-2))", BinaryExpressionTree.Notation.Prefix)
21330.0

Evaluate expressions, when tree parsing is based on postfix notation

>>> tree.evaluate("(2+2-23)", BinaryExpressionTree.Notation.Postfix)
-19.0
>>> tree.evaluate("((434+42-2)*(43+4-2))", BinaryExpressionTree.Notation.Postfix)
21330.0

Notation (Enum)

An enumeration.

evaluate(self, expression, notation=<Notation.Infix: 1>)

Return the solution to a mathematical expression

Parameters:

Name	Type	Description	Default
expression	str	the expression to be solved	required
notation	Notation	the notation to use when building the parse tree	<Notation.Infix: 1>

Returns:

Type	Description
float	the solution to the passed expression

Source code in trees/binary_expression_tree.py

def evaluate(self, expression: str, notation: Notation = Notation.Infix) -> float:
    """Return the solution to a mathematical expression

    :param expression: the expression to be solved
    :param notation: the notation to use when building the parse tree
    :returns: the solution to the passed expression
    """

    def evaluate_helper(node: BinaryTree._Node):
        try:
            if node.children == [None, None]:
                return float(node.key)
        except AttributeError:
            raise SyntaxError

        left_result = evaluate_helper(node.children[0])
        right_result = evaluate_helper(node.children[1])
        operator = node.key

        if operator == "+":
            return left_result + right_result
        elif operator == "-":
            return left_result - right_result
        elif operator == "*":
            return left_result * right_result
        elif operator == "/":
            return left_result / right_result
        else:
            raise ValueError(f"'{operator}' is not a valid operator")

    self.__refresh()
    self.__parse(expression, notation)

    if self.is_empty():
        return 0.0
    else:
        return evaluate_helper(self._root)

insert(self, data, _=None)

Insert a value into the tree. Operators and operands inserted need to follow the infix notation when using this method.

Parameters:

Name	Type	Description	Default
data	str	item to be added to the tree	required
_		this parameter is not used, and is thus ignored	None

Source code in trees/binary_expression_tree.py

def insert(self, data: str, _=None) -> None:
    """Insert a value into the tree. Operators and operands inserted need to follow the infix notation when using
    this method.

    :param data: item to be added to the tree
    :param _: this parameter is not used, and is thus ignored
    """
    self.__insert_infix(data)