accepting a grammar in C++

Question

this is a lab assignment i am stuck on. i cant believe i am having problems with this basic programming, but i cant afford to waste any more time on this. i gotta ask the experts.

i need to accept this grammar (ab)*b, which basically means any number of "ab" and ending with b.

i have written this code but somehow, it checks only the first 2 letters. please help.

#include <iostream.h>
#include <conio.h>
#include <string.h>

enum track {true, false};

void main()

{
    clrscr();
    char*str;
    enum track track_pos, track_pos_2;
    cout<<"enter the string: ";
    cin>>str;
    int len=strlen(str);
    cout<<"length of the string is "<<len;
    getch();
    int i;
    for(i=0;i<len; i++)
    {
     ++str;
     cout<<"loop"<<i;
     if(*str=='a' && i%2==0)
     {
      cout<<"\nchecking a...";
      track_pos=true;
      cout<<"\na.check";
      ++str;
      if (*str=='b')
       {
       cout<<"\nchecking b...";
       track_pos=true;
       cout<<"\nb.check";
      }
      else{
       track_pos=false;
       cout<<"\nb.uncheck";
      }
     }

    }

    if(*str=='b')
     track_pos_2=true;
    else
     track_pos_2=false;

    if(track_pos==true && track_pos_2==true)
     cout<<"\nThe string is accpeted.";
    else
     cout<<"\nThe string is rejected.";

    getch();
    cout<<"\n\nDo you want to continue (Y/N)? ";
    char ch;
    cin>>ch;
    if(ch=='y' || ch=='Y')
     main();

}

Answer 1

Implement a simple state machine. It has these states:

• 0 = start
• 1 = 'received a of (ab)'
• 2 = 'received b of (ab)'
• 3 = 'received final b'
• -1 = error, invalid grammar

Then you just need a function like this:

int nextState(int currentState, char inputChar) {
  if (currentState == 0 && inputChar == 'a') return 1; // handled string is "a"
  if (currentState == 0 && inputChar == 'b') return 3; // handled string is "b"
  if (currentState == 1 && inputChar == 'b') return 2; // handled string is "ab", or "abab", or ...
  if (currentState == 2 && inputChar == 'a') return 1; // handled string is "aba", or "ababa", or ...
  if (currentState == 2 && inputChar == 'b') return 3; // handled string is "abb", or "ababb", or ...
  return -1;
}

Iterate this "state machine" over your input chars, starting with state 0, and if you end up in state 3, your input is valid.

int isValid(char* inputString) {
  int state = 0;
  for(int i=0; i<str_len(inputString); i++) {
    state = nextState(state, inputString[i]);
  }

  return (state == 3);
}

Answer 2

Don't do this!

enum track {true, false};

Here your true is equal to 0 and false is equal to one! When you later assign track_pos, you may get the wrong value! (Because when converting bool to int, true converts to 1 and false converts to 0.)

That's only a guess though. Maybe it's something else that matters.

Answer 3

Things wrong with your code:

#include <iostream.h>

should be:

#include <iostream>

The following is a non-standard (and very old) header:

#include <conio.h>

The following is illegal - true and false are reserved words.

enum track {true, false};

In C and C++, main must return an int:

void main()

Non standard function:

clrscr();

No memory allocated to this pointer:

char*str;

which is then used here - result undefined behaviour:

cin>>str;

Illegal call to main:

    main();

I suspect you are using a very old and obsolete C++ compiler. You should replace it with something like MinGW.

Answer 4

I'm going to regret this, but each time I look at this question I see something else wrong with your code. Here is the line by line. I've probably missed a lot.

The correct name for this header is "iostream", not "iostream.h" - the ".h" version is deprecated. Similarly, use "string", not "string.h" in modern C++, and use the modern STL string classes.

#include <iostream.h>
#include <conio.h>
#include <string.h>

As pointed out, don't do this. You have redefined the standard bool type to have the opposite value from the standard types. I don't even know that this is legal.

enum track {true, false};

The return value of the main function is int, not void.

void main()    
{
    clrscr();

Do you know what a buffer overflow is? You have defined str as a pointer here, with no allocated memory, and you write to that undefined bit of memory a bit later on. This is undefined behaviour, and you are pretty much guaranteed to crash. I recommend, you should defined str as a std::string - this will nicely avoid the buffer overflow, and it has many useful methods that you can use in your program.

    char*str;
    enum track track_pos, track_pos_2;
    cout<<"enter the string: ";

This is the buffer overflow right here. You are writing to who knows what area of memory.

    cin>>str;

If str was a std::string - you would do size_t len=str.length();

    int len=strlen(str);
    cout<<"length of the string is "<<len;

It's probably not a good idea to mix console IO functions like this with iostreams functions - there are some buffering issues that can lead to difficulties.

    getch();

Declare i in the body of the loop, since you aren't using it again. Like so:

    for (int i=0; i<len; i++) etc...

    int i;
    for(i=0;i<len; i++)
    {

Instead of using poiter arithmetic, since you are keeping track of the index of the current character in i, just use that and treat str as an array. This way, you don't have to keep str in synch with i all of the way through. This is the cause the bug you are reporting, by the way.

        ++str;
        cout<<"loop"<<i;

You should change this to:

        if (str[i]=='a' && i%2==0)

(That works even if str is a std::string by the way, unlike the pointer arithmetic version).

        if(*str=='a' && i%2==0)
        {

You really should drop out at some point, if you figure out that the string doesn't match, then there is no point going on to the end of the string.

                cout<<"\nchecking a...";

I don't favour status flags like this - your code is partly hard to understand because of the proliferation of these flags, you cannot keep track of the proper behaviour. The name track_pos is not mnemonic, that makes it hard to work out what it is meant to signify without detailed study of the code.

I would recommend that you would refactor your code inside the body of the for loop to call a function, the purpose of which is simply to match a single group of "ab" - this function could return true if it did, and false if it did not.

                track_pos=true;
                cout<<"\na.check";

Note that since we are dealing with the buffer overflow mentioned before, you are iterating undefined memory. Also note that you did not increment i here.

                ++str;
                if (*str=='b')
                        {
                        cout<<"\nchecking b...";
                        track_pos=true;
                        cout<<"\nb.check";
                }
                else{
                        track_pos=false;
                        cout<<"\nb.uncheck";
                }
        }

    }

When we get to here, according to your for loop, we have iterated the whole string, so we must be looking past the end of the string (even ignoring the buffer overflow) so there is no possible way this test can succeed. In short, your for loop must be going too far.

    if(*str=='b')
        track_pos_2=true;
    else
        track_pos_2=false;

    if(track_pos==true && track_pos_2==true)

Should I mention the spelling mistake?

        cout<<"\nThe string is accpeted.";
    else
        cout<<"\nThe string is rejected.";

    getch();
    cout<<"\n\nDo you want to continue (Y/N)? ";
    char ch;
    cin>>ch;

If you refactor your code into appropriate sub-routines, you will find the structure of the program takes care of itself. Note that calling main recursively is not strictly illegal, but it is kind of weird and has an obvious vulnerability that will lead to an eventual stack overflow, if the program never exits.

    if(ch=='y' || ch=='Y')
        main();

}