The human understandable notation is infix. But it turns out that trying to parse a string with infix expression, from left to right and evaluate it is not possible. Because you cannot now what in advance and operators have different precedence; and there are parentheses too.<\/p>\n
To solve the problem you’d have to build a helper structure representing the infix expression. There are two possibilities:<\/p>\n
- \n
- Reverse Polish Notation<\/a> (RPN) implies transforming the infix expression in a postfix expression and then evaluating it from left to right. 1 + 2*3 is transformed into 1 2 3 * +. You go from left to right until you find an operator, evaluate the expression and then replace it in the stack.<\/li>\n
- \n
Abstract Syntax Tree<\/a> (AST) is an abstract representation of an expression, with inner nodes representing operators and leafs representing numbers.<\/p>\n
![\"Abstract](\"\/blog\/wp-content\/uploads\/2009\/02\/ast.png\")
<\/p>\n<\/li>\n<\/ul>\nThe RPN is harder to build and evaluate in my opinion, so I will focus on the approach with the AST.<\/p>\n
We build an AST while parsing the expression. First, we’ll have to define the grammar for the expression. Otherwise we wouldn’t know what to parse. <\/p>\n
\r\nEXP -> EXP + EXP | EXP - EXP | EXP * EXP | EXP \/ EXP | - EXP | (EXP) | number\r\n<\/pre>\n
First, this grammar is recursive, as you can see, but another important problem is that it does not represent the precedence of the operators. For this reasons, a better grammar is this:<\/p>\n
\r\nEXP -> EXP + TERM | \r\n EXP - TERM | \r\n TERM\r\nTERM -> TERM * FACTOR | \r\n TERM \/ FACTOR | \r\n FACTOR\r\nFACTOR -> ( EXP ) | - EXP | number\r\n<\/pre>\n
These rules written above are called productions. The symbols used are:<\/p>\n
- \n
- EXP, TERM, FACTOR are called non-terminal symbols<\/li>\n
- +, -, \/, *, (, ) number are called terminal symbols<\/li>\n
- EXT is the start symbol<\/li>\n<\/ul>\n
While the grammar has the correct operator precedence, it’s still recursive, or more precisely, left-recursive. You can see that EXP goes into EXP then operator + then TERM. You never reach to match operator + because you have start again and again with a new expression. There are techniques for eliminating this recursion and the result is:<\/p>\n
\r\nEXP -> TERM EXP1\r\nEXP1 -> + TERM EXP1 | \r\n - TERM EXP1 | \r\n epsilon\r\nTERM -> FACTOR TERM1\r\nTERM1 -> * FACTOR TERM1 | \r\n \/ FACTOR TERM1 | \r\n epsilon\r\nFACTOR -> ( EXP ) | - EXP | number\r\n<\/pre>\n
‘epsilon’ here means ‘nothing’.<\/p>\n
With the theory (well, this is just the tip of the iceberg, but should be a good start for you) in place we’ll have to do three things:<\/p>\n
- \n
- Parse the expression<\/a><\/li>\n
- Build the abstract syntax tree<\/a><\/li>\n
- Evaluate the abstract syntax tree<\/a><\/li>\n<\/ul>\n
The first two steps will be done the same time, but I’ll take them one at a time and explain it in details.<\/p>\n
Before you continue with the implementation details, I suggest you read more about both RPN and AST and grammars.<\/p>\n
Here are several references:<\/p>\n
- \n
- Syntax, Grammar<\/a><\/li>\n
- Arithmetic Expressions<\/a><\/li>\n
- Abstract Syntax<\/a><\/li>\n
- Top-Down Parsing<\/a><\/li>\n
- \n","protected":false},"excerpt":{"rendered":"
I was discussing a few days ago about evaluating expressions and I decided to explain how you can build an evaluator. I will do this in a series of posts, getting one step more in each post. I will use C++, but the approaches are the same regardless the language. Let’s consider this expression: 1+2*3. … 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,61,91],"class_list":["post-148","post","type-post","status-publish","format-standard","hentry","category-articles_and_tutorials","category-c","tag-ast","tag-c","tag-expression","tag-rpn"],"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
- Arithmetic Expressions<\/a><\/li>\n
- Build the abstract syntax tree<\/a><\/li>\n
- Parse the expression<\/a><\/li>\n
- \n