{"id":26851,"date":"2017-12-24T15:47:56","date_gmt":"2017-12-24T10:17:56","guid":{"rendered":"https:\/\/www.wikitechy.com\/technology\/?p=26851"},"modified":"2018-10-30T16:01:01","modified_gmt":"2018-10-30T10:31:01","slug":"python-algorithm-evaluation-postfix-expression","status":"publish","type":"post","link":"https:\/\/www.wikitechy.com\/technology\/python-algorithm-evaluation-postfix-expression\/","title":{"rendered":"Evaluation of Postfix Expression"},"content":{"rendered":"<h3 id=\"python-algorithm-evaluation-of-postfix-expression\"><span style=\"color: #333300;\">Python Algorithm \u2013 Evaluation of Postfix Expression:<\/span><\/h3>\n<p>The <a href=\"https:\/\/www.wikitechy.com\/technology\/26824-2\/\" target=\"_blank\" rel=\"noopener\">Postfix notation<\/a> is used to represent algebraic expressions. The expressions written in postfix form are evaluated faster compared to <span id=\"more-142800\"><\/span>infix notation as parenthesis are not required in postfix. We have discussed infix to postfix conversion. In this post, evaluation of postfix expressions is discussed.<\/p>\n<h3 id=\"following-is-algorithm-for-evaluation-postfix-expressions\"><span style=\"color: #000080;\">Following is algorithm for evaluation postfix expressions:<\/span><\/h3>\n<p><span style=\"color: #008000;\"><strong>Step 1:<\/strong><\/span>\u00a0<strong>Create<\/strong> a <a href=\"https:\/\/www.wikitechy.com\/technology\/implement-stack-using-queues\/\" target=\"_blank\" rel=\"noopener\">stack<\/a> to store operands (or values).<br \/>\n<span style=\"color: #008000;\"><strong>Step 2:<\/strong><\/span> <strong>Scan<\/strong> the given <strong>expression<\/strong> and do following for every scanned element.<br \/>\n\u2026..a) If the element is a <strong>number<\/strong>, <strong>push it<\/strong> into the stack<br \/>\n\u2026..b) If the element is a <strong>operator, pop operands<\/strong> for the operator from stack. Evaluate the operator and push the result back to the stack<br \/>\n<span style=\"color: #008000;\"><strong>Step 3:<\/strong> <\/span>When the expression is ended, the<strong> number<\/strong> in the stack is the <strong>final answer<\/strong><\/p>\n<h3 id=\"example\"><span style=\"color: #0000ff;\"><strong>Example:<\/strong><\/span><\/h3>\n<p>Let the given expression be \u201c<strong>2 3 1 * + 9 \u2013<\/strong>\u201c. We scan all elements one by one.<br \/>\n1) <strong>Scan \u20182\u2019,<\/strong> it\u2019s a number, so <strong>push<\/strong> it to stack. Stack contains \u20182\u2019<br \/>\n2) <strong>Scan \u20183<\/strong>\u2019, again a number, <strong>push<\/strong> it to stack, stack now contains \u20182 3\u2019 (from bottom to top)<br \/>\n3)<strong> Scan \u20181\u2019,<\/strong> again a number, push it to stack, stack now contains \u20182 3 1\u2019<br \/>\n4)<strong> Scan \u2018*\u2019,<\/strong> it\u2019s an operator, <strong>pop two operands<\/strong> from stack, apply the * operator on operands, we get 3*1 which results in 3. We push the result \u20183\u2019 to stack. Stack now becomes \u20182 3\u2019.<br \/>\n5) <strong>Scan \u2018+\u2019<\/strong>, it\u2019s an operator, <strong>pop two operands<\/strong> from stack, apply the + operator on operands, we get 3 + 2 which results in 5. We push the result \u20185\u2019 to stack. Stack now becomes \u20185\u2019.<br \/>\n6) <strong>Scan \u20189\u2019<\/strong>, it\u2019s a number, we <strong>push<\/strong> it to the stack. Stack now becomes \u20185 9\u2019.<br \/>\n7) <strong>Scan \u2018-\u2018<\/strong>, it\u2019s an operator,<strong> pop two operands<\/strong> from stack, apply the \u2013 operator on operands, we get 5 \u2013 9 which results in -4. We push the result \u2018-4\u2019 to stack. Stack now becomes \u2018-4\u2019.<br \/>\n8) There are no more elements to scan, we return the <strong>top element from stack<\/strong> (which is the only element left in stack).<\/p>\n[ad type=\u201dbanner\u201d]\n<p>Following is <a href=\"https:\/\/www.wikitechy.com\/tutorials\/python\/python-program-to-reverse-a-number\" target=\"_blank\" rel=\"noopener\">Python implementation<\/a> of above algorithm.<\/p>\n<p><span style=\"color: #800080;\"><strong>Python Programming:<\/strong><\/span><\/p>\n[pastacode lang=\u201dpython\u201d manual=\u201d%23%20Python%20program%20to%20evaluate%20value%20of%20a%20postfix%20expression%0A%20%0A%23%20Class%20to%20convert%20the%20expression%0Aclass%20Evaluate%3A%0A%20%20%20%20%20%0A%20%20%20%20%23%20Constructor%20to%20initialize%20the%20class%20variables%0A%20%20%20%20def%20__init__(self%2C%20capacity)%3A%0A%20%20%20%20%20%20%20%20self.top%20%3D%20-1%0A%20%20%20%20%20%20%20%20self.capacity%20%3D%20capacity%0A%20%20%20%20%20%20%20%20%23%20This%20array%20is%20used%20a%20stack%20%0A%20%20%20%20%20%20%20%20self.array%20%3D%20%5B%5D%0A%20%20%20%20%20%0A%20%20%20%20%23%20check%20if%20the%20stack%20is%20empty%0A%20%20%20%20def%20isEmpty(self)%3A%0A%20%20%20%20%20%20%20%20return%20True%20if%20self.top%20%3D%3D%20-1%20else%20False%0A%20%20%20%20%20%0A%20%20%20%20%23%20Return%20the%20value%20of%20the%20top%20of%20the%20stack%0A%20%20%20%20def%20peek(self)%3A%0A%20%20%20%20%20%20%20%20return%20self.array%5B-1%5D%0A%20%20%20%20%20%0A%20%20%20%20%23%20Pop%20the%20element%20from%20the%20stack%0A%20%20%20%20def%20pop(self)%3A%0A%20%20%20%20%20%20%20%20if%20not%20self.isEmpty()%3A%0A%20%20%20%20%20%20%20%20%20%20%20%20self.top%20-%3D%201%0A%20%20%20%20%20%20%20%20%20%20%20%20return%20self.array.pop()%0A%20%20%20%20%20%20%20%20else%3A%0A%20%20%20%20%20%20%20%20%20%20%20%20return%20%22%24%22%0A%20%20%20%20%20%0A%20%20%20%20%23%20Push%20the%20element%20to%20the%20stack%0A%20%20%20%20def%20push(self%2C%20op)%3A%0A%20%20%20%20%20%20%20%20self.top%20%2B%3D%201%0A%20%20%20%20%20%20%20%20self.array.append(op)%20%0A%20%0A%20%0A%20%20%20%20%23%20The%20main%20function%20that%20converts%20given%20infix%20expression%0A%20%20%20%20%23%20to%20postfix%20expression%0A%20%20%20%20def%20evaluatePostfix(self%2C%20exp)%3A%0A%20%20%20%20%20%20%20%20%20%0A%20%20%20%20%20%20%20%20%23%20Iterate%20over%20the%20expression%20for%20conversion%0A%20%20%20%20%20%20%20%20for%20i%20in%20exp%3A%0A%20%20%20%20%20%20%20%20%20%20%20%20%20%0A%20%20%20%20%20%20%20%20%20%20%20%20%23%20If%20the%20scanned%20character%20is%20an%20operand%0A%20%20%20%20%20%20%20%20%20%20%20%20%23%20(number%20here)%20push%20it%20to%20the%20stack%0A%20%20%20%20%20%20%20%20%20%20%20%20if%20i.isdigit()%3A%0A%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20self.push(i)%0A%20%0A%20%20%20%20%20%20%20%20%20%20%20%20%23%20If%20the%20scanned%20character%20is%20an%20operator%2C%0A%20%20%20%20%20%20%20%20%20%20%20%20%23%20pop%20two%20elements%20from%20stack%20and%20apply%20it.%0A%20%20%20%20%20%20%20%20%20%20%20%20else%3A%0A%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20val1%20%3D%20self.pop()%0A%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20val2%20%3D%20self.pop()%0A%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20self.push(str(eval(val2%20%2B%20i%20%2B%20val1)))%0A%20%0A%20%20%20%20%20%20%20%20return%20int(self.pop())%0A%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%0A%20%0A%20%20%20%20%20%20%20%20%20%20%20%20%20%0A%23%20Driver%20program%20to%20test%20above%20function%0Aexp%20%3D%20%22231*%2B9-%22%0Aobj%20%3D%20Evaluate(len(exp))%0Aprint%20%22Value%20of%20%25s%20is%20%25d%22%20%25(exp%2C%20obj.evaluatePostfix(exp))%0A%20%0A%23%20This%20code%20is%20contributed%20by%20Nikhil%20Kumar%20Singh(nickzuck_007)\u201d message=\u201d\u201d highlight=\u201d\u201d provider=\u201dmanual\u201d\/]\n<h3 id=\"output\"><span style=\"color: #008000;\"><strong>Output:<\/strong><\/span><\/h3>\n<pre>Value of 231*+9- is -4<\/pre>\n<p><span style=\"color: #008080;\"><strong>Time complexity<\/strong><\/span> of evaluation algorithm is<strong> O(n)<\/strong> where n is number of characters in input expression.<\/p>\n<h3 id=\"there-are-following-limitations-of-above-implementation\"><span style=\"color: #333399;\">There are following limitations of above implementation:<\/span><\/h3>\n<p>1) It supports only 4 binary <a href=\"https:\/\/www.wikitechy.com\/tutorials\/python\/python-operator\" target=\"_blank\" rel=\"noopener\">operators<\/a> \u2018<strong>+\u2019, \u2018*\u2019, \u2018-\u2018 and \u2018\/\u2019.<\/strong> It can be extended for more operators by adding more switch cases.<br \/>\n2) The allowed operands are only single digit operands. The program can be extended for multiple digits by adding a separator like space between all elements (operators and operands) of given expression.<\/p>\n[ad type=\u201dbanner\u201d]\n","protected":false},"excerpt":{"rendered":"<p>Python Algorithm &#8211; Evaluation of Postfix Expression &#8211; Data Structure -The Postfix notation is used to represent algebraic expressions.<\/p>\n","protected":false},"author":1,"featured_media":31259,"comment_status":"open","ping_status":"open","sticky":false,"template":"","format":"standard","meta":{"footnotes":""},"categories":[69969,73012,4148,79607],"tags":[79896,80041,80097,80038,80039,80040,80102,80103,80098,80104,80101,80099,80100],"class_list":["post-26851","post","type-post","status-publish","format-standard","has-post-thumbnail","hentry","category-algorithm","category-data-structures","category-python","category-stack","tag-algorithm-for-evaluation-of-postfix-expression","tag-algorithm-for-evaluation-of-prefix-expression","tag-evaluate-postfix-expression-python","tag-evaluation-of-postfix-expression-using-stack-examples","tag-evaluation-of-postfix-expression-using-stack-in-c","tag-evaluation-of-postfix-expression-using-stack-in-data-structure","tag-how-to-evaluate-postfix-expression","tag-infix-to-postfix-python","tag-postfix-expression-evaluation-using-stack-in-python","tag-postfix-notation","tag-postfix-python-code","tag-pseudo-code-for-postfix-evaluation","tag-python-postfix-calculator"],"_links":{"self":[{"href":"https:\/\/www.wikitechy.com\/technology\/wp-json\/wp\/v2\/posts\/26851","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\/1"}],"replies":[{"embeddable":true,"href":"https:\/\/www.wikitechy.com\/technology\/wp-json\/wp\/v2\/comments?post=26851"}],"version-history":[{"count":0,"href":"https:\/\/www.wikitechy.com\/technology\/wp-json\/wp\/v2\/posts\/26851\/revisions"}],"wp:featuredmedia":[{"embeddable":true,"href":"https:\/\/www.wikitechy.com\/technology\/wp-json\/wp\/v2\/media\/31259"}],"wp:attachment":[{"href":"https:\/\/www.wikitechy.com\/technology\/wp-json\/wp\/v2\/media?parent=26851"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/www.wikitechy.com\/technology\/wp-json\/wp\/v2\/categories?post=26851"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/www.wikitechy.com\/technology\/wp-json\/wp\/v2\/tags?post=26851"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}