WAP to Convert Infix Expression into PostFix Expression Effciiently

Example a+b*c =abc+*
Data Structure:Array

Algorithm: let Q be the Arithmetic Expression
1.Push ( in to Stack.n ) in end of the Q.
2. Scan Q from left to right & repat stpe 3 to 6 fro each elemnt of Q untill stack is
emptty.
3.if an operand encountered ad it to p.
4. if ( encountered push it into stack.
5.if an operator encountered then
a.add operator to stack.
b.repeatedly op from the satck & add P each char (on top of the stack) which has
the same or higher precendence than operator .
6.if ) encountered then
a. repeatedly pop from the satck & add p to each opeartor (on top of stack untill
a ' (' encountered.
b. remove '(' (do add '(' to the P.

Working Code:

#include
#include
#include
#include
#include
#define MAX 100


/*this is the structure of the stack used to save operators in the expression*/
struct stack
{
char elem[MAX];
int top;
};
struct stack stk;


void convert(char *infix, char *postfix);
int prcd(char op1, char op2);
void create();
void push(char op);
char pop(int *und);
int empty();
int full();
int isopnd(char ch);
int isoprtr(char ch);



int main()
{
char ch, infix[MAX], postfix[MAX];

create();

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

convert(infix, postfix);

printf("\n\nThe postfix expression is :\n");
printf("%s\n", postfix);

getch();
}

return(0);
}




void convert(char *infix, char *postfix)
{
int i, pos=0, over, und, n;
char ch, op;

for(i=0; (ch=infix[i]) != '\0' ; ++i)
{
/*
operands are entered directly into the postfix expression

*/

if(isopnd(ch))
{
postfix[pos++] = ch;
}

/*
if an operator is encountered, insert it into the stack or the postfix expression according to the precedence wit rspect to previous operators(if any) in the stack
*/
else if(isoprtr(ch))
{
op = pop(&und);

while(!und && prcd(op, ch))
{
postfix[pos++] = op;
op = pop(&und);
}

if(!und)
push(op);

if(und || ch != ')')
push(ch);
else
pop(&und);
}

/*
if we get some other character than an operand or an operator, then the infix expression is invalid.
*/
else
{
printf("\n\nThe infix expression is not valid\n");
getch();
return(0);
}
}

while(!empty())
{
postfix[pos++] = pop(&und);
}

postfix[pos++] = '\0';
}


/*function to check precedence of different operators*/
int prcd(char op1, char op2)
{
if(op1 == '(' || op2 == '(')
return 0;

if(op2 == ')')
return 1;

if(op1 == '^')
{
if(op2 == '^')
return 0;
else
return 1;
}

if(op1 == '/' || op1 == '*')
{
if(op2 == '^')
return 0;
else
return 1;
}

else
{
if(op2 == '^' || op2 == '/' || op2 == '*')
return 0;
else
return 1;
}
}




void create()
{
stk.top = -1;
}


void push(char op)
{
stk.elem[++(stk.top)] = op;
}



char pop(int *und)
{
if(empty())
{
*und = 1;
return('0');
}

*und = 0;
return(stk.elem[stk.top--]);

}



int empty()
{
if(stk.top == -1)
return 1;
else
return 0;
}


int full()
{
if(stk.top == MAX - 1)
return 1;
else
return 0;
}


/*check whether the given char is an operand or not*/
int isopnd(char ch)
{
if((ch>=48 && ch<58) || (ch>64 && ch<=90) || (ch>96 && ch<=122))
return 1;
else
return 0;
}


/*check whether the given char is an operator or not*/
int isoprtr(char ch)
{
if(ch == '+' || ch == '-' || ch == '*' || ch == '/' || ch == '^' || ch == '(' || ch == ')')
return 1;
else
return 0;
}

Time Complexity O(n)
Space Complexity O(n) Stack Space
Run Here https://ideone.com/cQAJP