Expression Trees

Mathematical expressions can be depicted graphically via expression trees that show the structure of the terms in an expression. For example, the algebraic expression

x + 4 (x + 2)

can be represented by the expression tree below.

We can replicate this structure in Python through the use of objects. Each node in the expression tree will be represented by an object. If a node has other nodes connected to it, those child nodes will be stored as member variables in the object representing that node. For example, the object representing an addition operation would have two member variables left and right that store the two operands for the addition operation.

An expression tree is useful for evaluating the expression it represents. To do this, we equip each node in the structure with an evaluate(x) function that will evaluate that node given a value for x. Nodes that contain other nodes as member variables will do the evaluation by first calling evaluate() on the nodes below the node in the structure and then performing the appropriate arithmetic on the results that come back. For example, here is the code for the evaluate() method in the object that represents an addition:

def evaluate(self,x):
    a = self.left.evaluate(x)
    b = self.right.evaluate(x)
    return a + b

Programming assignment

Construct a set of classes that can represent the various node types you would encounter in the expression tree depicted above. You will need classes for the following kinds of nodes:

• Numbers
• x-nodes
• Addition
• Multiplication

Equip each class with an appropriate __init__ method and a version of the evaluate(x) method.

Once you have written the code for these classes, write a test program that assembles the expresion tree shown above and then evaluates that expression tree at x = 2 and x = 3 and prints the results of those two evaluations.

Due date

This assignment is due by the start of class on Thursday, Oct. 12