Marius Bancila’s Blog

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.