Fix for logic bug in expression code

expression-fixed.py

#!/usr/bin/env python3

class Expression:
    OPERATORS = ['+', '-']

    @staticmethod
    def parse(expression):
        # If it is a leaf-expression return even a leaf:
        if len(expression) == 1:
            return Expression(int(expression[0]), None, None)

        # We may implement some validation check if the input is not validated
        # enough. We may also check if the input operators are in
        # Expression.OPERATORS..

        l, r = Expression.parse(expression[:-2]), Expression.parse(expression[-1])
        return Expression(expression[-2], l, r)

    def __init__(self, value, left, right):
        """
        value, left and right may be any object. In this implementation
        we use string for operators and integer for values but this may vary
        for future purposes. It is important that the given objects implement
        all used operators (in evaluate()).
        """

        self.value, self.left, self.right = value, left, right

    def is_leaf(self):
        """
        This function returns true only if the expression does not have
        any successor.
        """

        return self.left == None and self.right == None

    def evaluate(self):
        if self.is_leaf():
            return self.value

        if self.value == '+':
            return self.left.evaluate() + self.right.evaluate()

        if self.value == '-':
            return self.left.evaluate() - self.right.evaluate()

    def __str__(self):
        if self.is_leaf():
            return str(self.value)
        return str(self.left) + self.value + str(self.right)

    def balance(self):
        raise NotImplementedError


def main():
    expr = Expression.parse("1+2-3+4")
    print(expr)
    print(expr.evaluate())

if __name__ == "__main__":
    main()

The change is: The underlying tree structure is rather strong leftist than leaning to the right as before.

This is an obious solution in theory for the problem of contemt of the distributive rule. In a leftist tree the length of the right subtree of every node has a maximum length of 1. That means every node that is a right-subtree of some parents node is a leaf. Therefore the distributive rule can't be broken.

Another fix would be the evaluation of some x-y expression that gets evolved to x + (-y)

An invalid fix (imho!) would be the left-side-traversal of the constructed tree, because with that concept we would ignore brackets in general and do some flaws in the other direction.