: WAP to convert infix to prefix
notation.
#include<stdio.h>
#include<conio.h>
#include<string.h>
char stack[20];
int top=-1;
char pop();
void push(char sym);
int prcd(char sym)
{
switch(sym)
{
case
'+':
case
'-': return 2;
case
'*':
case
'/': return 4;
case
'^':
case
'$': return 6;
case
'(':
case ')':
case
'#': return 1;
}
}
int isoperator(char sym)
{
switch(sym)
{
case
'+':
case
'-':
case
'*':
case
'/':
case
'^':
case
'$':
case
'(':
case
')': return 1;
default:
return 0;
}
}
void intopre(char infix[],char prefix[])
{
int sym;
int j=0;
stack[++top]='#';
for(int
i=strlen(infix)-1;i>=0;i--)
{
sym=infix[i];
if(isoperator(sym)==0)
{
prefix[j]=sym;
j++;
}
else
{
if(sym==')')
push(sym);
else if(sym=='(')
{
while(stack[top]!=')')
{
prefix[j]=pop();
j++;
}
pop();// to pop (
}
else
{
if(prcd(sym)>prcd(stack[top]))
push(sym);
else
{
while(prcd(sym)<prcd(stack[top]))
{
prefix[j]=pop();
j++;
}
push(sym);
}
}
}
}
while(stack[top]!='#')
{
prefix[j]=pop();
j++;
}
prefix[j]='\0';
}
void main()
{
clrscr();
char
infix[20],prefix[20];
char temp;
int len;
printf("\nEnter the infix string(max 20 char):");
gets(infix);
intopre(infix,prefix);
printf("\nThe corresponding prefix string is:");
len=strlen(prefix);
for(int
i=0;i<=(len/2);i++)
{
temp=prefix[i];
prefix[i]=prefix[len-i-1];
prefix[len-i-1]=temp;
}
puts(prefix);
getch();
}
void push(char ch)
{
stack[++top]=ch;
}
char pop()
{
char ch;
ch=stack[top--];
return ch;
}
OUTPUT:
No comments:
Post a Comment