Oct 9, 2009

Operator precedence parsing algorithm


//This is operator precedence parsing algorithm using C

char pre[10][10],ss[30],rs[30],stk[10][2];
int i,j,k,n,p,sp=0,br=0;
void push();
void pop();
char chk_pre();
void reduce_ss();
void main()
{
clrscr();
strcpy(pre[0]," +*()]");
strcpy(pre[1],"+><<>>");
strcpy(pre[2],"*>><>>");
strcpy(pre[3],"(<<<=e");
strcpy(pre[4],")>>e>>");
strcpy(pre[5],"[<<<e=");
n=6;
scanf ("%s",ss, printf("Enter the source string : "));
strcpy(rs,"[");
strcat(rs,ss);
strcat(rs,"]");
strcpy(ss,rs);
printf("\n");
for(i=0;i<n;i++)
{
for(j=0;j<strlen(pre[i]);j++)
printf("%c\t",pre[i][j]);
printf("\n");}
while(ss[2]!=']' && br==0)
{
sp=0;
for(i=0;i<strlen(ss);i++)
{
if( (ss[i]>='a' && ss[i]<='z') || (ss[i]>='A' && ss[i]<='Z') )
continue;
push();
if(stk[sp-1][1]=='e' || ss[1]==']' || ss[0]==']')
{ printf("\n\nInvalid string.");
br=1;
break; }
if((stk[sp-1][1]=='>' && stk[sp-2][1]=='<') || stk[sp-1][1]=='=')
{ reduce_ss();
pop(); } } }
if(ss[2]==']')
printf("\nValid String.");
getch();
}
void push()
{ stk[sp][0]=ss[i];
stk[sp][1]=chk_pre();
sp++; }
void pop()
{ char tmp,tmp1;
sp--;
tmp=stk[sp][0];
tmp1=stk[sp][1];
sp--;
stk[sp][0]=tmp;
stk[sp][1]=tmp1;
sp++; }
char chk_pre()
{ char tmp;
if(i==0)
tmp=' ';
else
{ for(j=0;j<n;j++)
for(k=0;k<strlen(pre[j]);k++)
if(stk[sp-1][0]==pre[j][0] && stk[sp][0]==pre[0][k])
tmp=(pre[j][k]); }
return tmp; }
void reduce_ss()
{  char t1[30],t3[30];
int tmp;
if(stk[sp-1][0]==')' && stk[sp-2][0]=='(')
tmp=i-2;
else
tmp=i-3;
for(j=0;j<tmp;j++)
{  t1[j]=ss[j];  }
t1[j]='\0';
tmp=tmp+3;
k=0;
for(j=tmp;j<strlen(ss);j++)
{  t3[k]=ss[j];
k++;  }
t3[k]='\0';
strcpy(ss,"");
strcpy(ss,t1);
strcat(ss,"i");
strcat(ss,t3);
}