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

ABOUT THE EXPERIMENT: Infix: Operators are written in-between their operands.

Ex: X + Y

Prefix: Operators are written before their operands.

Ex: +X Y

postfix: Operators are written after their operands. Ex: XY+

### Algorithm to convert Infix To Postfix

Let, X is an arithmetic expression  in infix form. This algorithm finds the equivalent postfix expression Y.

1. Scan X from left to right and repeat Step 3 to 6 for each element of X until the Stack is empty.
2. If an operand is encountered, add it to Y.
3. If a left parenthesis is encountered, push it onto Stack.
4. If an operator is encountered ,then:
1. Repeatedly pop from Stack and add to Y each operator (on the top of Stack) which has the same precedence as or higher precedence than operator.
2. Add operator to Stack. [End of If]
5. If a right parenthesis is encountered ,then:
1. Repeatedly pop from Stack and add to Y each operator (on the top of Stack) until a left parenthesis is encountered.
2. Remove the left Parenthesis. [End of If] [End of If]
6. END
				
#include<stdio.h>
#include<string.h>
#include<conio.h>
int F(char symbol)
{
switch(symbol)
{
case '+' case '-': return 2;
case ‘*’: case ‘/’: return 4;
case '^': case '$': return 5; case '(': return 0; case '#': return -1; default: return 8; } } int G(char symbol) { switch(symbol) { case '+' case '-': return 1; case ‘*’: case ‘/’: return 3; case '^': case '$': return 6;
case '(': return 9; case ')': return 0;
default: return 7;
}
}
void infix_postfix(char infix[], char postfix[])
{
int top, j, i;
char s[30], symbol;
top = -1;
s[++top] = '#';
j = 0;
for(i=0; i < strlen(infix); i++)
{
symbol = infix[i];
while(F(s[top]) > G(symbol))
{
postfix[j] = s[top--]; j++;
}
if(F(s[top]) != G(symbol)) s[++top] = symbol;
else
top--;
}
while(s[top] != '#')
{
postfix[j++] = s[top--];
}
postfix[j] = '\0';
}
void main()
{
char infix[20], postfix[20];
clrscr();
printf("\nEnter a valid infix expression\n");
flushall();
gets(infix);
infix_postfix(infix,postfix);
printf("\nThe infix expression is:\n");
printf ("%s",infix);
printf("\nThe postfix expression is:\n");
printf ("%s",postfix);
getch();
}


output: Enter a valid infix expression (a+(b-c)*d) The infix expression is: (a+(b-c)*d) The postfix expression is: abc-d*+