Infix To Postfix Program In C

Here's the infix to postfix algorithm in c: 

1. Traversing the Expression: Scan the given infix expression from left to right and go character by character.
2. If the Scanned Character is an Operand: Directly output the operand (e.g., A, B, 3, etc.) to the postfix expression.
3. If the Scanned Character is an Operator :
   • If the operator’s precedence is greater than the operator on top of the stack, or the stack is empty, or the top of the stack is a (, push the scanned operator onto the stack.
   • Operator Precedence: Operators like * and / have higher precedence over + and -. This step ensures that operators with higher precedence are handled first.
4. If the Scanned Operator has Lower or Equal Precedence:
   • While the operator at the top of the stack has greater than or equal precedence than the current operator, pop the stack and append each popped operator to the postfix expression.
   • After popping the operators with higher or equal precedence, push the current operator onto the stack.
5. Parentheses Handling: If you encounter a (, during popping, stop popping and push the scanned operator onto the stack.
6. If the Scanned Character is a Left Parenthesis (:
   • Push the ( onto the stack. This helps to keep track of the boundaries of sub-expressions. It ensures that operators are processed correctly within those bounds.
7. If the Scanned Character is a Right Parenthesis ):
   • Pop the stack and output each operator until a ( is encountered.
   • Eliminate both the ( and ) after processing.
   • This ensures that any operators inside parentheses are properly evaluated and placed in the correct order.
8. Repeat Steps 2 to 6: Continue scanning the entire expression, applying the above steps for each character.
9. End of Expression:
   • After the entire expression has been scanned, pop and print any remaining operators from the stack.
   • This step ensures that all operators are output in the correct postfix order.

Now let’s look at the infix to postfix program in C by two different approaches. 

1. Using an Array-Based Stack Approach 

Here’s how to implement infix to postfix conversion using stack in C

#include <limits.h>
#include <stdio.h>
#include <stdlib.h>
#define MAX 20

char stk[20];
int top = -1;

int isEmpty()  
{  
    return top == -1;  
}

int isFull()  
{  
    return top == MAX - 1;  
}

char peek()  
{  
    return stk[top];  
}

char pop()  
{  
    if (isEmpty())  
        return -1;  

    char ch = stk[top];  
    top--;  
    return(ch);  
}

void push(char oper)  
{  
    if (isFull())  
        printf("Stack Full!!!!");  
    else {  
        top++;  
        stk[top] = oper;  
    }  
}

int checkIfOperand(char ch)   
{   
    return (ch >= 'a' && ch <= 'z') || (ch >= 'A' && ch <= 'Z');   
}   

int precedence(char ch)   
{   
    switch (ch)   
    {   
    case '+':   
    case '-':   
        return 1;   
  
    case '*':   
    case '/':   
        return 2;   
  
    case '^':   
        return 3;   
    }   
    return -1;   
}

void convertInfixToPostfix(char* expression)   
{   
    int i, j = 0;
    char postfix[MAX];

    for (i = 0; expression[i]; ++i)   
    {   
        if (checkIfOperand(expression[i]))   
            postfix[j++] = expression[i];   
  
        else if (expression[i] == '(')   
            push(expression[i]);   
  
        else if (expression[i] == ')')   
        {   
            while (!isEmpty() && peek() != '(')   
                postfix[j++] = pop();   
            if (!isEmpty() && peek() != '(')   
                return; // Invalid expression
            else  
                pop();   
        }  
        else   
        {   
            while (!isEmpty() && precedence(expression[i]) <= precedence(peek()))   
                postfix[j++] = pop();   
            push(expression[i]);   
        }   
    }   
  
    while (!isEmpty())   
        postfix[j++] = pop();   
  
    postfix[j] = '\0';   // Null-terminate the postfix expression

    printf("Postfix Expression: %s\n", postfix);   
}

int main()  
{  
    char expression[] = "((x+(y*z))-w)";   
    convertInfixToPostfix(expression);   
    return 0;   
}

Output:

xyz*+w-

2. Using Struct-Based Stack Approach

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

// Define the Stack structure
struct Stack {   
    int top;   
    int maxSize;  
    char* array;   // Change from int* to char* to store characters   
};   

// Function to create a stack
struct Stack* create(int max)   
{   
    struct Stack* stack = (struct Stack*)malloc(sizeof(struct Stack));   
    stack->maxSize = max;   
    stack->top = -1;   
    stack->array = (char*)malloc(stack->maxSize * sizeof(char)); // Allocate memory for char type
    return stack;   
}   

// Function to check if the stack is full
int isFull(struct Stack* stack)   
{   
    if (stack->top == stack->maxSize - 1)  
    {  
        printf("Will not be able to push, maxSize reached\n");  
    }  
    return stack->top == stack->maxSize - 1;   
}   

// Function to check if the stack is empty
int isEmpty(struct Stack* stack)   
{   
    return stack->top == -1;   
}  

// Function to push an item onto the stack
void push(struct Stack* stack, char item)   
{   
    if (isFull(stack))   
        return;   
    stack->array[++stack->top] = item;   
}  

// Function to pop an item from the stack
char pop(struct Stack* stack)   
{   
    if (isEmpty(stack))   
        return INT_MIN;  // Return INT_MIN if stack is empty
    return stack->array[stack->top--];   
}   

// Function to peek the top item of the stack
char peek(struct Stack* stack)   
{   
    if (isEmpty(stack))   
        return INT_MIN;  // Return INT_MIN if stack is empty
    return stack->array[stack->top];   
}   

// Function to check if a character is an operand
int checkIfOperand(char ch)   
{   
    return (ch >= 'a' && ch <= 'z') || (ch >= 'A' && ch <= 'Z');   
}

// Function to return the precedence of operators
int precedence(char ch)   
{   
    switch (ch)   
    {   
    case '+':   
    case '-':   
        return 1;   
  
    case '*':   
    case '/':   
        return 2;   
  
    case '^':   
        return 3;   
    }   
    return -1;   
}   

// Function to convert infix to postfix expression
int covertInfixToPostfix(char* expression)   
{   
    int i, j;   
  
    // Create a stack for the expression
    struct Stack* stack = create(strlen(expression));   
    if (!stack)  
        return -1;  // Return error if memory allocation fails
  
    // Traverse the expression character by character
    for (i = 0, j = -1; expression[i]; ++i)   
    {   
       // If the character is an operand, append it to the postfix expression
       if (checkIfOperand(expression[i]))   
            expression[++j] = expression[i];   
  
       // If the character is a left parenthesis
       else if (expression[i] == '(')   
            push(stack, expression[i]);   
  
       // If the character is a right parenthesis
        else if (expression[i] == ')')   
        {   
            // Pop from stack until we encounter a left parenthesis
            while (!isEmpty(stack) && peek(stack) != '(')   
                expression[++j] = pop(stack);   
            if (!isEmpty(stack) && peek(stack) != '(')   
                return -1;  // Return error if parentheses mismatch
            else  
                pop(stack);   
        }   
        else  
        {   
            // Pop operators from the stack if they have higher or equal precedence
            while (!isEmpty(stack) && precedence(expression[i]) <= precedence(peek(stack)))   
                expression[++j] = pop(stack);   
            push(stack, expression[i]);   
        }   
    }   
  
    // Pop remaining operators from the stack
    while (!isEmpty(stack))   
        expression[++j] = pop(stack);   
  
    expression[++j] = '\0';   
    printf("Postfix Expression: %s\n", expression);  // Output the postfix expression
    return 0;
}   

// Main function to test the conversion
int main()  
{  
    char expression[] = "((x+(y*z))-w)";   
    covertInfixToPostfix(expression);   
    return 0;   
}

Output:

xyz*+w-

• Postfix eliminates the need for parentheses. Therefore it simplifies expression notation.
• Operator precedence is built into the notation. It avoids ambiguity.
• Computers can evaluate postfix expressions using a stack without complex precedence rules.
• Postfix notation is easier for compilers to parse and process.
• The evaluation follows a uniform left-to-right order, which reduces computational complexity.

Understanding infix to prefix algorithm in C is a critical skill for any programmer. This concept not only strengthens your grasp of data structures like stacks but also lays the foundation for solving complex problems in compiler design and expression evaluation. It is also a popular topic in coding interviews, where questions often test your ability to convert expressions and evaluate postfix notation efficiently. Mastering this algorithm helps students write better code while improving problem-solving skills crucial for real-world programming challenges. To build your skills further, enroll in the CCBP 4.0 Academy now to start your professional journey in software engineering.

1. What is infix notation?

Infix notation is the standard way of writing mathematical expressions. It is where operators are placed between operands. Think of A + B as an example where the + sign is the operator and A and B are operands. 

2. What is postfix notation?

Postfix notation is also called Reverse Polish Notation (RPN). It places operators after operands. In the same example as above, it looks like AB+.

3. Why convert infix to postfix?

Postfix eliminates the need for parentheses and simplifies expression evaluation. It makes it easier for computers to process.

4. Which data structure is used in infix to postfix conversion?

The stack data structure is used to handle operators and parentheses during the conversion process.

5. Is Infix to Postfix important for coding interviews?

Infix to postfix conversion tests your understanding of stacks, operator precedence, and expression handling. Therefore, it is a common question in technical interviews.