Making a Math Interpreter: AST
Tags: algorithms, csharp
Published: 2021-09-21 13:50:32

---
title: Making a Math Interpreter: AST
published: true
series: Making a Math Interpreter using C#
description: Adding AST
tags: algorithms, csharp
cover_image: https://dev-to-uploads.s3.amazonaws.com/uploads/articles/2um78ah24581l3l3ll1s.jpg
---
#### Resources
- Find the Github link [here](https://github.com/j0nimost/calcy)

## AST
We now need to define a structure which our interpreter will use to store and **evaluate** the mathematical expressions. In our case we will form a **Bottom-Up Evaluation** more details when we get to `Parsing` in the next chapter.

If you can recall our ast structure in [Part 1](https://dev.to/j0nimost/implementing-a-math-interpreter-using-c-part1-2mf)
![AST TREE](https://dev-to-uploads.s3.amazonaws.com/uploads/articles/e8986cg077v4t91ygnxd.png)

We're going to form an AST structure of the following form
```
  ASTPlus(Leaf(2),
                  ASTMult(Leaf(5), Leaf(4)))
```
Simply to put it, our AST will have Leaf Nodes which will hold numeric value, `ASTPlus` and `ASTMult` will hold objects of type Leaf Node or Other ASTs.

### Init
Let's start by creating a class, let's call it: `AST.cs`.

We can go ahead and make the class generated an Abstract class, then lets add an abstract method `Eval` which will allow us to recursively evaluate expressions

```csharp
    public abstract class AST
    {
        public abstract decimal Eval();
    }
```

Now right below this class lets define a leaf node which inherits from AST abstract class and implements the abstract method.

We also know our leaf nodes will only hold numerical values so we can design the class like so.

```csharp
    public class ASTLeaf : AST
    {
        public readonly decimal _num;
        public ASTLeaf(decimal num)
        {
            this._num = num;
        }
        public override decimal Eval()
        {
            return this._num;
        }

        public override string ToString()
        {
            return this._num.ToString();
        }
    }
```

Lets create another class right below this ASTLeaf and call it ASTPlus. It will hold the addition objects.
```csharp
    public class ASTPlus : AST
    {
        public readonly AST _leftNode;
        public readonly AST _rightNode;

        public ASTPlus(AST leftNode, AST rightNode)
        {
            this._leftNode = leftNode;
            this._rightNode = rightNode;
        }
        public override decimal Eval()
        {
            // Perform the evaluation
            return this._leftNode.Eval() + this._rightNode.Eval();
        }

        public override string ToString()
        {
            return String.Format("({0} + {1})", this._leftNode.ToString(), this._rightNode.ToString());
        }
    }
```
In our class `ASTPlus` we are taking in two AST objects, this could be any class. Implementing it in this approach allows us to implicitly have any class as long as it implements AST.

Our Eval method returns the sum of the evaluations of the AST objects. So, this means be it `ASTMinus` or `ASTLeaf` we will be calling the Eval method from the class objects first before we sum them up in `ASTPlus`

We have added the `ToString` method override, this will allow us to view the evaluation heirachy.

The same class structure goes for ASTMinus, ASTMultiply and ASTDivide. Just remember to change the operation sign in the `Eval`and `ToString` methods.

So our final `AST.cs` class will look like so.
```csharp

    public abstract class AST
    {
        public abstract decimal Eval();
    }

    public class ASTLeaf : AST
    {
        public readonly decimal _num;
        public ASTLeaf(decimal num)
        {
            this._num = num;
        }
        public override decimal Eval()
        {
            return this._num;
        }

        public override string ToString()
        {
            return this._num.ToString();
        }
    }

    public class ASTPlus : AST
    {
        public readonly AST _leftNode;
        public readonly AST _rightNode;

        public ASTPlus(AST leftNode, AST rightNode)
        {
            this._leftNode = leftNode;
            this._rightNode = rightNode;
        }
        public override decimal Eval()
        {
            // Perform the evaluation
            return this._leftNode.Eval() + this._rightNode.Eval();
        }

        public override string ToString()
        {
            return String.Format("({0} + {1})", this._leftNode.ToString(), this._rightNode.ToString());
        }
    }

    public class ASTMinus : AST
    {
        public readonly AST _leftNode;
        public readonly AST _rightNode;

        public ASTMinus(AST leftNode, AST rightNode)
        {
            this._leftNode = leftNode;
            this._rightNode = rightNode;
        }
        public override decimal Eval()
        {
            return this._leftNode.Eval() - this._rightNode.Eval();
        }
        public override string ToString()
        {
            return String.Format("({0} - {1})", this._leftNode.ToString(), this._rightNode.ToString());
        }
    }

    public class ASTMultiply : AST
    {
        public readonly AST _leftNode;
        public readonly AST _rightNode;

        public ASTMultiply(AST leftNode, AST rightNode)
        {
            this._leftNode = leftNode;
            this._rightNode = rightNode;
        }
        public override decimal Eval()
        {
            return this._leftNode.Eval() * this._rightNode.Eval();
        }

        public override string ToString()
        {
            return String.Format("({0} * {1})", this._leftNode.ToString(), this._rightNode.ToString());
        }
    }
    public class ASTDivide : AST
    {
        public readonly AST _leftNode;
        public readonly AST _rightNode;

        public ASTDivide(AST leftNode, AST rightNode)
        {
            this._leftNode = leftNode;
            this._rightNode = rightNode;
        }
        public override decimal Eval()
        {
            return this._leftNode.Eval() / this._rightNode.Eval();
        }

        public override string ToString()
        {
            return String.Format("({0} / {1})", this._leftNode.ToString(), this._rightNode.ToString());
        }
    }
```

So now we have an AST structure that will hold our expressions.
In the next chapter we are going to;
 - Create a Parser -> Expression, Factor and Term
 - Implement Eval
 - Write Tests