expression tree

express.py

from abc import ABC


class Node:

    def __init__(self, data):
        self.data = data
        self.left = self.right = None

    def __str__(self):
        return str(self.data)


class Operator(ABC):

    def evaluate(self, stack):
        pass

    def sign(self):
        pass


class Plus(Operator):

    def evaluate(self, stack):
        stack.append(stack.pop() + stack.pop())

    def sign(self):
        return "+"


class BinaryTree:

    def __init__(self, expression):
        """Construct bin tree."""
        self.root = Node(expression.pop())
        self.expression = expression
        self._build_subtree(self.root, self.expression)
        self.operators = [Plus()]

    def _build_subtree(self, node, stack):
        """Build subtree."""
        if node is None or not stack:
            return

        top = Node(stack.pop())

        if node.left is None:
            node.left = top

        self._build_subtree(top, stack)

        if node.right is None:
            node.right = top

    def get_operator(self, sign):
        for operator in self.operators:
            if operator.sign() == sign:
                return operator

    def eval(self):
        """Public interface ..."""
        stack = []
        self._evaluate(self.root, stack)
        return stack.pop()

    def _evaluate(self, node, result):
        """Recursive evaluation of the tree."""
        if node is None:
            return

        self._evaluate(node.left, result)
        self._evaluate(node.right, result)

        op = self.get_operator(node.data)
        if op:
            op.evaluate(result)
        else:
            result.append(float(node.data))