Evaluation of postfix expression using array |Data Structure in C|

Introduction

     In computer science, converting an infix expression to postfix is a common operation that involves rearranging the operators and operands to simplify evaluation. In this blog post, we'll delve into a C program that performs infix to postfix conversion, showcasing the powerful role of stacks in the process.  

Code

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

    char s[50];
    int top = -1;

    void push(char x) {
        s[++top] = x;
    }

    char pop() {
        if (top == -1)
            return -1;
        else
            return s[top--];
    }

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

    void main() {
        char exp[50];
        char *e, x;
        clrscr();

        printf("Enter the infix expression:\n");
        scanf("%s", &exp);

        printf("The postfix expression is:\n");
        e = exp;

        while (*e != '\0') {
            if (isalnum(*e))
                printf("%c", *e);
            else if (*e == '(')
                push(*e);
            else if (*e == ')') {
                while ((x = pop()) != '(')
                    printf("%c", x);
            } else {
                while (precedence(s[top]) >= precedence(*e))
                    printf("%c", pop());
                push(*e);
            }
            e++;
        }

        while (top != -1)
            printf("%c", pop());

        getch();
    }
       
     

Output

    Enter the infix expression:
    a+b*(c-d)/e
    The postfix expression is:
    abcd-*e/+
       

        In this example, the program takes the infix expression a + b * (c - d) / e as input and converts it to the postfix expression abcd-*e/+. The output demonstrates the successful conversion from infix to postfix using the provided C program. You can try running the program with different infix expressions to see how it consistently produces the corresponding postfix output.

Explanation

1. Header Files:

The program includes the standard input/output header <stdio.h>, the console I/O header <conio.h>, and the character type header <ctype.h>.

2. Stack Functions:

push and pop functions handle stack operations, allowing the program to efficiently manage operators during the conversion process.

3. Precedence Function:

The precedence function determines the precedence of operators, aiding in the decision-making process during conversion.

4. Infix to Postfix Conversion:

The main function takes user input in the form of an infix expression and iterates through each character.

Operands are directly printed, while operators are pushed onto the stack or popped based on their precedence.

5. Result Display:

The program prints the resulting postfix expression after the conversion.Conclusion

     

Conlcusion

 This C program showcases the elegance of stack-based algorithms in converting infix expressions to postfix. Understanding stack operations and operator precedence is crucial for implementing such algorithms efficiently. Experiment with different infix expressions, analyze the flow of the program, and observe how the stack efficiently manages the conversion process. This example serves as an insightful introduction to the world of stack-based algorithms in programming. Happy coding!