Introduction

In the last post I have explained about the infix,prefix,postfix expression. In this post we are going to know about the conversion of infix to postfix expression.

Infix to Postfix Conversion

  • Consider an infix string x+y*c.Each character of the string is called tokens.

  • The algorithm for converting an infix expression to postfix expression is given below.

  • We need a stack to solve this problem

Program

#include


#define SIZE 40 char stack[SIZE]; int top=-1; void push(char data) {     if(top==SIZE-1)     {         printf("Stack is fulln");         return;     }     else     {         top=top+1;         stack[top]=data;         printf("Pushed element is %cn",data);     } } char pop() {     char ch;     if(top<0)     {         printf("stack is emptyn");         return;     }     else     {         ch=stack[top];         printf("poped element is%cn",ch);         top=top-1;         return(ch);     } } int check_pre(char a ,char b) {     //operators are arranged in the array based     //on their priority. from low to high     char op[]={'-','+','%','/','*','(',')'};     int i,c1=0,c2=0;     for(i=0;i<7;i++)     {         if(a==op[i])             c1=i+1;         else if(b==op[i])             c2=i+1;     }     if(c1>c2)         return(1);     else if(c1int main() {     char in_str[50],out_str[50];     char ch,temp;     int x=0,y=0,pre;     printf("Enter the infix stringn");     scanf("%s",in_str);     ch=in_str[x];     while(ch!='')     {         //for operand         if((ch>='a' && ch<='z') ||  (ch<='A' && ch>='Z') ||  (ch>='0' && ch<='9'))                out_str[y++]=ch;         //for '(' paranthesis         else if(ch=='(')             push(ch);         //for ')' parenthesis         else if(ch==')')         {             temp=pop();             while(temp!='(')             {                 out_str[y++]=temp;                 temp=pop();             }           //  if(temp=='(')                // pop();                                  }         //for operator         else         {         //if the stack is empty or         // the stack top element is '('         //just push the operator in to the stack                 if (top==-1 || stack[top]=='(')                 push(ch);             else             {                 temp=stack[top];                 //check the precedence                 pre=check_pre(ch,temp);                 if(pre<0 )                 {                     do{                                         out_str[y++]=pop();                     temp=stack[top]; }while(top!=-1 && temp!='(' &&  (check_pre(ch,temp)<0));                     push(ch);                 }                 else                 {                     push(ch);                 }             }         }         x++;         ch=in_str[x];     }     while(top!=-1)     {         out_str[y++]=pop();     }     out_str[y]='';     printf("Postfix string=%sn",out_str);     return; }

Output (1)

Enter the infix string
((a+b)*c-(d-e))%(f+g)
Pushed element is (
Pushed element is (
Pushed element is +
poped element is+
poped element is(
Pushed element is *
poped element is*
Pushed element is –
Pushed element is (
Pushed element is –
poped element is-
poped element is(
poped element is-
poped element is(
Pushed element is %
Pushed element is (
Pushed element is +
poped element is+
poped element is(
poped element is%
Postfix string=ab+c*de–fg+%

Output

Enter the infix string
(5*(((9+8)*(4*6))+7))
Pushed element is (
Pushed element is *
Pushed element is (
Pushed element is (
Pushed element is (
Pushed element is +
poped element is+
poped element is(
Pushed element is *
Pushed element is (
Pushed element is *
poped element is*
poped element is(
poped element is*
poped element is(
Pushed element is +
poped element is+
poped element is(
poped element is*
poped element is(
Postfix string=598+46**7+*