{"id":26813,"date":"2017-12-24T15:24:24","date_gmt":"2017-12-24T09:54:24","guid":{"rendered":"https:\/\/www.wikitechy.com\/technology\/?p=26813"},"modified":"2017-12-24T15:24:24","modified_gmt":"2017-12-24T09:54:24","slug":"java-algorithm-infix-postfix-conversion-using-stack","status":"publish","type":"post","link":"https:\/\/www.wikitechy.com\/technology\/java-algorithm-infix-postfix-conversion-using-stack\/","title":{"rendered":"Java Algorithm &#8211; Infix to Postfix Conversion using Stack"},"content":{"rendered":"<p><strong>Infix expression:<\/strong>The expression of the form a op b. When an operator is in-between every pair of operands.<span id=\"more-142798\"><\/span><\/p>\n<p><strong>Postfix expression:<\/strong>The expression of the form a b op. When an operator is followed for every pair of operands.<\/p>\n<p><strong>Why postfix representation of the expression?<\/strong><br \/>\nThe compiler scans the expression either from left to right or from right to left.<\/p>\n<p>Consider the below expression: 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 convert 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 evaluation in a separate post.<\/p>\n<p><strong>Algorithm<\/strong><br \/>\n<strong>1.<\/strong> Scan the infix expression from left to right.<br \/>\n<strong>2.<\/strong> If the scanned character is an operand, output it.<br \/>\n<strong>3. <\/strong>Else,<br \/>\n\u2026..<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\u2026..<strong>3.2<\/strong> Else, Pop the operator from the stack until the precedence of the scanned operator is less-equal to the precedence 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[ad type=\u201dbanner\u201d]\n<p>Following is C implementation of the above algorithm<\/p>\n<p><strong>Java Programming:<\/strong><\/p>\n[pastacode lang=\u201djava\u201d manual=\u201d%2F*%20Java%20implementation%20to%20convert%20infix%20expression%20to%20postfix*%2F%0A%2F%2F%20Note%20that%20here%20we%20use%20Stack%20class%20for%20Stack%20operations%0A%20%0Aimport%20java.util.Stack%3B%0A%20%0Aclass%20Test%0A%7B%0A%20%20%20%20%2F%2F%20A%20utility%20function%20to%20return%20precedence%20of%20a%20given%20operator%0A%20%20%20%20%2F%2F%20Higher%20returned%20value%20means%20higher%20precedence%0A%20%20%20%20static%20int%20Prec(char%20ch)%0A%20%20%20%20%7B%0A%20%20%20%20%20%20%20%20switch%20(ch)%0A%20%20%20%20%20%20%20%20%7B%0A%20%20%20%20%20%20%20%20case%20\u2019%2B\u2019%3A%0A%20%20%20%20%20%20%20%20case%20\u2032-\u2018%3A%0A%20%20%20%20%20%20%20%20%20%20%20%20return%201%3B%0A%20%20%20%20%20%20%0A%20%20%20%20%20%20%20%20case%20\u2019*\u2019%3A%0A%20%20%20%20%20%20%20%20case%20\u2019%2F\u2019%3A%0A%20%20%20%20%20%20%20%20%20%20%20%20return%202%3B%0A%20%20%20%20%20%20%0A%20%20%20%20%20%20%20%20case%20\u2019%5E\u2019%3A%0A%20%20%20%20%20%20%20%20%20%20%20%20return%203%3B%0A%20%20%20%20%20%20%20%20%7D%0A%20%20%20%20%20%20%20%20return%20-1%3B%0A%20%20%20%20%7D%0A%20%20%20%20%20%20%0A%20%20%20%20%2F%2F%20The%20main%20method%20that%20converts%20given%20infix%20expression%0A%20%20%20%20%2F%2F%20to%20postfix%20expression.%20%0A%20%20%20%20static%20String%20infixToPostfix(String%20exp)%0A%20%20%20%20%7B%0A%20%20%20%20%20%20%20%20%2F%2F%20initializing%20empty%20String%20for%20result%0A%20%20%20%20%20%20%20%20String%20result%20%3D%20new%20String(%22%22)%3B%0A%20%20%20%20%20%20%20%20%20%0A%20%20%20%20%20%20%20%20%2F%2F%20initializing%20empty%20stack%0A%20%20%20%20%20%20%20%20Stack%3CCharacter%3E%20stack%20%3D%20new%20Stack%3C%3E()%3B%0A%20%20%20%20%20%20%20%20%20%0A%20%20%20%20%20%20%20%20for%20(int%20i%20%3D%200%3B%20i%3Cexp.length()%3B%20%2B%2Bi)%0A%20%20%20%20%20%20%20%20%7B%0A%20%20%20%20%20%20%20%20%20%20%20%20char%20c%20%3D%20exp.charAt(i)%3B%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%20%2F%2F%20If%20the%20scanned%20character%20is%20an%20operand%2C%20add%20it%20to%20output.%0A%20%20%20%20%20%20%20%20%20%20%20%20if%20(Character.isLetterOrDigit(c))%0A%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20result%20%2B%3D%20c%3B%0A%20%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%2F%2F%20If%20the%20scanned%20character%20is%20an%20\u2032(\u2018%2C%20push%20it%20to%20the%20stack.%0A%20%20%20%20%20%20%20%20%20%20%20%20else%20if%20(c%20%3D%3D%20\u2032(\u2018)%0A%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20stack.push(c)%3B%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%2F%2F%20%20If%20the%20scanned%20character%20is%20an%20\u2019)\u2019%2C%20pop%20and%20output%20from%20the%20stack%20%0A%20%20%20%20%20%20%20%20%20%20%20%20%2F%2F%20until%20an%20\u2032(\u2018%20is%20encountered.%0A%20%20%20%20%20%20%20%20%20%20%20%20else%20if%20(c%20%3D%3D%20\u2032)\u2019)%0A%20%20%20%20%20%20%20%20%20%20%20%20%7B%0A%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20while%20(!stack.isEmpty()%20%26%26%20stack.peek()%20!%3D%20\u2032(\u2018)%0A%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20result%20%2B%3D%20stack.pop()%3B%0A%20%20%20%20%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%20%20%20%20if%20(!stack.isEmpty()%20%26%26%20stack.peek()%20!%3D%20\u2032(\u2018)%0A%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20return%20%22Invalid%20Expression%22%3B%20%2F%2F%20invalid%20expression%20%20%20%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%20%20%20%20else%0A%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20stack.pop()%3B%0A%20%20%20%20%20%20%20%20%20%20%20%20%7D%0A%20%20%20%20%20%20%20%20%20%20%20%20else%20%2F%2F%20an%20operator%20is%20encountered%0A%20%20%20%20%20%20%20%20%20%20%20%20%7B%0A%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20while%20(!stack.isEmpty()%20%26%26%20Prec(c)%20%3C%3D%20Prec(stack.peek()))%0A%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20result%20%2B%3D%20stack.pop()%3B%0A%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20stack.push(c)%3B%0A%20%20%20%20%20%20%20%20%20%20%20%20%7D%0A%20%20%20%20%20%20%0A%20%20%20%20%20%20%20%20%7D%0A%20%20%20%20%20%20%0A%20%20%20%20%20%20%20%20%2F%2F%20pop%20all%20the%20operators%20from%20the%20stack%0A%20%20%20%20%20%20%20%20while%20(!stack.isEmpty())%0A%20%20%20%20%20%20%20%20%20%20%20%20result%20%2B%3D%20stack.pop()%3B%0A%20%20%20%20%20%20%0A%20%20%20%20%20%20%20%20return%20result%3B%0A%20%20%20%20%7D%0A%20%20%20%0A%20%20%20%20%2F%2F%20Driver%20method%20%0A%20%20%20%20public%20static%20void%20main(String%5B%5D%20args)%20%0A%20%20%20%20%7B%0A%20%20%20%20%20%20%20%20String%20exp%20%3D%20%22a%2Bb*(c%5Ed-e)%5E(f%2Bg*h)-i%22%3B%0A%20%20%20%20%20%20%20%20System.out.println(infixToPostfix(exp))%3B%0A%20%20%20%20%7D%0A%7D\u201d message=\u201d\u201d highlight=\u201d\u201d provider=\u201dmanual\u201d\/]\n<p><strong>Output:<\/strong><\/p>\n<pre>abcd^e-fgh*+^*+i-<\/pre>\n[ad type=\u201dbanner\u201d]\n","protected":false},"excerpt":{"rendered":"<p>Java 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":0,"comment_status":"open","ping_status":"open","sticky":false,"template":"","format":"standard","meta":{"footnotes":""},"categories":[69969,2139,79607],"tags":[79896,79892,79926,79895,79894,79927,79891,79893,79890],"class_list":["post-26813","post","type-post","status-publish","format-standard","hentry","category-algorithm","category-java","category-stack","tag-algorithm-for-evaluation-of-postfix-expression","tag-algorithm-for-infix-to-postfix-conversion-using-stack-in-c","tag-algorithm-to-convert-infix-to-postfix-expression-in-data-structure","tag-infix-to-postfix-algorithm-geeksforgeeks","tag-infix-to-postfix-algorithm-java","tag-infix-to-postfix-algorithm-with-parentheses","tag-infix-to-postfix-conversion-using-stack-in-c","tag-infix-to-postfix-using-stack-c-code","tag-infix-to-prefix-algorithm"],"_links":{"self":[{"href":"https:\/\/www.wikitechy.com\/technology\/wp-json\/wp\/v2\/posts\/26813","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=26813"}],"version-history":[{"count":0,"href":"https:\/\/www.wikitechy.com\/technology\/wp-json\/wp\/v2\/posts\/26813\/revisions"}],"wp:attachment":[{"href":"https:\/\/www.wikitechy.com\/technology\/wp-json\/wp\/v2\/media?parent=26813"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/www.wikitechy.com\/technology\/wp-json\/wp\/v2\/categories?post=26813"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/www.wikitechy.com\/technology\/wp-json\/wp\/v2\/tags?post=26813"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}