Evaluate Expressions – Part 4: Evaluate the Abstract Syntax Tree

Evaluate Expressions – Part 1: The Approaches
Evaluate Expressions – Part 2: Parse the Expression
Evaluate Expressions – Part 3: Building the Abstract Syntax Tree
Evaluate Expressions – Part 4: Evaluate the Abstract Syntax Tree

So far we have managed to parse the text representing an expression and build an abstract syntax tree. The only thing left, and the simplest of them all, is traversing this abstract syntax tree and evaluating the expression is represents.

In pseudo code, this would look like this:

double Evaluate(subtree)
{
   if(subtree is numeric)
      return value;
   else
   {
      op = subtree.operator
      v1 = Evaluate(subtree.left)
      v2 = Evaluate(subtree.right)
      return v1 op v2;
   }
}

We actually have to check for one more type of node, the one representing an unary expression. However, the evaluation function is as simple as this:

class Evaluator 
{
   double EvaluateSubtree(ASTNode* ast)
   {
      if(ast == NULL) 
         throw EvaluatorException("Incorrect syntax tree!");

      if(ast->Type == NumberValue)
         return ast->Value;
      else if(ast->Type == UnaryMinus)
         return -EvaluateSubtree(ast->Left);
      else 
      {
         double v1 = EvaluateSubtree(ast->Left);
         double v2 = EvaluateSubtree(ast->Right);
         switch(ast->Type)
         {
         case OperatorPlus:  return v1 + v2;
         case OperatorMinus: return v1 - v2;
         case OperatorMul:   return v1 * v2;
         case OperatorDiv:   return v1 / v2;
         }
      }

      throw EvaluatorException("Incorrect syntax tree!");
   }

public:
   double Evaluate(ASTNode* ast)
   {
      if(ast == NULL)
         throw EvaluatorException("Incorrect abstract syntax tree");

      return EvaluateSubtree(ast);
   }
};

The exception class is defined as:

class EvaluatorException : public std::exception
{
public:
   EvaluatorException(const std::string& message):
      std::exception(message.c_str())
      {
      }
};

So let’s try it:

void Test(const char* text)
{
   Parser parser;

   try 
   {
      ASTNode* ast = parser.Parse(text);

      try 
      {
         Evaluator eval;
         double val = eval.Evaluate(ast);

         std::cout << text << " = " << val << std::endl;
      }
      catch(EvaluatorException& ex)
      {
		  std::cout << text << " t " << ex.what() << std::endl; 
      }

      delete ast;
   }
   catch(ParserException& ex)
   {
      std::cout << text << " t " << ex.what() << std::endl; 
   }   
}

int main()
{
   Test("1+2+3+4");
   Test("1*2*3*4");
   Test("1-2-3-4");
   Test("1/2/3/4");
   Test("1*2+3*4");
   Test("1+2*3+4");
   Test("(1+2)*(3+4)");
   Test("1+(2*3)*(4+5)");
   Test("1+(2*3)/4+5");
   Test("5/(4+3)/2");
   Test("1 + 2.5");
   Test("125");
   Test("-1");
   Test("-1+(-2)");
   Test("-1+(-2.0)");

   Test("   1*2,5");
   Test("   1*2.5e2");
   Test("M1 + 2.5");
   Test("1 + 2&5");
   Test("1 * 2.5.6");
   Test("1 ** 2.5");
   Test("*1 / 2.5");

   return 0;
}

The output of this test program is:

1+2+3+4 = 10
1*2*3*4 = 24
1-2-3-4 = -8
1/2/3/4 = 0.0416667
1*2+3*4 = 14
1+2*3+4 = 11
(1+2)*(3+4) = 21
1+(2*3)*(4+5) = 55
1+(2*3)/4+5 = 7.5
5/(4+3)/2 = 0.357143
1 + 2.5 = 3.5
125 = 125
-1 = -1
-1+(-2) = -3
-1+(-2.0) = -3
   1*2,5         Unexpected token ',' at position 6
   1*2.5e2       Unexpected token 'e' at position 8
M1 + 2.5         Unexpected token 'M' at position 0
1 + 2&5          Unexpected token '&' at position 5
1 * 2.5.6        Unexpected token '.' at position 7
1 ** 2.5         Unexpected token '*' at position 4
*1 / 2.5         Unexpected token '*' at position 1

And that’s it. Define the grammar, build the parser, insert semantic actions and build the abstract syntax tree and then traverse it and evaluate the expression. If you are interested in understanding the grammar, and the parsing in a deeper manner than I presented in this posts, I suggest you read more articles. The purpose was not to teach compilers theory, but put it to a practical purpose.

Here you can download a Visual Studio 2008 project with the code contained in this tutorial.

7 Replies to “Evaluate Expressions – Part 4: Evaluate the Abstract Syntax Tree”

  1. I know this is a somewhat old post, but anyway: These posts could have been a lot “cleaner” if you added a separate lexer class. Other than that, the fact that it works, and that it works well, is much appreciated. It helped me build an AST parser, while my previous attempts on a RPN parser failed.

  2. I enjoyed reading your posts, but I have a questions. How should I modify this to replace double division with integer division, as a simple cast to int won’t do the trick.

  3. Hi Marius,

    It is great example to build and evaluate AST. Thank you for this good tutorial, all chapters are pretty tidy and easy to understand.

    I would like to ask that if it is possible to reach same result without any OOP? I mean using only simple data structure and functions. No classes and objects.

    I am sure of that it is possible even it is not this much easy to construct.

    What do you think?

    Greetings,

    Mehmet.

  4. Of course it’s possible. OOP is a logical concept. The simplest way to transform the OOP code into procedural code is to make the member functions of classes free functions that take a parameter a pointer to a data structure that only holds data.

  5. Pingback: yuri manga
  6. Hello Marius,

    is it possible to implmment token like variables m = 21
    or comments // /* */
    or functions sin(0.5) ?

    great work

  7. Hi Marius!

    This is a really good series of articles!

    I’m doing a small public-domain lexer and parser (in C) and I’m keen to use some of your code (which I’d translate to C). Is that ok with you? I’m happy to give acknowledgement, no problem there!

    Hope to hear from you soon – keep up the good work! Bye for now –
    – Andy

Leave a Reply

This site uses Akismet to reduce spam. Learn how your comment data is processed.