Infix to Postfix program in C | Easy Explantion with 5 Steps.

Posted on by

Infix to Postfix program in C.

Question link: Infix to Postfix Program in C  Geeksforgeeks.

For Beginners step-by-step procedure to solve this Infix to Postfix Program in C.

  • Understand the question
  • Try to think of other test cases than present in the question.
  • Try to write a pseudo code for it.

Question:

Convert an infix expression (expression of Type a+b-c*d ) to and postfix expression (expression of Type ab+ddf/*-g+ ).

Input:

A string/ char[] which contains the infix expression.

Output:

Infix expression to Postfix expression.

Solution for Infix to Postfix expression in C:

Hint 1: Create a condition when scanning an operand(1,5,2,5 .. ) or operator(^,+,- .)

Hint 2: Consider the Precedence of operators.

Intuition for Infix to Postfix expression in C:  Keep Scanning the characters in infix expression from left to right order. While evaluating a postfix expression the operators on the right side are performed to the immediate left two operands

Important: We will be using an array-based stack method. C doesn’t support a stl library like C++. Hence we will be using a stack index which will point to the rightmost present element in the array since the stack always points to the topmost element only. Always we will be using char[] since string is not supported in C.

Steps to Solve Infix to Postfix program in C:

  1. Scan the infix expression from left to right using a loop.
  2. If the scanned character is an operand(1,3,4,2 ..) , append it to the postfix expression.
  3. Else (the scanned character is an operator):
    • Check the precedence of the scanned operator is greater than the current operator in the stack, or it is empty, or it is a ‘(‘, then add the current scanned operator to the stack.
    • For all other cases, pop the element from the stack and append it to the postfix expression.
  4. The case for ( and ).
    • For (: Push it to the stack;
    • For ): Pop the characters from the stack until a ( is not found;
  5. While the stack is not empty, pop all the characters and add to the postfix expression.

 

Infix to Postfix program in C :

#include<stdio.h>
#include<stdlib.h>
#include<string.h>

int precedence_check(char op)
{  
      switch(op):
      case '+':
      case '-':
          return 0; // if (op == + || op == -) return 0;
      case '*':
      case '/':
          return 1; // if (op == * || op == /) return 1;
      case '^':
          return 2; // If (op == ^) return 2;
      default:
          return -1; // else return -1;
}

int operator_check(char op)
{
   return (op == '+' || op== '-' || op== '*' || op== '/' || ch == '^');
}

char* infixToPostfix(char* infix)
{
    int i, j;
    int len = strlen(infix);
    char* postfix = (char*)malloc(sizeof(char) * (len + 2));
    char stack[len+2];
    int stindex= -1;
  
    for (i = 0, j = 0; i < len; i++) { 
            if (infix[i] == ' ' || infix[i] == '\t') continue; 
            if (isalnum(infix[i])) { postfix[j++] = infix[i]; } 
            else if (infix[i] == '(') 
                 { stack[++stindex] = infix[i]; 
                 } 
             else if (infix[i] == ')') 
              { 
             while (stindex> -1 && stack[stindex] != '(')
                {
                   postfix[j++] = stack[stindex--];
                }
             if (top > -1 && stack[stindex] != '(')
                { 
                   return "Invalid Expression";
                }
            else{
                stindex--;
               }
        }
        else if (operator_check(infix[i])) {
            while (stindex> -1
                   && precedence_check(stack[stindex])
                          >= precedence_check(infix[i]))
                postfix[j++] = stack[stindex--];
            stack[++stindex] = infix[i];
        }
    }
  
    while (stindex> -1) {
        if (stack[stindex] == '(') {
            return "Invalid Expression";
        }
        postfix[j++] = stack[stindex--];
    }
    postfix[j] = '\0';
    return postfix;
}

int main()
{
    char infix[10000] = "a+b*(c^d-e)^(f+g*h)-i";
    char* postfix = infixToPostfix(infix);
    printf("%s\n", postfix);
    return 0;
}

 

Thank You!

Visit to See More Coding Solutions.

CSES Longest Flight Route Solution