# Expression Trees¶

In this section, we discuss some ways that we can perform advanced manipulation of expressions.

Most generic interface to represent a mathematical expression in Diofant is a
tree. Let us take the expression \(x y + x^2\). We can see what this expression
looks like internally by using `repr()`

```
>>> repr(x*y + x**2)
"Add(Pow(Symbol('x'), Integer(2)), Mul(Symbol('x'), Symbol('y')))"
```

The easiest way to tear this apart is to look at a diagram of the expression tree:

First, let’s look at the leaves of this tree. We got here instances
of the `Symbol`

class and the Diofant
version of integers, instance of the
`Integer`

class, even technically we
input integer literal `2`

.

What about `x*y`

? As we might expect, this is the multiplication of
`x`

and `y`

. The Diofant class for multiplication is
`Mul`

.

```
>>> repr(x*y)
"Mul(Symbol('x'), Symbol('y'))"
```

Thus, we could have created the same object by writing

```
>>> Mul(x, y)
x⋅y
```

When we write `x**2`

, this creates a
`Pow`

class instance.

```
>>> repr(x**2)
"Pow(Symbol('x'), Integer(2))"
```

We could have created the same object by calling

```
>>> Pow(x, 2)
2
x
```

Now we get to our final expression, `x*y + x**2`

. This is the
addition of our last two objects. The Diofant class for addition is
`Add`

, so, as you might expect, to create
this object, we could use

```
>>> Add(Pow(x, 2), Mul(x, y))
2
x + x⋅y
>>> x*y + x**2
2
x + x⋅y
```

Note

You may have noticed that the order we entered our expression and
the order that it came out from printers like `repr()`

or in
the graph were different. This because the arguments
of `Add`

and the commutative arguments of
`Mul`

are stored in an arbitrary (but
consistent!) order, which is independent of the order inputted.

There is no subtraction class. `x - y`

is represented as
`x + (-1)*y`

```
>>> repr(x - y)
"Add(Symbol('x'), Mul(Integer(-1), Symbol('y')))"
```

Similarly to subtraction, there is no division class.

```
>>> repr(x/y)
"Mul(Symbol('x'), Pow(Symbol('y'), Integer(-1)))"
```

We see that `x/y`

is represented as `x*y**(-1)`

.

But what about `x/2`

? Following the pattern of the previous
example, we might expect to see `Mul(x, Pow(Integer(2), -1))`

. But
instead, we have

```
>>> repr(x/2)
"Mul(Rational(1, 2), Symbol('x'))"
```

Rational numbers are always combined into a single term in a multiplication, so that when we divide by 2, it is represented as multiplying by 1/2.

## Walking the Tree¶

Let’s look at how to dig our way through an expression tree. For this
every object in Diofant has a very generic interface — two important
attributes, `func`

, and
`args`

.

The head of the object is encoded in the
`func`

attribute. Usually it is the
same as the class of the object, but not always.

```
>>> expr = 2 + x*y
>>> expr
x⋅y + 2
>>> expr.func
<class 'diofant.core.add.Add'>
>>> type(expr)
<class 'diofant.core.add.Add'>
```

The class of an object need not be the same as the one used to create it.

```
>>> Add(x, x)
2⋅x
>>> _.func
<class 'diofant.core.mul.Mul'>
```

Note

Diofant classes make heavy use of the `__new__()`

class
constructor, which, unlike `__init__()`

, allows a
different class to be returned from the constructor.

The children of a node in the tree are held in the
`args`

attribute.

```
>>> expr.args
(2, x⋅y)
```

From this, we can see `expr`

can be completely reconstructed from
its `func`

and its
`args`

.

```
>>> expr.func(*expr.args)
x⋅y + 2
```

Note

Every well-formed expression must either have empty
`args`

or satisfy invariant

```
>>> expr == expr.func(*expr.args)
True
```

Empty `args`

signal that
we have hit a leaf of the expression tree.

```
>>> x.args
()
>>> Integer(2).args
()
```

This interface allows us to write recursive generators that walk expression trees either in post-order or pre-order fashion.

```
>>> expr = x*y + 2
>>> for term in preorder_traversal(expr):
... print(term)
x*y + 2
2
x*y
x
y
```