{"id":26824,"date":"2017-12-24T15:40:04","date_gmt":"2017-12-24T10:10:04","guid":{"rendered":"https:\/\/www.wikitechy.com\/technology\/?p=26824"},"modified":"2018-10-24T21:49:05","modified_gmt":"2018-10-24T16:19:05","slug":"26824-2","status":"publish","type":"post","link":"https:\/\/www.wikitechy.com\/technology\/26824-2\/","title":{"rendered":"Python Algorithm &#8211; Infix to Postfix Conversion using Stack"},"content":{"rendered":"<h2 id=\"infix-expression\"><span style=\"color: #ff0000;\"><strong>Infix expression:<\/strong><\/span><\/h2>\n<ul>\n<li>The expression of the form a op b. When an <a href=\"https:\/\/www.wikitechy.com\/technology\/smallest-three-integers-without-comparison-operators\/\">operator<\/a> is in-between every pair of operands.<span id=\"more-142798\"><\/span><\/li>\n<\/ul>\n<h2 id=\"postfix-expression\"><span style=\"color: #339966;\"><strong>Postfix expression:<\/strong><\/span><\/h2>\n<ul>\n<li>The <a href=\"https:\/\/www.wikitechy.com\/technology\/expression-evaluation\/\">expression<\/a> of the form a b op. When an operator is followed for every pair of operands.<\/li>\n<\/ul>\n<h2 id=\"why-postfix-representation-of-the-expression\"><span style=\"color: #800080;\"><strong>Why postfix representation of the expression?<\/strong><\/span><\/h2>\n<ul>\n<li>The<a href=\"https:\/\/www.wikitechy.com\/technology\/compiler-design-lexical-analysis\/\"> compiler<\/a> scans the expression either from left to right or from right to left.<\/li>\n<\/ul>\n<p>Consider the below expression:<\/p>\n<p>a op1 b op2 c op3 d<br \/>\nIf op1 = +, op2 = *, op3 = +<\/p>\n<p>The compiler first scans the expression to evaluate the expression b * c, then again scan the expression to add a to it. The result is then added to d after another scan.<\/p>\n<p>The repeated scanning makes it very in-efficient. It is better to<a href=\"https:\/\/www.wikitechy.com\/technology\/how-to-convert-your-phone-into-a-portable-amazon-echo\/\"> convert<\/a> the expression to postfix(or prefix) form before evaluation.<\/p>\n<p>The corresponding expression in postfix form is: abc*+d+. The postfix expressions can be evaluated easily using a stack. We will cover postfix expression<a href=\"https:\/\/www.wikitechy.com\/technology\/c-algorithm-evaluation-postfix-expression\/\"> evaluation<\/a> in a separate post.<\/p>\n[ad type=\u201dbanner\u201d]\n<h2 id=\"algorithm\"><span style=\"color: #ff6600;\"><strong>Algorithm<\/strong><\/span><\/h2>\n<p><strong>1.<\/strong> Scan the infix expression from left to right.<br \/>\n<strong>2.<\/strong> If the scanned <a href=\"https:\/\/www.wikitechy.com\/technology\/c-programming-for-pattern-searching-set-7-boyer-moore-algorithm-bad-character-heuristic-2\/\">character<\/a> is an operand, output it.<br \/>\n<strong>3. <\/strong>Else,<br \/>\n\u2014-><strong>3.1<\/strong> If the precedence of the scanned operator is greater than the precedence of the operator in the stack(or the stack is empty), push it.<br \/>\n\u2014\u2013><strong>3.2<\/strong> Else, Pop the operator from the stack until the precedence of the scanned operator is less-equal to the <a href=\"https:\/\/www.wikitechy.com\/technology\/c-programming-efficient-way-multiply-7\/\">precedence<\/a> of the operator residing on the top of the stack. Push the scanned operator to the stack.<br \/>\n<strong>4.<\/strong> If the scanned character is an \u2018(\u2018, push it to the stack.<br \/>\n<strong>5.<\/strong> If the scanned character is an \u2018)\u2019, pop and output from the stack until an \u2018(\u2018 is encountered.<br \/>\n<strong>6.<\/strong> Repeat steps 2-6 until infix expression is scanned.<br \/>\n<strong>7. <\/strong>Pop and output from the stack until it is not empty.<\/p>\n<p><span style=\"color: #008000;\"><strong>Following is C implementation of the above algorithm<\/strong><\/span><\/p>\n<p><strong>Python Programming:<\/strong><\/p>\n[pastacode lang=\u201dpython\u201d manual=\u201d%23%20Python%20program%20to%20convert%20infix%20expression%20to%20postfix%0A%20%0A%23%20Class%20to%20convert%20the%20expression%0Aclass%20Conversion%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%20%20%20%23%20Precedence%20setting%0A%20%20%20%20%20%20%20%20self.output%20%3D%20%5B%5D%0A%20%20%20%20%20%20%20%20self.precedence%20%3D%20%7B\u2019%2B\u2019%3A1%2C%20\u2032-\u2018%3A1%2C%20\u2019*\u2019%3A2%2C%20\u2019%2F\u2019%3A2%2C%20\u2019%5E\u2019%3A3%7D%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%20%20%20%23%20A%20utility%20function%20to%20check%20is%20the%20given%20character%0A%20%20%20%20%23%20is%20operand%20%0A%20%20%20%20def%20isOperand(self%2C%20ch)%3A%0A%20%20%20%20%20%20%20%20return%20ch.isalpha()%0A%20%0A%20%20%20%20%23%20Check%20if%20the%20precedence%20of%20operator%20is%20strictly%0A%20%20%20%20%23%20less%20than%20top%20of%20stack%20or%20not%0A%20%20%20%20def%20notGreater(self%2C%20i)%3A%0A%20%20%20%20%20%20%20%20try%3A%0A%20%20%20%20%20%20%20%20%20%20%20%20a%20%3D%20self.precedence%5Bi%5D%0A%20%20%20%20%20%20%20%20%20%20%20%20b%20%3D%20self.precedence%5Bself.peek()%5D%0A%20%20%20%20%20%20%20%20%20%20%20%20return%20True%20if%20a%20%20%3C%3D%20b%20else%20False%0A%20%20%20%20%20%20%20%20except%20KeyError%3A%20%0A%20%20%20%20%20%20%20%20%20%20%20%20return%20False%0A%20%20%20%20%20%20%20%20%20%20%20%20%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%20infixToPostfix(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%23%20If%20the%20character%20is%20an%20operand%2C%20%0A%20%20%20%20%20%20%20%20%20%20%20%20%23%20add%20it%20to%20output%0A%20%20%20%20%20%20%20%20%20%20%20%20if%20self.isOperand(i)%3A%0A%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20self.output.append(i)%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%20character%20is%20an%20\u2032(\u2018%2C%20push%20it%20to%20stack%0A%20%20%20%20%20%20%20%20%20%20%20%20elif%20i%20%20%3D%3D%20\u2032(\u2018%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%20\u2019)\u2019%2C%20pop%20and%20%0A%20%20%20%20%20%20%20%20%20%20%20%20%23%20output%20from%20the%20stack%20until%20and%20\u2032(\u2018%20is%20found%0A%20%20%20%20%20%20%20%20%20%20%20%20elif%20i%20%3D%3D%20\u2019)\u2019%3A%0A%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20while(%20(not%20self.isEmpty())%20and%20self.peek()%20!%3D%20\u2032(\u2018)%3A%0A%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20a%20%3D%20self.pop()%0A%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20self.output.append(a)%0A%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20if%20(not%20self.isEmpty()%20and%20self.peek()%20!%3D%20\u2032(\u2018)%3A%0A%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20return%20-1%0A%20%20%20%20%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%20%20%20%20%20self.pop()%0A%20%0A%20%20%20%20%20%20%20%20%20%20%20%20%23%20An%20operator%20is%20encountered%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%20while(not%20self.isEmpty()%20and%20self.notGreater(i))%3A%0A%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20self.output.append(self.pop())%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%23%20pop%20all%20the%20operator%20from%20the%20stack%0A%20%20%20%20%20%20%20%20while%20not%20self.isEmpty()%3A%0A%20%20%20%20%20%20%20%20%20%20%20%20self.output.append(self.pop())%0A%20%0A%20%20%20%20%20%20%20%20print%20%22%22.join(self.output)%0A%20%0A%23%20Driver%20program%20to%20test%20above%20function%0Aexp%20%3D%20%22a%2Bb*(c%5Ed-e)%5E(f%2Bg*h)-i%22%0Aobj%20%3D%20Conversion(len(exp))%0Aobj.infixToPostfix(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[ad type=\u201dbanner\u201d]\n<p><strong>Output:<\/strong><\/p>\n<pre>abcd^e-fgh*+^*+i-<\/pre>\n<h2 id=\"\"><\/h2>\n<p>\u00a0<\/p>\n<p>\u00a0<\/p>\n<p>\u00a0<\/p>\n","protected":false},"excerpt":{"rendered":"<p>Python Algorithm &#8211; Infix to Postfix Conversion using Stack &#8211; Data Structure &#8211; Infix expression:The expression of the form a op b.<\/p>\n","protected":false},"author":1,"featured_media":31392,"comment_status":"open","ping_status":"open","sticky":false,"template":"","format":"standard","meta":{"footnotes":""},"categories":[1,73012,79607],"tags":[80023,80022,85583,80017,79891,79897,80016,85580,80020,85581,79893,80018,80021,80019,85582,85584,80015],"class_list":["post-26824","post","type-post","status-publish","format-standard","has-post-thumbnail","hentry","category-coding","category-data-structures","category-stack","tag-import-stack-python","tag-infix-to-postfix-algorithm","tag-infix-to-postfix-conversion-program-in-data-structure-in-c","tag-infix-to-postfix-conversion-using-python","tag-infix-to-postfix-conversion-using-stack-in-c","tag-infix-to-postfix-conversion-using-stack-in-java","tag-infix-to-postfix-conversion-using-stack-in-python","tag-infix-to-postfix-converter","tag-infix-to-postfix-program-in-python","tag-infix-to-postfix-questions","tag-infix-to-postfix-using-stack-c-code","tag-infix-to-prefix-conversion-in-python","tag-isidentifier-python","tag-postfix-evaluation-in-python","tag-postfix-to-prefix-conversion","tag-prefix-to-postfix-conversion-using-stack-in-data-structure","tag-python-infix-to-postfix-code"],"_links":{"self":[{"href":"https:\/\/www.wikitechy.com\/technology\/wp-json\/wp\/v2\/posts\/26824","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=26824"}],"version-history":[{"count":0,"href":"https:\/\/www.wikitechy.com\/technology\/wp-json\/wp\/v2\/posts\/26824\/revisions"}],"wp:featuredmedia":[{"embeddable":true,"href":"https:\/\/www.wikitechy.com\/technology\/wp-json\/wp\/v2\/media\/31392"}],"wp:attachment":[{"href":"https:\/\/www.wikitechy.com\/technology\/wp-json\/wp\/v2\/media?parent=26824"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/www.wikitechy.com\/technology\/wp-json\/wp\/v2\/categories?post=26824"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/www.wikitechy.com\/technology\/wp-json\/wp\/v2\/tags?post=26824"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}