Infix To Postfix Using Stack

Infix To Postfix Using Stack

In the last docs, we learned to convert an infix expression to its postfix and prefix equivalents manually. The simple steps we followed were:

1. Parenthesize the expression according to operators’ precedence and their associativity.
2. Convert the expressions from innermost to outermost.

However, we didn’t discuss their implementation using stacks. Today, we will learn how to convert an infix expression into its postfix equivalent using stacks.

Converting an infix expression to its postfix counterpart requires the following steps:

1. Start moving left to right from the beginning of the expression.
2. When you encounter an operand, concatenate it to the postfix expression string.
3. Upon encountering an operator, check the stack. If the topmost operator in the stack has lower precedence, push the current operator onto the stack. If it has higher precedence, pop operators from the stack and concatenate them to the postfix expression until the topmost operator has lower precedence than the current operator.
4. Upon reaching the end of the expression (EOE), pop every element from the stack and concatenate them. The resulting expression will be the postfix equivalent of the original expression.

For our understanding today, let us consider the expression x - y / z - k * a. Step by step, we will turn this expression into its postfix equivalent using stacks.

1. We will start traversing from the left.

2. First, we got the letter ‘x’. We just pushed it into the postfix string. Then we got the subtraction symbol ‘-’, and we push it into the stack since the stack is empty.

3. Similarly, we push the division operator in the stack since the topmost operator has a precedence number 1, and the division has 2.

4. The next operator we encounter is again a subtraction. Since the topmost operator in the stack has an operator precedence number 2, we would pop elements out from the stack until we can push the current operator. This leads to removing both the present operators in the stack since they are both greater or equal in precedence. Don’t forget to concatenate the popped operators to the postfix expression.

5. Next, we have a multiplication operator whose precedence number is 2 relative to the topmost operator in the stack. Hence we simply push it in the stack.

6. And then we get to the EOE and still have two elements inside the stack. So, just pop them one by one, and concatenate them to the postfix. And this is when we succeed in converting the infix to the postfix expression.

Infix To Postfix Using Stack

Follow every step meticulously, and you will find it very easy to master this process. You can verify if the final answer is correct manually.

• Example Conversion:
  x - y / z - k * a → (( x - ( y / z )) - ( k * a )) → (( x - [ y z / ]) - [ k a * ]) → [ x y z / - ] - [ k a * ] → x y z / - k a * -

And it is indeed a correct conversion. Now, I would like you to follow the same steps and convert the expression x + y * z - k, using the stack method, and verify your answer manually using parentheses.

This was a visualization of the conversion process of infix to postfix using stacks. We will see the programming part in the next docs. It would be beneficial if you practiced converting a few expressions on your own. If you still feel unsure about using stacks, please check out the previous docs where we discussed stacks in detail.

Coding Infix to Postfix in C using Stack

We previously saw how infix expressions can be converted to their other equivalents manually. When it comes to automating the process, we utilize stacks to manage the operators encountered in the expression. We follow an algorithm to convert an infix expression to its postfix equivalent, summarized as follows:

1. Create a string variable to hold the postfix expression. Start moving from left to right. When you receive an operand, concatenate it to the postfix string. Upon encountering an operator, follow these steps:

   • Consider the operator and its relative precedence.
   • If the stack is empty or its topmost operator has lower relative precedence, push this operator-precedence pair onto the stack.
   • Else, pop operators from the stack and concatenate them to the postfix expression until the topmost operator has lower precedence than the current operator.

2. Upon reaching the end of the expression (EOE), pop every element from the stack (if any) and concatenate them. You will then have your postfix expression.

Understanding the Program for Infix to Postfix Conversion

1. Create a character pointer function infixToPostfix since the function must return a character array. Pass the given expression (also a character pointer) into this function.

2. Define a struct stack pointer variable sp. Allocate the required memory in the heap and create the instance. Assume that a struct stack element and all its basic operations (push, pop, etc.) have already been defined. It is advisable to copy everything from the stack docs.

3. Create a character array/pointer postfix and assign sufficient memory in the heap to hold all characters of the infix expression.

4. Create two counters: one to traverse the infix expression and another to insert elements into the postfix expression. Refer to the illustration below, which describes the initial conditions.

5. Run a while loop until you reach the end of the expression (EOE) of the infix. Inside that loop, check if the current index holds an operator. If it does not, add that character to the postfix and increment both counters by 1. If it does hold an operator, call another function to check if the precedence of the stack's top operator is less than the precedence of the current operator. If yes, push the current operator onto the stack. Otherwise, pop the top operator from the stack and add it back into the postfix. Increment the counter for the postfix expression (j) by 1.

