Let L be the language defined as follows:
- The words are made up of strings of a’s followed by b’s.
- The number of a’s is always equal to the number of b’s.
- Examples of words that belong to L are: ab, aabb, aaabbb etc...
One way to test if a word w belong to this language is to use a stack to check if the number of a’s balances the number of b’s.
This is what I though of doing:
- Check if the length string is even
- If it is send input to the function
- Divide length by two and push the a's onto a stack
- Reverse the string
- Divide length by two and push the b's onto a stack
- While the stack isn't empty pop each and store the count of each
- Compare the count and if they are equal then return 0 or if not return 1
Please see below for the program I implemented:
#include <iostream>
#include <string>
#include <stack>
#include <algorithm>
using namespace std;
int count1 = 0;
int count2 = 0;
bool isInLanguageL (string w);
int main()
{
string input;
cout << "Input any string; ";
getline(cin,input);
if (input.length() % 2 != 0)
cout <<"Pattern entered does not match the language ";
else
isInLanguageL(input);
return 0;
}
bool isInLanguageL (string w)
{
stack<string> word1, word2;
string a, b;
for (unsigned i = 0; i < w.length()/2; i++)
{
a = w.at(i);
word1.push(a);
}
reverse(w.begin(), w.end());
for (unsigned i = 0; i < w.length()/2; i++)
{
b = w.at(i);
word2.push(b);
}
while(!word1.empty() && !word2.empty())
{
word1.pop();
count1 = count1++;
word2.pop();
count2 = count2++;
}
if(count1 == count2)
return true;
else
return false;
}
The issue I have with this is despite it working correctly I would appreciate and opinion on it as I feel they may have been another way to approach handling the strings although after racking my brains this was the best solution I could come up with.
What seems a bit silly to me is where I am comparing counts of the two stacks as it's pretty obvious based on the fact that I am not allowing odd numbers to pass into the function that the counts will always be equal which would also be due to the division by 2 in each iteration which clearly rules out the counts ever not being equal.
Also, it's all good and well that I am using the stacks to compare counts but I'm not really doing a check here on whether or not the string matches a pattern. In my mind I would have used the approach of checking a pattern but as the question just wants to see whether a's and b's balance I thought this approach wouldn't be bad.
Any advice on how else to approach this question would be appreciated.
Thanks