{"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=”banner”]\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

<\/div> 
#include <stdio.h>#include <string.h>#include <stdlib.h> \/\/ Stack typestruct Stack{    int top;    unsigned capacity;    int* array;}; \/\/ Stack Operationsstruct Stack* createStack( unsigned capacity ){    struct Stack* stack = (struct Stack*) malloc(sizeof(struct Stack));     if (!stack)         return NULL;     stack->top = -1;    stack->capacity = capacity;     stack->array = (int*) malloc(stack->capacity * sizeof(int));     if (!stack->array)        return NULL;    return stack;}int isEmpty(struct Stack* stack){    return stack->top == -1 ;}char peek(struct Stack* stack){    return stack->array[stack->top];}char pop(struct Stack* stack){    if (!isEmpty(stack))        return stack->array[stack->top--] ;    return '$';}void push(struct Stack* stack, char op){    stack->array[++stack->top] = op;}  \/\/ A utility function to check if the given character is operandint isOperand(char ch){    return (ch >= 'a' && ch <= 'z') || (ch >= 'A' && ch <= 'Z');} \/\/ A utility function to return precedence of a given operator\/\/ Higher returned value means higher precedenceint Prec(char ch){    switch (ch)    {    case '+':    case '-':        return 1;     case '*':    case '\/':        return 2;     case '^':        return 3;    }    return -1;}  \/\/ The main function that converts given infix expression\/\/ to postfix expression. int infixToPostfix(char* exp){    int i, k;     \/\/ Create a stack of capacity equal to expression size     struct Stack* stack = createStack(strlen(exp));    if(!stack) \/\/ See if stack was created successfully         return -1 ;     for (i = 0, k = -1; exp[i]; ++i)    {        \/\/ If the scanned character is an operand, add it to output.        if (isOperand(exp[i]))            exp[++k] = exp[i];                 \/\/ If the scanned character is an \u2018(\u2018, push it to the stack.        else if (exp[i] == '(')            push(stack, exp[i]);                 \/\/ If the scanned character is an \u2018)\u2019, pop and output from the stack         \/\/ until an \u2018(\u2018 is encountered.        else if (exp[i] == ')')        {            while (!isEmpty(stack) && peek(stack) != '(')                exp[++k] = pop(stack);            if (!isEmpty(stack) && peek(stack) != '(')                return -1; \/\/ invalid expression                         else                pop(stack);        }        else \/\/ an operator is encountered        {            while (!isEmpty(stack) && Prec(exp[i]) <= Prec(peek(stack)))                exp[++k] = pop(stack);            push(stack, exp[i]);        }     }     \/\/ pop all the operators from the stack    while (!isEmpty(stack))        exp[++k] = pop(stack );     exp[++k] = '\\0';    printf( "%s\\n", exp );} \/\/ Driver program to test above functionsint main(){    char exp[] = "a+b*(c^d-e)^(f+g*h)-i";    infixToPostfix(exp);    return 0;}<\/code><\/pre> <\/div>\n
Output:<\/strong><\/p>\n
abcd^e-fgh*+^*+i-<\/pre>\n[ad type=”banner”]\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}]}}