Program for Infix to Postfix Conversion in C

Back to: Data Structures and Algorithms Tutorials

Program for Infix to Postfix Conversion in C:

In this article, I will discuss the Program for Infix to Postfix Conversion in C Language with Examples. Please read our previous article discussing Infix to Postfix using Stack in C. So, now, we’ll discuss writing a function for converting infix expressions to postfix expressions. The function’s name is Convert(char *infix). It will take a character type pointer (*infix) to an array of characters.

Here, we have an array of size 10 containing the same expression (demonstrated in previous articles). Since it’s a string, it ends with a null character (\0). Our Convert function converts and returns a character pointer, essentially providing the postfix expression.

This is the basic precedence table. Now, for this procedure, we need two more functions: isOperand (char x) and int Pre (char x).

Function to Check Whether the Symbol is Operand or Not:

int isOperand (char x){
    if(x == '+' || x == '-' || x == '*' || x == '/')
        return 0;
    else 
        return 1;
}

This function will check whether the passed symbol is an operand or not. Inside the function, we check if x is equal to any of the operators +, -, *, or /; if so, it will return false or 0. Otherwise, if the symbol is an operand, the function will return true or 1. Next, we also need precedences.

Function that returns the precedence of the operator:

int pre (char x) {
    if(x == '+' || x == '-')
        return 1;
    else if(x == '*' || x == '/')
        return 2;
    return 0;
}

Here, we have a function ‘pre’ that stands for precedence. It will check if the symbol is ‘+’ or ‘-‘. It will return 1; if the symbol is ‘*’ or ‘/’, it will return 2, and for any other character, it will return 0.

So, we will use these functions in the Convert function, which is our main function for converting infix to postfix expressions. Inside the Convert function, we need a few things. First, we need a character-type stack. If you’ve read the parenthesis matching article, you’ll remember we initialized and used a character type stack. We do the same thing here.

struct Stack {
  int size;
  int top;
  char * S;
};

This is the structure of the Stack that we used in the parenthesis-matching article.

char * Convert (char *infix) {
}

This is the prototype of the Convert function. Let’s start writing the code for the Convert function. Assume that all the code is being written inside the Convert function.

struct Stack st;

Here, we declare a variable st of type Stack. This st will hold the expression’s characters or symbols.

st.size = strlen (infix);
st.top = -1;
st.S = (char *)malloc(st.size * sizeof(char));

Here, we initialize the stack st with a size equal to the length of the infix expression. The strlen function returns the length of the given string. We also initialize the top pointer to -1, which means the stack is empty. Then, we initialize the stack using the malloc function.

Now, we need a postfix array to store the result of the postfix expression. So, what will the size of the postfix array be? It will be the same as the infix array.

char *postfix = (char * ) malloc (sizeof(char) * (strlen (infix) + 1));

So, here, we have created an array postfix equal to the size of the infix array plus 1. We need a null character to end a string, which is why we added 1 to the length of the infix array. We declare a character type pointer postfix and initialize it by creating a new array from the heap. Now, we need a few variables to scan the infix array and the postfix array. So, we need two integer variables: i and j.

int i = 0, j = 0;

We’ve declared and initialized the variables i and j. Now, in the procedure, we have to scan through the infix expression from the first symbol until we reach the null character. So, for scanning, we can use a for loop that will iterate through the entire expression. However, instead of a for loop, we prefer to use a while loop. We’ll explain the reason later.

while (infix[i] != ‘\0’){

This while loop will run until we reach the null character. As per the procedure, we’re checking every symbol (operand or operator) in the expression. If it is an operand, we’ll add it to the postfix expression; if it is an operator, we’ll push it onto the stack. Let’s write inside the while loop.

if (isOperand (infix [i]))

To check whether the symbol is an operand, we’ve called the isOperand function. This function returns true if the given symbol is an operand. If this is the case, we should add that symbol or operand to the postfix expression. We will write a statement in the if-block to handle this situation.

postfix [j++] = infix[i++];

Here, the symbol that is present at the ith index in the infix array will be stored in the jth index in the postfix array. Then, both the i and j indices will be incremented. If the if-block condition fails, it means the symbol is an operator. In the case of operators, we have to check the precedence.

        else{
            if(pre(infix[i]) > pre(stackTop(st)))
                push(&st,infix[i++]);
            else
                postfix[j++] = pop(&st);
        }

In this else block, we have written if-else statements. In the if-block, we check if the precedence of the ith operator in the infix array is greater than the precedence of the topmost operator inside the stack. If this is the case, we push the ith operator from the infix array onto the stack st, then increment the ith index. In the else block, if the precedence of the infix symbol is lower or equal to the topmost operator present in the stack, we pop out that operator and add it to the postfix array. Finally, we increment the j index. As we have popped out, the ith index remains unchanged. It means we are at the same symbol in infix until it is pushed into the stack or directly moved to the postfix array.

Why haven’t we used For-Loop?

As we’re not moving i in every step, we used a while loop instead of a for loop. In a for loop, the i index will always be incremented automatically, but in a while loop, we can control when and how i is incremented.

If we reach the end of the expression and there are remaining operators inside the stack, they all need to be popped out and added to the postfix array. Let’s write the code for this.

….. (previous function code)….
while (!isEmpty (st)){
    	postfix[j++] = pop(&st);
    }
    postfix[j] = '\0';
    return postfix;
}

