Program to check whether a string belongs to the grammar or not

Download full Doc

Algorithm:

Start.

Declare two character arrays str[],token[] and initialize integer variables a=0,b=0,c,d. Input the string from the user.

Repeat steps 5 to 12 till str[a] =’\0’.

If str[a] =='(' or str[a] =='{' then token[b] =’4’, b++.

If str[a] ==')' or str[a] =='}’ then token[b] =’5’, b++.  Check if isdigit(str[a]) then repeat steps 8 till isdigit(str[a]) a++.

a--, token[b] =’6’, b++.

If str[a]=='+’ then token[b]='2',b++. If(str[a]=='*') then token[b]=’3’,b++. a++.

token[b]='\0';

then print the token generated for the string . b=0.

Repeat step 22 to 31 till token[b]!='\0' c=0.

Repeat step 24 to 30 till (token[b]=='6' and token[b+1]=='2' and token[b+2]=='6') or (token[b]=='6' and token[b+1]=='3'and token[b+2]=='6') or (token[b]=='4' and token[b+1]=='6' and token[b+2]=='5') or (token[c]!='\0').

token[c]='6'; c++;

Repeat step 27 to 28 till token[c]!='\0'. token[c]=token[c+2].

c++.

token[c-2]=’\0’. print token. b++.

Compare token with 6 and store the result in d.

If d=0 then print that the string is in the grammar. Else print that the string is not in the grammar.

Stop.

Program:

#include<stdio.h>

#include<conio.h>

#include<ctype.h>

#include<string.h> void main()

{

    int a = 0, b = 0, c;

    char str[20], tok[11];

    clrscr();

    printf("Input the expression = ");

    gets(str);

    while (str[a] != '\0') {

        if ((str[a] == '(') || (str[a] == '{')) {

            tok[b] = '4';

            b++;

        }

        if ((str[a] == ')') || (str[a] == '}')) {

            tok[b] = '5';

            b++;

        }

        if (isdigit(str[a])) {

            while (isdigit(str[a])) {

                a++;

            }

            a--;

            tok[b] = '6';

            b++;

        }

        if (str[a] == '+') {

            tok[b] = '2';

            b++;

        }

        if (str[a] == '*') {

            tok[b] = '3';

            b++;

        }

        a++;

    }

    tok[b] = '\0';

    puts(tok);

    b = 0;

    while (tok[b] != '\0') {

        if (((tok[b] == '6')&&(tok[b + 1] == '2')&&(tok[b + 2] == '6')) || ((tok[b] == '6')&&(tok[b + 1

                ] == '3')&&(tok[b + 2] == '6')) || ((tok[b] == '4')&&(tok[b + 1] == '6')&&(tok[b + 2] == '5'))) {

            tok[b] = '6';

            c = b + 1;

            while (tok[c] != '\0') {

                tok[c] = tok[c + 2];

                c++;

            }

            tok[c] = '\0';

            puts(tok);

            b = 0;

        } else {

            b++;

            puts(tok);

        }

    }

    int d;

    d = strcmp(tok, "6");

    if (d == 0) {

        printf("It is in the grammar.");

    } else {

        printf("It is not in the grammar.");

    }

    getch();

}

Output: