{"id":27141,"date":"2018-01-05T20:39:31","date_gmt":"2018-01-05T15:09:31","guid":{"rendered":"https:\/\/www.wikitechy.com\/technology\/?p=27141"},"modified":"2018-01-05T20:39:31","modified_gmt":"2018-01-05T15:09:31","slug":"c-programming-program-evaluate-simple-expressions","status":"publish","type":"post","link":"https:\/\/www.wikitechy.com\/technology\/c-programming-program-evaluate-simple-expressions\/","title":{"rendered":"C++ Programming – Program to evaluate simple expressions"},"content":{"rendered":"

You are given a string that represent an expression of digits and operands. E.g. 1+2*3, 1-2+4. You need to evaluate the string or the expression. NO BODMAS is followed. If the expression is of incorrect syntax return -1.<\/span>
\nTest cases:
\na) 1+2*3 will be evaluated to 9.
\nb) 4-2+6*3 will be evaluated to 24.
\nc) 1++2 will be evaluated to -1(INVALID).
\nAlso, in the string spaces can occur. For that case we need to ignore the spaces. Like :- 1*2 -1 is equals to 1.<\/p>\n

The idea is simple start from the first character and traverse from left to right and check for errors like two consecutive operators and operands. We also keep track of result and update the result while traversing the expression.<\/p>\n

Following is C++ program to evaluate the given expression.<\/p>\n[pastacode lang=\u201dcpp\u201d manual=\u201d%2F%2F%20C%2B%2B%20program%20to%20evaluate%20a%20given%20expression%0A%23include%20%3Cioexpeam%3E%0Ausing%20namespace%20std%3B%0A%20%0A%2F%2F%20A%20utility%20function%20to%20check%20if%20a%20given%20character%20is%20operand%0Abool%20isOperand(char%20c)%20%7B%20return%20(c%20%3E%3D%20\u20190\u2019%20%26%26%20c%20%3C%3D%20\u20199\u2032)%3B%20%7D%0A%20%0A%2F%2F%20utility%20function%20to%20find%20value%20of%20and%20operand%0Aint%20value(char%20c)%20%7B%20%20return%20(c%20-%20\u20190\u2032)%3B%20%7D%0A%20%0A%2F%2F%20This%20function%20evaluates%20simple%20expressions.%20It%20returns%20-1%20if%20the%0A%2F%2F%20given%20expression%20is%20invalid.%0Aint%20evaluate(char%20*exp)%0A%7B%0A%20%20%20%20%2F%2F%20Base%20Case%3A%20Given%20expression%20is%20empty%0A%20%20%20%20if%20(*exp%20%3D%3D%20\u2019%5C0\u2032)%20%20return%20-1%3B%0A%20%0A%20%20%20%20%2F%2F%20The%20first%20character%20must%20be%20an%20operand%2C%20find%20its%20value%0A%20%20%20%20int%20res%20%3D%20value(exp%5B0%5D)%3B%0A%20%0A%20%20%20%20%2F%2F%20Traverse%20the%20remaining%20characters%20in%20pairs%0A%20%20%20%20for%20(int%20i%20%3D%201%3B%20exp%5Bi%5D%3B%20i%20%2B%3D%202)%0A%20%20%20%20%7B%0A%20%20%20%20%20%20%20%20%2F%2F%20The%20next%20character%20must%20be%20an%20operator%2C%20and%0A%20%20%20%20%20%20%20%20%2F%2F%20next%20to%20next%20an%20operand%0A%20%20%20%20%20%20%20%20char%20opr%20%3D%20exp%5Bi%5D%2C%20opd%20%3D%20exp%5Bi%2B1%5D%3B%0A%20%0A%20%20%20%20%20%20%20%20%2F%2F%20If%20next%20to%20next%20character%20is%20not%20an%20operand%0A%20%20%20%20%20%20%20%20if%20(!isOperand(opd))%20%20return%20-1%3B%0A%20%0A%20%20%20%20%20%20%20%20%2F%2F%20Update%20result%20according%20to%20the%20operator%0A%20%20%20%20%20%20%20%20if%20(opr%20%3D%3D%20\u2019%2B\u2019)%20%20%20%20%20%20%20res%20%2B%3D%20value(opd)%3B%0A%20%20%20%20%20%20%20%20else%20if%20(opr%20%3D%3D%20\u2032-\u2018)%20%20res%20-%3D%20value(opd)%3B%0A%20%20%20%20%20%20%20%20else%20if%20(opr%20%3D%3D%20\u2019*\u2019)%20%20res%20*%3D%20value(opd)%3B%0A%20%20%20%20%20%20%20%20else%20if%20(opr%20%3D%3D%20\u2019%2F\u2019)%20%20res%20%2F%3D%20value(opd)%3B%0A%20%0A%20%20%20%20%20%20%20%20%2F%2F%20If%20not%20a%20valid%20operator%0A%20%20%20%20%20%20%20%20else%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20return%20-1%3B%0A%20%20%20%20%7D%0A%20%20%20%20return%20res%3B%0A%7D%0A%20%0A%2F%2F%20Driver%20program%20to%20test%20above%20function%0Aint%20main()%0A%7B%0A%20%20%20%20char%20expr1%5B%5D%20%3D%20%221%2B2*5%2B3%22%3B%0A%20%20%20%20int%20res%20%3D%20evaluate(expr1)%3B%0A%20%20%20%20(res%20%3D%3D%20-1)%3F%20cout%20%3C%3C%20expr1%20%3C%3C%20%22%20is%20%22%20%3C%3C%20%22Invalid%5Cn%22%3A%0A%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20cout%20%3C%3C%20%22Value%20of%20%22%20%3C%3C%20expr1%20%3C%3C%20%22%20is%20%22%20%3C%3C%20res%20%3C%3C%20endl%3B%0A%20%0A%20%20%20%20char%20expr2%5B%5D%20%3D%20%221%2B2*3%22%3B%0A%20%20%20%20res%20%3D%20evaluate(expr2)%3B%0A%20%20%20%20(res%20%3D%3D%20-1)%3F%20cout%20%3C%3C%20expr2%20%3C%3C%20%22%20is%20%22%20%3C%3C%20%22Invalid%5Cn%22%3A%0A%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20cout%20%3C%3C%20%22Value%20of%20%22%20%3C%3C%20expr2%20%3C%3C%20%22%20is%20%22%20%3C%3C%20res%20%3C%3C%20endl%3B%0A%20%0A%20%20%20%20char%20expr3%5B%5D%20%3D%20%224-2%2B6*3%22%3B%0A%20%20%20%20res%20%3D%20evaluate(expr3)%3B%0A%20%20%20%20(res%20%3D%3D%20-1)%3F%20cout%20%3C%3C%20expr3%20%3C%3C%20%22%20is%20%22%20%3C%3C%20%22Invalid%5Cn%22%3A%0A%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20cout%20%3C%3C%20%22Value%20of%20%22%20%3C%3C%20expr3%20%3C%3C%20%22%20is%20%22%20%3C%3C%20res%20%3C%3C%20endl%3B%0A%20%0A%20%20%20%20char%20expr4%5B%5D%20%3D%20%221%2B%2B2%22%3B%0A%20%20%20%20res%20%3D%20evaluate(expr4)%3B%0A%20%20%20%20(res%20%3D%3D%20-1)%3F%20cout%20%3C%3C%20expr4%20%3C%3C%20%22%20is%20%22%20%3C%3C%20%22Invalid%5Cn%22%3A%0A%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20cout%20%3C%3C%20%22Value%20of%20%22%20%3C%3C%20expr4%20%3C%3C%20%22%20is%20%22%20%3C%3C%20res%20%3C%3C%20endl%3B%0A%20%20%20%20return%200%3B%0A%7D\u201d message=\u201dC++ Program\u201d highlight=\u201d\u201d provider=\u201dmanual\u201d\/]\n

