{"id":26800,"date":"2017-12-24T15:19:58","date_gmt":"2017-12-24T09:49:58","guid":{"rendered":"https:\/\/www.wikitechy.com\/technology\/?p=26800"},"modified":"2017-12-24T15:19:58","modified_gmt":"2017-12-24T09:49:58","slug":"c-algorithm-infix-postfix-conversion-using-stack","status":"publish","type":"post","link":"https:\/\/www.wikitechy.com\/technology\/c-algorithm-infix-postfix-conversion-using-stack\/","title":{"rendered":"C Algorithm – Infix to Postfix Conversion using Stack"},"content":{"rendered":"

Infix expression:<\/strong>The expression of the form a op b. When an operator is in-between every pair of operands.<\/span><\/p>\n

Postfix expression:<\/strong>The expression of the form a b op. When an operator is followed for every pair of operands.<\/p>\n

Why postfix representation of the expression?<\/strong>
\nThe compiler scans the expression either from left to right or from right to left.<\/p>\n

Consider the below expression: a op1 b op2 c op3 d
\nIf op1 = +, op2 = *, op3 = +<\/p>\n

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

The repeated scanning makes it very in-efficient. It is better to convert the expression to postfix(or prefix) form before evaluation.<\/p>\n

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[ad type=\u201dbanner\u201d]\n

Algorithm<\/strong>
\n1.<\/strong> Scan the infix expression from left to right.
\n2.<\/strong> If the scanned character is an operand, output it.
\n3. <\/strong>Else,
\n\u2026..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.
\n\u2026..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.
\n4.<\/strong> If the scanned character is an \u2018(\u2018, push it to the stack.
\n5.<\/strong> If the scanned character is an \u2018)\u2019, pop and output from the stack until an \u2018(\u2018 is encountered.
\n6.<\/strong> Repeat steps 2-6 until infix expression is scanned.
\n7. <\/strong>Pop and output from the stack until it is not empty.<\/p>\n

Following is C implementation of the above algorithm<\/p>\n

C Programming:<\/strong><\/p>\n[pastacode lang=\u201dc\u201d manual=\u201d%23include%20%3Cstdio.h%3E%0A%23include%20%3Cstring.h%3E%0A%23include%20%3Cstdlib.h%3E%0A%20%0A%2F%2F%20Stack%20type%0Astruct%20Stack%0A%7B%0A%20%20%20%20int%20top%3B%0A%20%20%20%20unsigned%20capacity%3B%0A%20%20%20%20int*%20array%3B%0A%7D%3B%0A%20%0A%2F%2F%20Stack%20Operations%0Astruct%20Stack*%20createStack(%20unsigned%20capacity%20)%0A%7B%0A%20%20%20%20struct%20Stack*%20stack%20%3D%20(struct%20Stack*)%20malloc(sizeof(struct%20Stack))%3B%0A%20%0A%20%20%20%20if%20(!stack)%20%0A%20%20%20%20%20%20%20%20return%20NULL%3B%0A%20%0A%20%20%20%20stack-%3Etop%20%3D%20-1%3B%0A%20%20%20%20stack-%3Ecapacity%20%3D%20capacity%3B%0A%20%0A%20%20%20%20stack-%3Earray%20%3D%20(int*)%20malloc(stack-%3Ecapacity%20*%20sizeof(int))%3B%0A%20%0A%20%20%20%20if%20(!stack-%3Earray)%0A%20%20%20%20%20%20%20%20return%20NULL%3B%0A%20%20%20%20return%20stack%3B%0A%7D%0Aint%20isEmpty(struct%20Stack*%20stack)%0A%7B%0A%20%20%20%20return%20stack-%3Etop%20%3D%3D%20-1%20%3B%0A%7D%0Achar%20peek(struct%20Stack*%20stack)%0A%7B%0A%20%20%20%20return%20stack-%3Earray%5Bstack-%3Etop%5D%3B%0A%7D%0Achar%20pop(struct%20Stack*%20stack)%0A%7B%0A%20%20%20%20if%20(!isEmpty(stack))%0A%20%20%20%20%20%20%20%20return%20stack-%3Earray%5Bstack-%3Etop\u2013%5D%20%3B%0A%20%20%20%20return%20\u2019%24\u2019%3B%0A%7D%0Avoid%20push(struct%20Stack*%20stack%2C%20char%20op)%0A%7B%0A%20%20%20%20stack-%3Earray%5B%2B%2Bstack-%3Etop%5D%20%3D%20op%3B%0A%7D%0A%20%0A%20%0A%2F%2F%20A%20utility%20function%20to%20check%20if%20the%20given%20character%20is%20operand%0Aint%20isOperand(char%20ch)%0A%7B%0A%20%20%20%20return%20(ch%20%3E%3D%20\u2019a\u2019%20%26%26%20ch%20%3C%3D%20\u2019z\u2019)%20%7C%7C%20(ch%20%3E%3D%20\u2019A\u2019%20%26%26%20ch%20%3C%3D%20\u2019Z\u2019)%3B%0A%7D%0A%20%0A%2F%2F%20A%20utility%20function%20to%20return%20precedence%20of%20a%20given%20operator%0A%2F%2F%20Higher%20returned%20value%20means%20higher%20precedence%0Aint%20Prec(char%20ch)%0A%7B%0A%20%20%20%20switch%20(ch)%0A%20%20%20%20%7B%0A%20%20%20%20case%20\u2019%2B\u2019%3A%0A%20%20%20%20case%20\u2032-\u2018%3A%0A%20%20%20%20%20%20%20%20return%201%3B%0A%20%0A%20%20%20%20case%20\u2019*\u2019%3A%0A%20%20%20%20case%20\u2019%2F\u2019%3A%0A%20%20%20%20%20%20%20%20return%202%3B%0A%20%0A%20%20%20%20case%20\u2019%5E\u2019%3A%0A%20%20%20%20%20%20%20%20return%203%3B%0A%20%20%20%20%7D%0A%20%20%20%20return%20-1%3B%0A%7D%0A%20%0A%20%0A%2F%2F%20The%20main%20function%20that%20converts%20given%20infix%20expression%0A%2F%2F%20to%20postfix%20expression.%20%0Aint%20infixToPostfix(char*%20exp)%0A%7B%0A%20%20%20%20int%20i%2C%20k%3B%0A%20%0A%20%20%20%20%2F%2F%20Create%20a%20stack%20of%20capacity%20equal%20to%20expression%20size%20%0A%20%20%20%20struct%20Stack*%20stack%20%3D%20createStack(strlen(exp))%3B%0A%20%20%20%20if(!stack)%20%2F%2F%20See%20if%20stack%20was%20created%20successfully%20%0A%20%20%20%20%20%20%20%20return%20-1%20%3B%0A%20%0A%20%20%20%20for%20(i%20%3D%200%2C%20k%20%3D%20-1%3B%20exp%5Bi%5D%3B%20%2B%2Bi)%0A%20%20%20%20%7B%0A%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%20if%20(isOperand(exp%5Bi%5D))%0A%20%20%20%20%20%20%20%20%20%20%20%20exp%5B%2B%2Bk%5D%20%3D%20exp%5Bi%5D%3B%0A%20%20%20%20%20%20%20%20%20%0A%20%20%20%20%20%20%20%20%2F%2F%20If%20the%20scanned%20character%20is%20an%20%E2%80%98(%E2%80%98%2C%20push%20it%20to%20the%20stack.%0A%20%20%20%20%20%20%20%20else%20if%20(exp%5Bi%5D%20%3D%3D%20\u2032(\u2018)%0A%20%20%20%20%20%20%20%20%20%20%20%20push(stack%2C%20exp%5Bi%5D)%3B%0A%20%20%20%20%20%20%20%20%20%0A%20%20%20%20%20%20%20%20%2F%2F%20If%20the%20scanned%20character%20is%20an%20%E2%80%98)%E2%80%99%2C%20pop%20and%20output%20from%20the%20stack%20%0A%20%20%20%20%20%20%20%20%2F%2F%20until%20an%20%E2%80%98(%E2%80%98%20is%20encountered.%0A%20%20%20%20%20%20%20%20else%20if%20(exp%5Bi%5D%20%3D%3D%20\u2032)\u2019)%0A%20%20%20%20%20%20%20%20%7B%0A%20%20%20%20%20%20%20%20%20%20%20%20while%20(!isEmpty(stack)%20%26%26%20peek(stack)%20!%3D%20\u2032(\u2018)%0A%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20exp%5B%2B%2Bk%5D%20%3D%20pop(stack)%3B%0A%20%20%20%20%20%20%20%20%20%20%20%20if%20(!isEmpty(stack)%20%26%26%20peek(stack)%20!%3D%20\u2032(\u2018)%0A%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20return%20-1%3B%20%2F%2F%20invalid%20expression%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%20else%0A%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20pop(stack)%3B%0A%20%20%20%20%20%20%20%20%7D%0A%20%20%20%20%20%20%20%20else%20%2F%2F%20an%20operator%20is%20encountered%0A%20%20%20%20%20%20%20%20%7B%0A%20%20%20%20%20%20%20%20%20%20%20%20while%20(!isEmpty(stack)%20%26%26%20Prec(exp%5Bi%5D)%20%3C%3D%20Prec(peek(stack)))%0A%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20exp%5B%2B%2Bk%5D%20%3D%20pop(stack)%3B%0A%20%20%20%20%20%20%20%20%20%20%20%20push(stack%2C%20exp%5Bi%5D)%3B%0A%20%20%20%20%20%20%20%20%7D%0A%20%0A%20%20%20%20%7D%0A%20%0A%20%20%20%20%2F%2F%20pop%20all%20the%20operators%20from%20the%20stack%0A%20%20%20%20while%20(!isEmpty(stack))%0A%20%20%20%20%20%20%20%20exp%5B%2B%2Bk%5D%20%3D%20pop(stack%20)%3B%0A%20%0A%20%20%20%20exp%5B%2B%2Bk%5D%20%3D%20\u2019%5C0\u2019%3B%0A%20%20%20%20printf(%20%22%25s%5Cn%22%2C%20exp%20)%3B%0A%7D%0A%20%0A%2F%2F%20Driver%20program%20to%20test%20above%20functions%0Aint%20main()%0A%7B%0A%20%20%20%20char%20exp%5B%5D%20%3D%20%22a%2Bb*(c%5Ed-e)%5E(f%2Bg*h)-i%22%3B%0A%20%20%20%20infixToPostfix(exp)%3B%0A%20%20%20%20return%200%3B%0A%7D%0A\u201d message=\u201d\u201d highlight=\u201d\u201d provider=\u201dmanual\u201d\/]\n

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

abcd^e-fgh*+^*+i-<\/pre>\n[ad type=\u201dbanner\u201d]\n","protected":false},"excerpt":{"rendered":"
C Algorithm – Infix to Postfix Conversion using Stack – Data Structure – 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,69866,1,79607],"tags":[79896,79892,79902,79899,79895,79894,79903,79898,79891,79904,79897,79901,79893,79890,79900,79905],"class_list":["post-26800","post","type-post","status-publish","format-standard","hentry","category-algorithm","category-c-programming","category-coding","category-stack","tag-algorithm-for-evaluation-of-postfix-expression","tag-algorithm-for-infix-to-postfix-conversion-using-stack-in-c","tag-c-program-to-convert-infix-to-postfix-and-evaluate-using-stack","tag-c-program-to-evaluate-postfix-expression","tag-infix-to-postfix-algorithm-geeksforgeeks","tag-infix-to-postfix-algorithm-java","tag-infix-to-postfix-conversion-algorithm","tag-infix-to-postfix-conversion-in-c-using-stack-examples","tag-infix-to-postfix-conversion-using-stack-in-c","tag-infix-to-postfix-conversion-using-stack-in-c-with-output","tag-infix-to-postfix-conversion-using-stack-in-java","tag-infix-to-postfix-program-in-c","tag-infix-to-postfix-using-stack-c-code","tag-infix-to-prefix-algorithm","tag-infix-to-prefix-program-in-c","tag-isalnum-in-c"],"_links":{"self":[{"href":"https:\/\/www.wikitechy.com\/technology\/wp-json\/wp\/v2\/posts\/26800","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=26800"}],"version-history":[{"count":0,"href":"https:\/\/www.wikitechy.com\/technology\/wp-json\/wp\/v2\/posts\/26800\/revisions"}],"wp:attachment":[{"href":"https:\/\/www.wikitechy.com\/technology\/wp-json\/wp\/v2\/media?parent=26800"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/www.wikitechy.com\/technology\/wp-json\/wp\/v2\/categories?post=26800"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/www.wikitechy.com\/technology\/wp-json\/wp\/v2\/tags?post=26800"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}