Infix To Postfix Program In C

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;   
}

Explanation

• Uses a fixed-size character array (stk[MAX]) to simulate a stack for storing operators.
• Scans each character in the infix expression:
  
  • Operands are added directly to the output (postfix).
  • Operators are pushed/popped from the stack based on precedence and parentheses.
• Handles ( and ) to maintain the correct order of operations and removes them after processing.
• Outputs the final postfix expression after popping any remaining operators from the stack.

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;   
}

Explanation

• Implements a dynamic stack using struct Stack with memory allocated using malloc().
• Stores operators dynamically — allowing variable-length expressions (more flexible than fixed-size arrays).
• The algorithm logic is the same: operands go to output, and operators are pushed/popped by precedence and parentheses rules.
• Directly modifies the input string to store the postfix expression, making it memory-efficient.

‍Output

xyz*+w-

Key Takeaways So Far

• Struct stack grows with input size — better for big expressions.
• Changes the input string directly (saves space).
• Same logic, just more flexible than an array.

• 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 the conversion from infix expression to postfix expression (also known as Reverse Polish Notation) is easier with concrete examples. Below, we walk through the process step by step, showing the stack status at each stage and highlighting how the infix-to-postfix (exp) algorithm works in practice.

Example 1: Simple Expression

Infix Expression
A + B * C

Step-by-Step Conversion:

1. Read 'A': Operand, add to postfix expression → Postfix: A
2. Read '+': Operator, push onto stack → Stack: [+]
3. Read 'B': Operand, add to postfix expression → Postfix: AB
4. Read '*': Operator, has higher precedence than '+', push onto stack → Stack: [+, *]
5. Read 'C': Operand, add to postfix expression → Postfix: ABC
6. End of expression: Pop operators from stack and add to postfix → Postfix: ABC*+

Postfix Expression
ABC*+

Example 2: Expression with Parentheses

Infix Expression
(a + b) * (c - d)

Step-by-Step Conversion:

1. Read '(': Push onto stack → Stack: [(]
2. Read 'a': Operand, add to postfix → Postfix: a
3. Read '+': Operator, push onto stack → Stack: [(, +]
4. Read 'b': Operand, add to postfix → Postfix: ab
5. Read ')': Pop and add to postfix until '(': → Postfix: ab+; Stack: []
6. Read '': Operator, push onto stack → Stack: []
7. Read '(': Push onto stack → Stack: [*, (]
8. Read 'c': Operand, add to postfix → Postfix: ab+c
9. Read '-': Operator, push onto stack → Stack: [*, (, -]
10. Read 'd': Operand, add to postfix → Postfix: ab+cd
11. Read ')': Pop and add to postfix until '(': → Postfix: ab+cd-; Stack: [*]
12. End of expression: Pop remaining operators → Postfix: ab+cd-*

Postfix Expression
ab+cd-*

Example 3: Evaluation of a Postfix Expression

After converting an infix expression to postfix, you can easily evaluate the postfix expression using a stack. For example, assess the postfix expression “82/3-” means:

1. Push 8 and 2 onto the stack.
2. Encounter '/', pop 8 and 2, compute 8/2 = 4, push 4.
3. Push 3 onto the stack.
4. Encounter '-', pop 4 and 3, compute 4-3 = 1, push 1.
5. Final result is 1.

Stack Status During Conversion

Throughout the infix-to-postfix (efficient solution) process, the stack temporarily holds operators and parentheses. This helps ensure that operator precedence and associativity are handled correctly, and that the final postfix expression can be evaluated from left to right without ambiguity.

Key Takeaways So Far

• Postfix advantages: parenthesis-free, stack-evaluable, O(n) time.
• Examples demonstrate precedence and parentheses handling.
• Manual tracing builds intuition for debugging.

Understanding the 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 and improve problem-solving skills crucial to 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.

Why It Matters?

Postfix is used in real compilers and AI math engines. It removes errors, speeds up code, and is a top interview question. Master it to stand out in tech jobs and build strong problem-solving skills.

Practical Advice for Learners

• Quiz Daily: Do 10 MCQs every day; aim for 90% correct.
• Hands-On: Run both codes; try inputs like A*(B+C) and trace step by step.
• Practice Tracing: Trace the stack and the output on paper for three new expressions each day.
• Fix Bugs: Change one part (like precedence) and see what breaks — learn from errors.
• Teach Someone: Explain the algorithm to a friend or write a short note — it sticks better.

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 evaluation. Therefore, it is a common question in technical interviews.