Here, we have written another while loop. This loop will continue running until the stack becomes empty. In each iteration, we pop out the topmost operator inside the stack and store that operator in the postfix array. Outside the loop, we have appended the null character (\0) to the postfix array. Finally, we return the postfix array. So, this is the function for converting the infix expression to a postfix expression in C language.

Complete Convert function in C Language:

int isOperand (char x){
    if(x == '+' || x == '-' || x == '*' || x == '/')
        return 0;
    else 
        return 1;
}

int pre (char x) {
    if(x == '+' || x == '-')
        return 1;
    else if(x == '*' || x == '/')
        return 2;
    return 0;
}

char * Convert (char *infix) {
    struct Stack st;
    st.size = strlen (infix);
    st.top = -1;
    st.S = (char *)malloc(st.size * sizeof(char));
    
    char *postfix = (char * ) malloc (sizeof(char) * (strlen (infix) + 1));
    int i = 0, j = 0;
    
    while (infix[i] != '\0'){
        if (isOperand (infix [i]))
            postfix [j++] = infix[i++];
        else{
            if(pre(infix[i]) > pre(stackTop(st)))
                push(&st,infix[i++]);
            else
                postfix[j++] = pop(&st);
        }
    }
    
    while (!isEmpty (st)){
    	postfix[j++] = pop(&st);
    }
    postfix[j] = '\0';
    return postfix;
}

Complete C Program to Convert Infix Expression to Postfix Expression:

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

struct Stack {
  int size;
  int top;
  char * S;
};

void create(struct Stack * st) {
  printf("Enter Size: ");
  scanf("%d", & st -> size);
  st -> top = -1;
  st -> S = (char * ) malloc(st -> size * sizeof(char));
}

void Display(struct Stack st) {
  int i;
  for (i = st.top; i >= 0; i--)
    printf("%d ", st.S[i]);
  printf("\n");
}

void push(struct Stack * st, int x) {
  if (st -> top == st -> size - 1)
    printf("Stack overflow\n");
  else {
    st -> top++;
    st -> S[st -> top] = x;
  }
}

int pop(struct Stack * st) {
  int x = -1;

  if (st -> top == -1)
    printf("Stack Underflow\n");
  else {
    x = st -> S[st -> top--];
  }
  return x;
}

int peek(struct Stack st, int index) {
  int x = -1;
  if (st.top - index + 1 < 0)
    printf("Invalid Index \n");
  x = st.S[st.top - index + 1];
  return x;
}

int isEmpty(struct Stack st) {
  if (st.top == -1)
    return 1;
  return 0;
}

int isFull(struct Stack st) {
  return st.top == st.size - 1;
}

int stackTop(struct Stack st) {
  if (!isEmpty(st))
    return st.S[st.top];
  return -1;
}

int isOperand (char x){
    if(x == '+' || x == '-' || x == '*' || x == '/')
        return 0;
    else 
        return 1;
}

int pre (char x) {
    if(x == '+' || x == '-')
        return 1;
    else if(x == '*' || x == '/')
        return 2;
    return 0;
}

char * Convert (char *infix) {
    struct Stack st;
    st.size = strlen (infix);
    st.top = -1;
    st.S = (char *)malloc(st.size * sizeof(char));
    
    char *postfix = (char * ) malloc (sizeof(char) * (strlen (infix) + 1));
    int i = 0, j = 0;
    
    while (infix[i] != '\0'){
        if (isOperand (infix [i]))
            postfix [j++] = infix[i++];
        else{
            if(pre(infix[i]) > pre(stackTop(st)))
                push(&st,infix[i++]);
            else
                postfix[j++] = pop(&st);
        }
    }
    
    while (!isEmpty (st)){
    	postfix[j++] = pop(&st);
    }
    postfix[j] = '\0';
    return postfix;
}

int main() {
  char* infix = "a+b*c-d/e\0";
  
  char* postfix = Convert (infix);
  
  printf("Infix Expression: %s\n", infix);
  printf("Postfix Expression: %s", postfix);
  
  return 0;
}

Output:

In the next article, I will discuss Queue Data Structure in C Language. In this article, I explain the Program for Infix to Postfix Conversion in C Language with examples. I hope you enjoy this article on the Program for Infix to Postfix Conversion in C Language.