Question

• 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.

Answer 1

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 

---

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

---