In computer science, an AST, or just syntax tree, is a tree representation of the abstract (simplified) syntactic structure of the source code. Each node of the tree denotes a construct of the programming language under consideration. In our expression evaluator, the nodes are numeric values (IEEE 754 floating points), binary operators, unary operators, trigonometric functions, and a variable.

The syntax is abstract in the sense that it does not represent every detail that appears in the real syntax. For instance, grouping parentheses is implicit in the tree structure, and AST data structure discards parentheses. Before we model the AST, let us see some expressions and its AST representations:

    // AST for 5*10 
    Exp e = new BinaryExp( 
    new NumericConstant(5), 
    new NumericConstant(10), 
    OPERATOR.MUL); 

The preceding example uses two node types, that is, NumericConstant, BinaryExp. Even the simplest expression creates a structure which seems a bit complicated.

Let us look at an expression which has a unary operator as well:

    // AST for -(10+(30+50)) 
    Exp e = new UnaryExp( 
      new BinaryExp( 
        new NumericConstant(10), 
        new BinaryExp( 
          new NumericConstant(30), 
          new NumericConstant(50), 
        OPERATOR.PLUS), 
      OPERATOR.PLUS) 
    ,OPERATOR.MINUS); 

Since our expression evaluator only supports a single variable, we create a context class which will store the variable in question. The class is named RUNTIME_CONTEXT, and the whole listing is given as follows:

    public class RUNTIME_CONTEXT 
    { 
      private double _t = 0 ; 
      public RUNTIME_CONTEXT(){ } 
      public double T { 
        get { return _t; } 
        set { _t = value; } 
      } 
    } 

In any programming language, expression is what you evaluate for its value. This can be modeled as an abstract class. The numeric value which we support is of the type IEEE 754 double precision floating point:

    abstract class Exp{ 
      public abstract double Evaluate(RUNTIME_CONTEXT cont);
    } 

The expression evaluator supports operators like PLUS (+), MINUS (-), DIV (/), and MUL (*). They are modeled using an enumerated type named OPERATOR:

    public enum OPERATOR{ 
      ILLEGAL = -1,PLUS, MINUS, DIV, MUL 
    } 

We will start by creating a hierarchy of nodes for modeling an expression. We use the composite pattern to compose bigger expressions out of smaller ones:

    class Exp // Base class for Expression 
    class NumericConstant // Numeric Value 
    class BinaryExp // Binary Expression 
    class UnaryExp // Unary Expression 
    class SineExp // Trig fn 
    class SineExp // Trig 
    class Var // psuedo variable $t 

The NumericConstant class can store an IEEE 754 double precision floating point value in it. This is a leaf node in the AST:

    public class NumericConstant : Exp 
    { 
      private double _value; 
      public NumericConstant(double value){ _value = value;} 
 
      public override double Evaluate(RUNTIME_CONTEXT cont) 
      { return _value;} 
    } 

The BinaryExp class models a binary expression which takes two expressions (ex1 for the left node and ex2 for the right node), it applies the operator on both, the left-side value and the right-side value, inside the evaluate routine:

    public class BinaryExp : Exp 
    { 
      private Exp _ex1, _ex2; 
      private OPERATOR _op; 
 
      public BinaryExp(Exp a, Exp b, OPERATOR op) 
      { _ex1 = a; _ex2 = b; _op = op; } 
 
      public override double Evaluate(RUNTIME_CONTEXT cont) 
      { 
        switch (_op) 
        { 
          case OPERATOR.PLUS: 
            return _ex1.Evaluate(cont) + _ex2.Evaluate(cont); 
          case OPERATOR.MINUS: 
            return _ex1.Evaluate(cont) - _ex2.Evaluate(cont); 
          case OPERATOR.DIV: 
            return _ex1.Evaluate(cont) / _ex2.Evaluate(cont); 
          case OPERATOR.MUL: 
            return _ex1.Evaluate(cont) * _ex2.Evaluate(cont); 
        } 
        return Double.NaN; 
      } 
    } 

In the case of unary expressions, we take an operator and an Exp node as a child:

    public class UnaryExp : Exp 
    { 
      private Exp _ex1; 
      private OPERATOR _op; 
      public UnaryExp(Exp a, OPERATOR op) 
      {_ex1 = a;_op = op } 
      public override double Evaluate(RUNTIME_CONTEXT cont) 
      { 
        switch (_op) 
        { 
          case OPERATOR.PLUS: 
          return _ex1.Evaluate(cont); 
          case OPERATOR.MINUS: 
          return -_ex1.Evaluate(cont); 
        } 
        return Double.NaN; 
      } 
    } 

The sine node takes an expression as a child. We evaluate _ex1, and invoke Math.Sin on the resulting value:

    class SineExp : Exp 
    { 
      private Exp _ex1; 
      public SineExp(Exp a) 
      { _ex1 = a; } 
      public override double Evaluate(RUNTIME_CONTEXT cont){ 
        double val = _ex1.Evaluate(cont); 
        return Math.Sin(val); 
      } 
    } 

The cosine node takes an expression as a child. We evaluate _ex1, and invoke Math.Cos on the resulting value:

    class CosExp : Exp 
    { 
      private Exp _ex1; 
      public CosExp(Exp a) 
      { _ex1 = a;} 
      public override double Evaluate(RUNTIME_CONTEXT cont){ 
        double val = _ex1.Evaluate(cont); 
        return Math.Cos(val); 
      } 
    } 

And finally, the variables ($t) are modeled as follows:

    class Var : Exp 
    { 
      public Var(){} 
      public override double Evaluate(RUNTIME_CONTEXT cont){ 
        return cont.T; 
      } 
    }