DS Menu

Infix to Postfic Converstion

Converting an infix expression to a postfix expression using a stack involves a few steps and rules. The primary reason for this conversion is that postfix expressions are easier to evaluate programmatically without the need for maintaining operator precedence and parentheses.

The algorithm for this conversion is known as the Shunting Yard Algorithm, devised by Edsger Dijkstra. This algorithm efficiently handles the conversion by dealing with operator precedence and parentheses.

Algorithm Converting an infix expression to a postfix expression

1. Initialize an Empty Stack: The stack is used to keep track of operators and parentheses.

2. Iterate Through the Infix Expression:

Operand: If the character is an operand (number or letter), add it directly to the output (postfix expression).
Left Parenthesis: If the character is a '(', push it onto the stack.
Right Parenthesis: If the character is a ')', pop from the stack and add to the output until a '(' is encountered. Discard the pair of parentheses.
Operator: If the character is an operator (like +, -, *, /):
- While there is an operator at the top of the stack with greater or equal precedence, pop it and add it to the output.
- Then push the current operator onto the stack.

3. Empty the Stack: After iterating through the expression, pop and add all remaining operators from the stack to the output.

Example to Convert the infix expression A * (B + C) / D to postfix.

infix expression	Stack	postfix expression	Explanation
A * (B + C) / D
* (B + C) / D		A	A: Operand, Add to output
(B + C) / D	*	A	*: Operator, Push onto stack
B + C) / D	( *	A	(: Left Parenthesis → Push onto stack
+ C) / D	( *	AB	B: Operand → Add to output
C) / D	+ ( *	AB	+: Operator → Push onto stack
) / D	+ ( *	ABC	C: Operand → Add to output
/ D	*	ABC+	): Right Parenthesis → Pop until '(' is encountered
D	/ *	ABC+	/: Operator → Push onto stack
	/ *	ABC+D	D: Operand → Add to output
	*	ABC+D/	Pop / operators and add to output
		ABC+D/*	Pop * operators and add to output

C Program to Converting an infix expression to a postfix expression

Program:

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

#define MAX 15

char stack[MAX];
int top = -1;

// Function to push an element to the stack
void push(char item) {
    if(top >= MAX-1) {
        printf("\nStack Overflow.");
    } else {
        stack[++top] = item;
    }
}

// Function to pop an element from the stack
char pop() {
    if(top < 0) {
        printf("Stack Underflow.");
        exit(1);
    } else {
        return stack[top--];
    }
}

// Function to return precedence of operators
int precedence(char symbol) {
    switch(symbol) {
        case '+': return 3;
        case '-': return 2;
        case '*': return 4;
        case '/': return 5;
        case '(': 
        case ')': return 1;
        default : return 0;
    }
}

// Function to convert infix to postfix
void infixToPostfix(char infix[], char postfix[]) {
    int i, j = 0;
    char item, x;

    push('(');                // Add '(' to infix expression
    strcat(infix, ")");       // Add ')' to infix expression

    for(i = 0; infix[i] != '\0'; i++) {
        item = infix[i];
        if(item == '(') {
            push(item);
        } else if(isalnum(item)) {
            postfix[j++] = item;  // Add operand to postfix
        } else if(precedence(item) > 1) {
            x = pop();
            while(precedence(x) >= precedence(item)) {
                postfix[j++] = x;
                x = pop();
            }
            push(x);
            push(item);
        } else if(item == ')') {
            x = pop();
            while(x != '(') {
                postfix[j++] = x;
                x = pop();
            }
        } else {
            printf("\nInvalid infix Expression.\n");
            exit(1);
        }
    }
    postfix[j] = '\0'; // Null terminate string.
}

// Main function
int main() {
    char infix[MAX], postfix[MAX];

    printf("Enter Infix expression : ");
    gets(infix);

    infixToPostfix(infix, postfix);
    printf("Postfix Expression: ");
    puts(postfix);

    return 0;
}

Next Topic :Postfix Evaluation