Write a code to check whether given string can be generated from given grammar ?
Grammar :
S – > 122S
S – > 12S
S – > 1S
S – > “”
==================================================================================
Input :
12221
Output :
0
===================================================================================
Input :
121
Output:
1
====================================================================================
O = > False (Cannot be generated)
1 = > True (Can be generated)
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 |
#include<stdio.h> int can_be_generated(char *str) { int len=strlen(str); int flag=1; int i=0; while(1){ if(((i+2)<=(len-1)) &&(str[i]=='1' && str[i+1]=='2' && str[i+2]=='2')){ i=i+3; continue; } else if(((i+1)<=(len-1)) && (str[i]=='1' && str[i+1]=='2')){ i=i+2; continue; } else if((i<=(len-1)) && (str[i]=='1')){ i=i+1; continue; } else if((i==len)&&(str[i]=='\0')){ break; } else{ flag=0; break; } } if(flag==0){ return 0; } else return 1; } int main(){ printf(" %d ",can_be_generated("121")); return 0; } |