Infix, Prefix and Postfix Conversion in Stack

Another application of stack is calculation of postfix expression. There are basically three types of notation for an expression (mathematical expression; An expression is defined as the number of operands or data items combined with several operators.)

1. Infix Notation
2. Prefix Notation
3. Postfix Notation

Precedence and Associativity:

1. Parentheses ( ): They don't have precedence themselves but force priority (group expressions manually).
2. Exponentiation ($ or ^): Highest among arithmetic operators.
   (Some programming languages like C use pow(), but in theory/conversion problems, $ or ^ is assumed.)
3. Multiply, Divide, Modulus (*, /, %) : These come next. % is modulus (remainder after division).
4. Addition, Subtraction (+, -) : Lowest precedence.

Operators with the same precedence level (like + and - or * and /) are left-associative, meaning they are evaluated from left to right.

Algorithm for Infix to Postfix Conversion

The algorithm for converting an infix expression (where operators are between operands, e.g., 3 + 4 * 2) to a postfix expression (also known as Reverse Polish Notation, e.g., 3 4 2 * +) involves utilizing a stack data structure.

Here’s a step-by-step breakdown of the algorithm:

1. Initialize an empty stack for operators and an empty list for the result (postfix expression).
2. Scan the infix expression from left to right.
3. For each character in the infix expression:
   • If the character is an operand (number or variable):
     • Add it directly to the result list.
   • If the character is an opening parenthesis (:
     • Push it onto the stack.
   • If the character is a closing parenthesis ):
     • Pop from the stack and add to the result list until an opening parenthesis ( is encountered. Discard the opening parenthesis.
   • If the character is an operator (e.g., +, -, *, /):
     • While the operator at the top of the stack has greater precedence or the same precedence (and is left-associative), pop it from the stack and add to the result.
     • Push the current operator onto the stack.
4. After the entire infix expression has been processed, pop any remaining operators from the stack and add them to the result list.
5. The result list now contains the postfix expression.

Example of Infix to Postfix Conversion

Let's convert the infix expression 3 + 4 * 2 / (1 - 5) to postfix.

1. Infix Expression: 3 + 4 * 2 / (1 - 5)
2. Stack: [], Result: []
3. Read 3 (operand): Add to result.
   • Result: [3]
4. Read + (operator): Push onto the stack.
   • Stack: [+]
5. Read 4 (operand): Add to result.
   • Result: [3, 4]
6. Read * (operator): * has higher precedence than +, so push onto the stack.
   • Stack: [+, *]
7. Read 2 (operand): Add to result.
   • Result: [3, 4, 2]
8. Read / (operator): / has the same precedence as *, so pop * and add to the result, then push / onto the stack.
   • Stack: [+, /]
   • Result: [3, 4, 2, *]
9. Read ( (left parenthesis): Push onto the stack.
   • Stack: [+, /, (]
10. Read 1 (operand): Add to result.
    • Result: [3, 4, 2, *, 1]
11. Read - (operator): Push onto the stack.
    • Stack: [+, /, (, -]
12. Read 5 (operand): Add to result.
    • Result: [3, 4, 2, *, 1, 5]
13. Read ) (right parenthesis): Pop operators until ( is encountered, adding them to the result.
    • Pop - and add to result.
    • Stack: [+, /]
    • Result: [3, 4, 2, *, 1, 5, -]
    • Discard the opening parenthesis.
14. End of expression: Pop the remaining operators from the stack.
    • Pop / and add to result.
    • Pop + and add to result.
    • Stack: []
    • Result: [3, 4, 2, *, 1, 5, -, /, +]

Final Postfix Expression: 3 4 2 * 1 5 - / +

For Example: Consider the following arithmetic Infix to Postfix expression

( A + ( B * C - ( D / E ^ F ) * G ) * H )

Postfix Expression is A B C * D E F ^ / G * - H * +

C Code for Infix to Postfix Conversion

Here's an example of how you can implement the infix to postfix conversion algorithm in C:

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

#define MAX 100

// Stack structure
char stack[MAX];
int top = -1;

// Function to check if the character is an operator
int isOperator(char c) {
    return (c == '+' || c == '-' || c == '*' || c == '/' || c == '^');
}

// Function to check if the character is an operand
int isOperand(char c) {
    return isdigit(c);  // Checks if the character is a digit
}

// Function to get the precedence of operators
int precedence(char c) {
    if (c == '+' || c == '-') {
        return 1;
    } else if (c == '*' || c == '/') {
        return 2;
    } else if (c == '^') {
        return 3;
    }
    return -1;
}

// Function to push element to the stack
void push(char c) {
    if (top == (MAX - 1)) {
        printf("Stack Overflow\n");
    } else {
        stack[++top] = c;
    }
}

// Function to pop element from the stack
char pop() {
    if (top == -1) {
        printf("Stack Underflow\n");
        return -1; // Return an invalid character when underflow occurs
    } else {
        return stack[top--];
    }
}

// Function to get the top element of the stack without removing it
char peek() {
    if (top == -1) {
        return -1;
    }
    return stack[top];
}

// Function to convert infix to postfix
void infixToPostfix(char* infix, char* postfix) {
    int i = 0, j = 0;
    char current;
    
    while (infix[i] != '\0') {
        current = infix[i];
        
        // If the current character is an operand, add it to the postfix expression
        if (isOperand(current)) {
            postfix[j++] = current;
        }
        // If the current character is '(', push it to the stack
        else if (current == '(') {
            push(current);
        }
        // If the current character is ')', pop until '(' is found
        else if (current == ')') {
            while (top != -1 && peek() != '(') {
                postfix[j++] = pop();
            }
            pop(); // Pop '('
        }
        // If the current character is an operator
        else if (isOperator(current)) {
            while (top != -1 && precedence(peek()) >= precedence(current)) 			  			{
                postfix[j++] = pop();
            }
            push(current);
        }
        i++;
    }
    
    // Pop all remaining operators from the stack
    while (top != -1) {
        postfix[j++] = pop();
    }
    
    postfix[j] = '\0'; // Null-terminate the postfix expression
}

int main() {
    char infix[MAX], postfix[MAX];
    
    printf("Enter an infix expression: ");
    fgets(infix, sizeof(infix), stdin);  // Read the infix expression
    
    infixToPostfix(infix, postfix);
    
    printf("Postfix expression: %s\n", postfix);
    
    return 0;
}

Explanation of the Code

Data Structures:

• stack[MAX]: A character array used to store operators and parentheses during the conversion.
• top: Integer that keeps track of the top of the stack.

Functions:

• isOperator(): Returns true if the character is an operator (+, -, *, /, ^).
• isOperand(): Returns true if the character is an operand (a digit in this case).
• precedence(): Returns the precedence of operators. Operators * and / have higher precedence than + and -, and ^ has the highest precedence.
• push(): Pushes a character onto the stack.
• pop(): Pops a character from the stack.
• peek(): Returns the top character from the stack without removing it.
• infixToPostfix(): Converts the given infix expression to a postfix expression using the stack.

Main Function:

• The user is prompted to enter an infix expression.
• The infix expression is then converted to a postfix expression using the infixToPostfix() function.
• Finally, the resulting postfix expression is printed.