{"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":"

Python Algorithm – Evaluation of Postfix Expression:<\/span><\/h3>\n

The Postfix notation<\/a> is used to represent algebraic expressions. The expressions written in postfix form are evaluated faster compared to <\/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

Following is algorithm for evaluation postfix expressions:<\/span><\/h3>\n

Step 1:<\/strong><\/span>\u00a0Create<\/strong> a stack<\/a> to store operands (or values).
\nStep 2:<\/strong><\/span> Scan<\/strong> the given expression<\/strong> and do following for every scanned element.
\n\u2026..a) If the element is a number<\/strong>, push it<\/strong> into the stack
\n\u2026..b) If the element is a operator, pop operands<\/strong> for the operator from stack. Evaluate the operator and push the result back to the stack
\nStep 3:<\/strong> <\/span>When the expression is ended, the number<\/strong> in the stack is the final answer<\/strong><\/p>\n

Example:<\/strong><\/span><\/h3>\n

Let the given expression be \u201c2 3 1 * + 9 –<\/strong>\u201c. We scan all elements one by one.
\n1) Scan \u20182\u2019,<\/strong> it\u2019s a number, so push<\/strong> it to stack. Stack contains \u20182\u2019
\n2) Scan \u20183<\/strong>\u2019, again a number, push<\/strong> it to stack, stack now contains \u20182 3\u2019 (from bottom to top)
\n3) Scan \u20181\u2019,<\/strong> again a number, push it to stack, stack now contains \u20182 3 1\u2019
\n4) Scan \u2018*\u2019,<\/strong> it\u2019s an operator, 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.
\n5) Scan \u2018+\u2019<\/strong>, it\u2019s an operator, 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.
\n6) Scan \u20189\u2019<\/strong>, it\u2019s a number, we push<\/strong> it to the stack. Stack now becomes \u20185 9\u2019.
\n7) Scan \u2018-\u2018<\/strong>, it\u2019s an operator, 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.
\n8) There are no more elements to scan, we return the top element from stack<\/strong> (which is the only element left in stack).<\/p>\n[ad type=”banner”]\n

Following is Python implementation<\/a> of above algorithm.<\/p>\n

Python Programming:<\/strong><\/span><\/p>\n

<\/div> 
# Python program to evaluate value of a postfix expression # Class to convert the expressionclass Evaluate:         # Constructor to initialize the class variables    def __init__(self, capacity):        self.top = -1        self.capacity = capacity        # This array is used a stack         self.array = []         # check if the stack is empty    def isEmpty(self):        return True if self.top == -1 else False         # Return the value of the top of the stack    def peek(self):        return self.array[-1]         # Pop the element from the stack    def pop(self):        if not self.isEmpty():            self.top -= 1            return self.array.pop()        else:            return "$"         # Push the element to the stack    def push(self, op):        self.top += 1        self.array.append(op)       # The main function that converts given infix expression    # to postfix expression    def evaluatePostfix(self, exp):                 # Iterate over the expression for conversion        for i in exp:                         # If the scanned character is an operand            # (number here) push it to the stack            if i.isdigit():                self.push(i)             # If the scanned character is an operator,            # pop two elements from stack and apply it.            else:                val1 = self.pop()                val2 = self.pop()                self.push(str(eval(val2 + i + val1)))         return int(self.pop())                               # Driver program to test above functionexp = "231*+9-"obj = Evaluate(len(exp))print "Value of %s is %d" %(exp, obj.evaluatePostfix(exp)) # This code is contributed by Nikhil Kumar Singh(nickzuck_007)<\/code><\/pre> <\/div>\n
Output:<\/strong><\/span><\/h3>\n
Value of 231*+9- is -4<\/pre>\n
Time complexity<\/strong><\/span> of evaluation algorithm is O(n)<\/strong> where n is number of characters in input expression.<\/p>\n
There are following limitations of above implementation:<\/span><\/h3>\n
1) It supports only 4 binary operators<\/a> \u2018+\u2019, \u2018*\u2019, \u2018-\u2018 and \u2018\/\u2019.<\/strong> It can be extended for more operators by adding more switch cases.
\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=”banner”]\n","protected":false},"excerpt":{"rendered":"
Python Algorithm – Evaluation of Postfix Expression – 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}]}}