FIFA-2022 Career Guide Free Tutorials Go to Your University Placement Preparation 
0 like 0 dislike
11.0k views
in VTU B.Tech (CSE-III Sem) Data Structure Lab by Goeduhub's Expert (7.6k points)
retagged by
  • Design, Develop and Implement a Program in C for converting an Infix Expression to Postfix Expression. 
  • Program should support for both parenthesized and free parenthesized expressions with the operators: +, -, *, /, % (Remainder), ^ (Power) and alphanumeric operands.

1 Answer

0 like 0 dislike
by Goeduhub's Expert (7.6k points)
edited by
 
Best answer

Design, Develop and Implement a Program in C for converting an Infix Expression to Postfix Expression

Expression conversion is the most important application of stacks. Given an infix expression, it can be converted to both postfix and prefix notations. Now, let us see how to convert an infix expression to postfix.

  • Infix notation ( a operator b ): For example, a + b is an infix notation.
  • Postfix notation ( a b operator ): a b + is the equivalent postfix notation of a + b.

The compiler scans the given  expression either from left to right or from right to left.

 Steps to convert infix expression to postfix

1. Scan the given infix expression from left to right.

2. If the scanned character is an operand, then output it.

3. Else,

  • If the precedence of the scanned operator is greater than the precedence of the operator in the top of the stack(or the stack is empty or if the stack contains a ‘(‘ ), push it.
  • Else, Pop all operators from the stack whose precedence is greater than or equal to that of the scanned operator. Then, push the scanned operator to the top of the stack. (If you encounter parenthesis while popping then stop there and push the scanned operator in the stack.)

4. If the scanned character is ‘(‘, push it to the stack.

5. If the scanned character is ‘)’, pop the stack and and output characters until ‘(‘ is encountered, and discard both the parenthesis.

6. Repeat steps 2-5 until infix expression is scanned completely.

7. Print the output.

8. Pop and output from the stack.

Program

#include<stdio.h>

#include<stdlib.h>

#include<math.h>

#include <string.h>

char infix_string[20], postfix_string[20];

int top; int stack[20]; int pop();

int precedence(char symbol);

int isEmpty();

void infix_to_postfix();

int check_space(char symbol);

void push(long int symbol);

int main()

{

    int count, length;

    char temp;

    top = -1;

    printf("\nINPUT THE INFIX EXPRESSION : ");

    scanf("%s", infix_string);

    infix_to_postfix();

    printf("\nEQUIVALENT POSTFIX EXPRESSION : %s\n", postfix_string);

    return 0;

}

void infix_to_postfix()

{

    unsigned int count, temp = 0;

    char next;

    char symbol;

    for(count = 0; count < strlen(infix_string); count++)

    {

        symbol = infix_string[count];   // Scanning the input expression

        if(!check_space(symbol))

        {

            switch(symbol)

            {

                case '(': push(symbol);

                    break;

                case ')':

                    while((next = pop()) != '(')     // pop until '(' is encountered

                    {

                        postfix_string[temp++] = next;

                    }

                    break;

                case '+':

                case '-':

                case '*':

                case '/':

                case '%':

                case '^':

                    while(!isEmpty() && precedence(stack[top]) >= precedence(symbol))   // Check precedence and push the higher one

                        postfix_string[temp++] = pop();

                    push(symbol);

                    break;

                default:

                    postfix_string[temp++] = symbol;

            }

        }

    }

    while(!isEmpty())

    {

        postfix_string[temp++] = pop();

    }

    postfix_string[temp] = '\0';

}

int precedence(char symbol)

{

    switch(symbol)

    {

        case '(': return 0;

        case '+':

        case '-':

            return 1;

        case '*':

        case '/':

        case '%':

            return 2;

        case '^':

            return 3;

        default:

            return 0;

    }

}

int check_space(char symbol)

{

    if(symbol == '\t' || symbol == ' ' )

    {

        return 1;

    }

    else

    {

        return 0;

    }

}

void push(long int symbol)

{

    if(top > 20)

    {

        printf("Stack Overflow\n");

        exit(1);

    }

    top = top + 1;

    stack[top] = symbol;    // Push the symbol and make it as TOP

}

int isEmpty()

{

    if(top == -1)

    {

        return 1;

    }

    else

    {

        return 0;

    }

}

int pop()

{

    if(isEmpty())

    {

        printf("Stack is Empty\n");

        exit(1);

    }

    return(stack[top--]);  // Pop the symbol and decrement TOP

}

Output 

output


For more Visvesvaraya Technological University(VTU) CSE-III Sem Data Structure Lab Experiments Click Here


Learn & Improve In-Demand Data Skills Online in this Summer With  These High Quality Courses[Recommended by GOEDUHUB]:-

Best Data Science Online Courses[Lists] on:-

Claim your 10 Days FREE Trial for Pluralsight.

Best Data Science Courses on Datacamp
Best Data Science Courses on Coursera
Best Data Science Courses on Udemy
Best Data Science Courses on Pluralsight
Best Data Science Courses & Microdegrees on Udacity
Best Artificial Intelligence[AI] Courses on Coursera
Best Machine Learning[ML] Courses on Coursera
Best Python Programming Courses on Coursera
Best Artificial Intelligence[AI] Courses on Udemy
Best Python Programming Courses on Udemy

Related questions

 Important Lists:

Important Lists, Exams & Cutoffs Exams after Graduation PSUs

 Goeduhub:

About Us | Contact Us || Terms & Conditions | Privacy Policy ||  Youtube Channel || Telegram Channel © goeduhub.com Social::   |  | 

 

Free Online Directory

...