Output:<\/strong><\/p>\n

Value of 1+2*5+3 is 18\r\nValue of 1+2*3 is 9\r\nValue of 4-2+6*3 is 24\r\n1++2 is Invalid<\/pre>\n
The above code doesn\u2019t handle spaces. We can handle spaces by first removing all spaces from the given string. A better solution is to handle spaces in single traversal. This is left as an exercise.<\/p>\n
Time Complexity is O(n) where n is length of the given expression.<\/p>\n[ad type=\u201dbanner\u201d]\n","protected":false},"excerpt":{"rendered":"
C++ Programming – Program to evaluate simple expressions – Algorithm – string that represent an expression of digits and operands. E.g. 1+2*3, 1-2+4. <\/p>\n","protected":false},"author":2,"featured_media":0,"comment_status":"open","ping_status":"open","sticky":false,"template":"","format":"standard","meta":{"footnotes":""},"categories":[69969,83515,1],"tags":[74843,69926,74830,80915,74826,80911,80912,75654,80914,80917,76278,69952,78357,74838],"class_list":["post-27141","post","type-post","status-publish","format-standard","hentry","category-algorithm","category-c-programming-3","category-coding","tag-arithmetic-operators-in-c","tag-c-language-basics-notes","tag-c-programming-basics-notes","tag-c-programming-conditional-operator","tag-c-programming-switch","tag-c-type-casting","tag-conditional-expression-in-c","tag-conditional-operator-in-c","tag-conditional-operators-in-c","tag-variable-declaration-in-c","tag-various-operators-in-c","tag-what-is-c-language-definition","tag-what-is-in-c-language","tag-while-loop-in-c-programming-example"],"_links":{"self":[{"href":"https:\/\/www.wikitechy.com\/technology\/wp-json\/wp\/v2\/posts\/27141","targetHints":{"allow":["GET"]}}],"collection":[{"href":"https:\/\/www.wikitechy.com\/technology\/wp-json\/wp\/v2\/posts"}],"about":[{"href":"https:\/\/www.wikitechy.com\/technology\/wp-json\/wp\/v2\/types\/post"}],"author":[{"embeddable":true,"href":"https:\/\/www.wikitechy.com\/technology\/wp-json\/wp\/v2\/users\/2"}],"replies":[{"embeddable":true,"href":"https:\/\/www.wikitechy.com\/technology\/wp-json\/wp\/v2\/comments?post=27141"}],"version-history":[{"count":0,"href":"https:\/\/www.wikitechy.com\/technology\/wp-json\/wp\/v2\/posts\/27141\/revisions"}],"wp:attachment":[{"href":"https:\/\/www.wikitechy.com\/technology\/wp-json\/wp\/v2\/media?parent=27141"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/www.wikitechy.com\/technology\/wp-json\/wp\/v2\/categories?post=27141"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/www.wikitechy.com\/technology\/wp-json\/wp\/v2\/tags?post=27141"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}