EX.NO:3 INFIX TO POSTFIX CONVERSION
AIM:
To write a c program to convert the given expression to postfix expression using stack.
ALGORITHM:
Step 1:
Start the program.
Step 2:
Given the precedence for left and right give higher precedence
for right.
for right.
Step 3:
Assign the precedence to the operator.
Step 4:
Get the infix expression.
Step 5:
Calculate the length of the infix expression.
Step 6:
If it is left parenthesis ,push it into the stock .if it is right
parenthesis then it is popped out until the ‘(‘ is seen..
parenthesis then it is popped out until the ‘(‘ is seen..
Step 7:
If it is operand ,then it is given directly to output.
Step 8:
If it is operator then check the precedence.
Step 9:
If the input precedence is less than the precedence is less than the
precedence of the top element,pop out then the top element of
stock,if it is greater push the scanned value into the stock.
precedence of the top element,pop out then the top element of
stock,if it is greater push the scanned value into the stock.
Step 10:
Repeat step6 to10 untill end of expression is scanned.
Step 11:
After reading all character pop the leftout character in stock.
Step 12:
Stop the process
PROGRAM:
#include<stdio.h>
#include<conio.h>
#include<string.h>
#include<ctype.h>
#include<stdlib.h>
#define N 64
#define LP 10
#define RP 20
#define OPERATOR 30
#define OPERAND 40
#define LPP 0
#define AP 1
#define SP AP
#define MP 2
#define DP MP
#define REMP 2
#define NONE 9
static char infix[N+1],stack[N],postfix[N+1];
static int top;
void infixtopostfix(void);
int gettype(char);
void push(char);
char pop(void);
int getprec(char);
void main()
{
clrscr();
char ch;
do
{
top=-1;
printf("\n Enter an infix expression\n");
fflush(stdin);
gets(infix);
infixtopostfix();
printf("\n infix=%s\n Postfix= %s\n",infix,postfix);
printf("\n Do you wish to cotinue\n");
ch=getch();
}while(ch=='Y'||ch=='Y');
}
void infixtopostfix(void)
{
int i,p,l,type,prec;
char next;
i=p=0;
l=strlen(infix);
while(i<l)
{
type=gettype(infix[i]);
switch(type)
{
case LP:
push(infix[i]);
break;
case RP:
while((next=pop())!='(')
postfix[p++]=next;
break;
case OPERAND:
postfix[p++]=infix[i];
break;
case OPERATOR:
prec=getprec(infix[i]);
while(top>-1 && prec <= getprec(stack[top]))
postfix[p++]=pop();
push(infix[i]);
break;
}
i++;
}while(top>-1)
postfix[p++]=pop();
postfix[p]='\0';
}
int gettype(char sym)
{ switch(sym)
{
case '(':
return(LP);
case ')':
return(RP);
case '+':
case '-':
case '*':
case '/':
case '%':
return(OPERATOR);
default:
return(OPERAND);
}
}
void push(char sym)
{
if(top>N)
{
printf("\nStack is full\n");
exit(0);
}
else
stack[++top]=sym;
}
char pop(void)
{
if(top<=-1)
{
printf("\n Stack is empty\n");
exit(0);
}
else
return(stack[top--]);
}
int getprec(char sym)
{
switch(sym)
{
case '(':return(LPP);
case '+':return(AP);
case '-':return(SP);
case '*':return(MP);
case '/':return(DP);
case '%':return(REMP);
default:return(NONE);
}
}
