PSUDO CODE :-
1) Scan infix expression from left to right one character at
a time.
2) Check whether the character is an operator or operand.
3) If it is an operand then copy it in to postfix array.
4) If it is an operator then
a) check whether stack is empty or not.
b) If it is empty then push the operator in the stack and
read next element from the infix array.
c) If stack is empty then match the priority of stack top
with operator out side.
d) If the precedence of outer operator is higher then
push it in to the stack and go to read next charecter
from infix array.
e) If the precedence of top is higher then pop it.Append
in the postfix array and go to step 1.
5) Repeat the above procedure until the infix expression
comes to an end.
6) Pop all the element (remaining) from the stack one
by one and copy them in the postfix array.
PROGRAM :-
#include<stdio.h>
#include<conio.h>
struct stack
{
char arr[20];
int tos;
};
void push(struct stack *,char);
char pop(struct stack *);
void convert(char[],char[]);
int isopnd(char);
int prcd(char,char);
int isempty(struct stack);
void main()
{
char infix[50],postfix[50];
clrscr();
printf("\nenter a vaid expression");
scanf("%s",infix);
convert(infix,postfix);
printf("the postfix expression is %s ",postfix);
getch();
}
void convert(char infix[50],char postfix[50])
{
int i,j=0,result;
char ch,op;
struct stack s;
s.tos=-1;
for(i=0;infix[i]!='\0';i++)
{
ch=infix[i];
if(isopnd(ch)==1)
{
postfix[j]=ch;
j++;
}
else
{
while(isempty(s)==0)
{
result=prcd(ch,s.arr[s.tos]);
if(result==0)
break;
op=pop(&s);
postfix[j]=op;
j++ ;
}
push(&s,ch);
}}
while(isempty(s)==0)
{
op=pop(&s);
postfix[j]=op;
j++;
}
postfix[j]='\0';
}
int isempty(struct stack s)
{
if(s.tos==-1)
return 1;
else
return 0;
}
int isopnd(char ch)
{
if((ch>=65 && ch<=90)||(ch>=97 && ch<=122))
return 1;
else
return 0;
}
int prcd(char out, char in)
{
if(in=='$')
return 1;
else if ( out=='$')
return 0;
else if(in=='/'|| in=='*')
return 1;
else if(out=='/' || out=='*')
return 0;
else
return 1;
}
No comments:
Post a Comment