char* infixToPostfix(char* infix){
    struct stack * sp = (struct stack *) malloc(sizeof(struct stack));
    sp->size = 10; 
    sp->top = -1;
    sp->arr = (char *) malloc(sp->size * sizeof(char));
    char * postfix = (char *) malloc((strlen(infix)+1) * sizeof(char));
    int i=0; // Track infix traversal
    int j = 0; // Track postfix addition 
    while (infix[i]!='\0')
    {
        if(!isOperator(infix[i])){
            postfix[j] = infix[i];
            j++;
            i++;
        }
        else{
            if(precedence(infix[i])> precedence(stackTop(sp))){
                push(sp, infix[i]);
                i++;
            }
            else{
                postfix[j] = pop(sp);
                j++;
            }
        }
    }
    while (!isEmpty(sp))    
    {
        postfix[j] = pop(sp);
        j++;
    }
    postfix[j] = '\0';
    return postfix;
}

Code Snippet 1: Creating the function infixToPostfix

6. Now, create two functions to facilitate the conversion: isOperator and precedence. The isOperator function checks if a character is an operator, while the precedence function compares the precedence of two operators.

7. Create an integer function isOperator that takes a character as its parameter. This function should return 1 if the character is an operator and 0 otherwise.

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

Code Snippet 2: Creating the function isOperator

8. Create another integer function precedence that takes a character as its parameter and returns its relative precedence. This function should return 3 for the operators ‘/’ or ‘*’, and 2 for ‘+’ or ‘-’.

9. Finally, if any elements remain in the stack at the end of the conversion process, pop them all and append them to the postfix expression.

int precedence(char ch){
    if(ch == '*' || ch=='/')
        return 3;
    else if(ch == '+' || ch=='-')
        return 2; 
    else
        return 0;
}

Code Snippet 3: Creating the function precedence

Here is the whole source code:

#include <stdio.h>
#include <stdlib.h>
#include <string.h>
 
struct stack
{
    int size;
    int top;
    char *arr;
};
 
int stackTop(struct stack* sp){
    return sp->arr[sp->top];
}
 
int isEmpty(struct stack *ptr)
{
    if (ptr->top == -1)
    {
        return 1;
    }
    else
    {
        return 0;
    }
}
 
int isFull(struct stack *ptr)
{
    if (ptr->top == ptr->size - 1)
    {
        return 1;
    }
    else
    {
        return 0;
    }
}
 
void push(struct stack* ptr, char val){
    if(isFull(ptr)){
        printf("Stack Overflow! Cannot push %d to the stack\n", val);
    }
    else{
        ptr->top++;
        ptr->arr[ptr->top] = val;
    }
}
 
char pop(struct stack* ptr){
    if(isEmpty(ptr)){
        printf("Stack Underflow! Cannot pop from the stack\n");
        return -1;
    }
    else{
        char val = ptr->arr[ptr->top];
        ptr->top--;
        return val;
    }
}
int precedence(char ch){
    if(ch == '*' || ch=='/')
        return 3;
    else if(ch == '+' || ch=='-')
        return 2; 
    else
        return 0;
}
 
int isOperator(char ch){
    if(ch=='+' || ch=='-' ||ch=='*' || ch=='/') 
        return 1;
    else
        return 0;
}
char* infixToPostfix(char* infix){
    struct stack * sp = (struct stack *) malloc(sizeof(struct stack));
    sp->size = 10; 
    sp->top = -1;
    sp->arr = (char *) malloc(sp->size * sizeof(char));
    char * postfix = (char *) malloc((strlen(infix)+1) * sizeof(char));
    int i=0; // Track infix traversal
    int j = 0; // Track postfix addition 
    while (infix[i]!='\0')
    {
        if(!isOperator(infix[i])){
            postfix[j] = infix[i];
            j++;
            i++;
        }
        else{
            if(precedence(infix[i])> precedence(stackTop(sp))){
                push(sp, infix[i]);
                i++;
            }
            else{
                postfix[j] = pop(sp);
                j++;
            }
        }
    }
    while (!isEmpty(sp))    
    {
        postfix[j] = pop(sp);
        j++;
    }
    postfix[j] = '\0';
    return postfix;
}
int main()
{
    char * infix = "x-y/z-k*d";
    printf("postfix is %s", infixToPostfix(infix));
    return 0;
}

Code Snippet 4: Source code for the function infixToPostfix

    char * infix = "x-y/z-k*d";
    printf("postfix is %s", infixToPostfix(infix));

Code Snippet 5: Calling the function infixToPostfix

postfix is xyz/-kd*-
PS D:\Code>

Figure 1: Output of the above program