{"id":151,"date":"2009-02-06T08:00:45","date_gmt":"2009-02-06T06:00:45","guid":{"rendered":"http:\/\/mariusbancila.ro\/blog\/?p=151"},"modified":"2009-02-25T08:30:29","modified_gmt":"2009-02-25T06:30:29","slug":"evaluate-expressions-%e2%80%93-part-4-evaluate-the-abstract-syntax-tree","status":"publish","type":"post","link":"https:\/\/mariusbancila.ro\/blog\/2009\/02\/06\/evaluate-expressions-%e2%80%93-part-4-evaluate-the-abstract-syntax-tree\/","title":{"rendered":"Evaluate Expressions – Part 4: Evaluate the Abstract Syntax Tree"},"content":{"rendered":"

\nEvaluate Expressions – Part 1: The Approaches<\/a><\/b>
\nEvaluate Expressions – Part 2: Parse the Expression<\/a><\/b>
\nEvaluate Expressions – Part 3: Building the Abstract Syntax Tree<\/a><\/b>
\nEvaluate Expressions – Part 4: Evaluate the Abstract Syntax Tree<\/b>\n<\/p>\n

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.<\/p>\n

In pseudo code, this would look like this:<\/p>\n

\r\ndouble Evaluate(subtree)\r\n{\r\n   if(subtree is numeric)\r\n      return value;\r\n   else\r\n   {\r\n      op = subtree.operator\r\n      v1 = Evaluate(subtree.left)\r\n      v2 = Evaluate(subtree.right)\r\n      return v1 op v2;\r\n   }\r\n}\r\n<\/pre>\n
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:<\/p>\n
\r\nclass Evaluator \r\n{\r\n   double EvaluateSubtree(ASTNode* ast)\r\n   {\r\n      if(ast == NULL) \r\n         throw EvaluatorException(\"Incorrect syntax tree!\");\r\n\r\n      if(ast->Type == NumberValue)\r\n         return ast->Value;\r\n      else if(ast->Type == UnaryMinus)\r\n         return -EvaluateSubtree(ast->Left);\r\n      else \r\n      {\r\n         double v1 = EvaluateSubtree(ast->Left);\r\n         double v2 = EvaluateSubtree(ast->Right);\r\n         switch(ast->Type)\r\n         {\r\n         case OperatorPlus:  return v1 + v2;\r\n         case OperatorMinus: return v1 - v2;\r\n         case OperatorMul:   return v1 * v2;\r\n         case OperatorDiv:   return v1 \/ v2;\r\n         }\r\n      }\r\n\r\n      throw EvaluatorException(\"Incorrect syntax tree!\");\r\n   }\r\n\r\npublic:\r\n   double Evaluate(ASTNode* ast)\r\n   {\r\n      if(ast == NULL)\r\n         throw EvaluatorException(\"Incorrect abstract syntax tree\");\r\n\r\n      return EvaluateSubtree(ast);\r\n   }\r\n};\r\n<\/pre>\n
The exception class is defined as:<\/p>\n
\r\nclass EvaluatorException : public std::exception\r\n{\r\npublic:\r\n   EvaluatorException(const std::string& message):\r\n      std::exception(message.c_str())\r\n      {\r\n      }\r\n};\r\n<\/pre>\n
So let’s try it:<\/p>\n
\r\nvoid Test(const char* text)\r\n{\r\n   Parser parser;\r\n\r\n   try \r\n   {\r\n      ASTNode* ast = parser.Parse(text);\r\n\r\n      try \r\n      {\r\n         Evaluator eval;\r\n         double val = eval.Evaluate(ast);\r\n\r\n         std::cout << text << \" = \" << val << std::endl;\r\n      }\r\n      catch(EvaluatorException& ex)\r\n      {\r\n\t\t  std::cout << text << \" t \" << ex.what() << std::endl; \r\n      }\r\n\r\n      delete ast;\r\n   }\r\n   catch(ParserException& ex)\r\n   {\r\n      std::cout << text << \" t \" << ex.what() << std::endl; \r\n   }   \r\n}\r\n\r\nint main()\r\n{\r\n   Test(\"1+2+3+4\");\r\n   Test(\"1*2*3*4\");\r\n   Test(\"1-2-3-4\");\r\n   Test(\"1\/2\/3\/4\");\r\n   Test(\"1*2+3*4\");\r\n   Test(\"1+2*3+4\");\r\n   Test(\"(1+2)*(3+4)\");\r\n   Test(\"1+(2*3)*(4+5)\");\r\n   Test(\"1+(2*3)\/4+5\");\r\n   Test(\"5\/(4+3)\/2\");\r\n   Test(\"1 + 2.5\");\r\n   Test(\"125\");\r\n   Test(\"-1\");\r\n   Test(\"-1+(-2)\");\r\n   Test(\"-1+(-2.0)\");\r\n\r\n   Test(\"   1*2,5\");\r\n   Test(\"   1*2.5e2\");\r\n   Test(\"M1 + 2.5\");\r\n   Test(\"1 + 2&5\");\r\n   Test(\"1 * 2.5.6\");\r\n   Test(\"1 ** 2.5\");\r\n   Test(\"*1 \/ 2.5\");\r\n\r\n   return 0;\r\n}\r\n<\/pre>\n
The output of this test program is:<\/p>\n
\r\n1+2+3+4 = 10\r\n1*2*3*4 = 24\r\n1-2-3-4 = -8\r\n1\/2\/3\/4 = 0.0416667\r\n1*2+3*4 = 14\r\n1+2*3+4 = 11\r\n(1+2)*(3+4) = 21\r\n1+(2*3)*(4+5) = 55\r\n1+(2*3)\/4+5 = 7.5\r\n5\/(4+3)\/2 = 0.357143\r\n1 + 2.5 = 3.5\r\n125 = 125\r\n-1 = -1\r\n-1+(-2) = -3\r\n-1+(-2.0) = -3\r\n   1*2,5         Unexpected token ',' at position 6\r\n   1*2.5e2       Unexpected token 'e' at position 8\r\nM1 + 2.5         Unexpected token 'M' at position 0\r\n1 + 2&5          Unexpected token '&' at position 5\r\n1 * 2.5.6        Unexpected token '.' at position 7\r\n1 ** 2.5         Unexpected token '*' at position 4\r\n*1 \/ 2.5         Unexpected token '*' at position 1\r\n<\/pre>\n
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.<\/p>\n
Here<\/a> you can download a Visual Studio 2008 project with the code contained in this tutorial.<\/p>\n
<\/p>\n","protected":false},"excerpt":{"rendered":"
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 … Read more<\/a><\/p>\n","protected":false},"author":1,"featured_media":0,"comment_status":"open","ping_status":"open","sticky":false,"template":"","format":"standard","meta":{"_uag_custom_page_level_css":"","advgb_blocks_editor_width":"","advgb_blocks_columns_visual_guide":"","_jetpack_newsletter_access":"","_jetpack_dont_email_post_to_subs":false,"_jetpack_newsletter_tier_id":0,"_jetpack_memberships_contains_paywalled_content":false,"_jetpack_feature_clip_id":0,"_jetpack_memberships_contains_paid_content":false,"footnotes":"","jetpack_publicize_message":"","jetpack_publicize_feature_enabled":true,"jetpack_social_post_already_shared":false,"jetpack_social_options":{"image_generator_settings":{"template":"highway","default_image_id":0,"font":"","enabled":false},"version":2},"jetpack_post_was_ever_published":false},"categories":[9,7],"tags":[58,451,66,65,59],"class_list":["post-151","post","type-post","status-publish","format-standard","hentry","category-articles_and_tutorials","category-c","tag-ast","tag-c","tag-expressions","tag-grammar","tag-parser"],"aioseo_notices":[],"aioseo_head":"\n\t\t\n\t\n\t\n\t\n\t\n\t\n\t\t\n\t\t\n\t\t\n\t\t\n\t\t\n\t\t\n\t\t\n\t\t\n\t\t\n\t\t