# Expression Trees¶

Most generic interface to represent a mathematical expression in Diofant is a tree. Let us take the expression

```
>>> x*y + x**2
2
x + x⋅y
```

We can see what this expression looks like internally by using `repr()`

```
>>> repr(_)
"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 also could use

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

Note

The arguments of `Add`

and the commutative
arguments of `Mul`

are stored in an 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, using a very
generic interface — attributes `func`

and
`args`

.

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

attribute

```
>>> expr = 2 + x*y; expr
x⋅y + 2
>>> expr.func
<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 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)
```

Note

Every expression with non-empty `args`

can
be reconstructed, using

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

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

```
>>> tuple(preorder_traversal(expr))
(x⋅y + 2, 2, x⋅y, x, y)
>>> tuple(postorder_traversal(expr))
(2, x, y, x⋅y, x⋅y + 2)
```