Thursday, September 22, 2011

Operator precedence parser

Share Orkut

E -> E + E | E * E | id


#include<stdio.h>
#include<string.h>
#include <stdlib.h>
char table[4][4]={'0','>','>','>',
         '<','>','<','>',
         '<','>','>','>',
         '<','<','<','0'};
char tab_ordr[4]={'i','+','*','$'};
int stk_res[100];
char stack[100];
int stkPtr=-1,strePtr=-1;
void push(char);
char pop();
void pushres(int);
int popres();
char peek();
void error();
int preced(char,char);
int main(){
   char str[20],temp,t[10];
   int len,inp_ptr=0,prec,no,f;
   printf("Enter the expression:- ");
   scanf("%s",str);
   push('$');
   len=strlen(str);
   str[len]='$';
   str[len+1]='\0';
   while(str[inp_ptr]!='$' || peek()!='$')
   {
     f=0;
     if(str[inp_ptr]>='0'&&str[inp_ptr]<='9'){
       no=atoi(&str[inp_ptr++]);
       while(str[inp_ptr]>='0' && str[inp_ptr]<='9')
         inp_ptr++;
       str[--inp_ptr]='i';
       f=1;
     }
     prec=preced(peek(),str[inp_ptr]);
     if(prec==0){
       if(f==1)
         pushres(no);
       push(str[inp_ptr++]);
     }
     else if(prec==1){

       do{
         temp=pop();
         switch(temp){
         case '+':if(strePtr<1)
             error();
           pushres(popres()+popres());
           break;
         case '*':if(strePtr<1)
             error();
           pushres(popres()*popres());
           break;
         }
       }
       while(preced(peek(),temp)!=0);
     }
     else
       error();
     }
     printf("Result= %d\n",popres());
     return 0;
}
void push(char a){
   stack[++stkPtr]=a;
}
char pop(){
   return stack[stkPtr--];
}
void pushres(int a){
   stk_res[++strePtr]=a;
}
int popres(){
   return stk_res[strePtr--];
}
char peek(){
  return stack[stkPtr];
}
void error(){
   printf("Error\n");
   exit(1);
}
int preced(char a,char b)
{
  int i,j;
  for(i=0;i<4;i++){
     if(tab_ordr[i]==a)
       break;
  }
  for(j=0;j<4;j++){
     if(tab_ordr[j]==b)
       break;
  }
  if(i==4 || j==4)
     error();
  else{
     if(table[i][j]=='<')
       return 0;
       else if(table[i][j]=='>')
         return 1;
       else
         return 2;
  }
}

Output




No comments:

Post a Comment