Comparing a string using a stack

Question

Let L be the language defined as follows:

1. The words are made up of strings of a’s followed by b’s.
2. The number of a’s is always equal to the number of b’s.
3. 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:

1. Check if the length string is even
2. If it is send input to the function
3. Divide length by two and push the a's onto a stack
4. Reverse the string
5. Divide length by two and push the b's onto a stack
6. While the stack isn't empty pop each and store the count of each
7. 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'm 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'm 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!

Answer 1

At least to me, this seems like an excessively complex design.

I'd guess the intent is to create something on the order of a pushdown automata. In other words, the code processes a stream of incoming characters one at a time, with no global view of all the incoming data, and (almost) no memory other than the stack.

The obvious way to do this would be to read a character of input. If it's an 'a', push it onto the stack, and repeat. If it's a 'b', pop one 'a' from the stack, and repeat:

stack<char> inputs;

char ch;

while ((ch = getinput()) == 'a')
    inputs.push(ch);

while (ch == 'b') {
    if (inputs.empty())
        error("Mismatch: more 'b's than 'a's");
    inputs.pop(ch);
    ch = getinput();
}

if (!inputs.empty())
    error("mismatch: more 'a's than 'b's");

Note that we're not really using any of the data we push onto the stack though--we're basically just using its depth (which can lead to an even simpler design, but on that doesn't appear to fit the specifications).

Answer 2

Your solution uses two stacks when in reality you only need one:

bool isInLanguage(const std::string &str)
{
    std::stack<char> st;
    for (const auto &c : str) {
        if (c == 'a') {
            st.push(c);
        } else if (c == 'b') {
            if (st.empty()) {
                return false;
            } else {
                st.pop();
            }
        } else { // only 'a' and 'b' allowed
            return false;
        }
    }
    return st.empty();
}

You don't even need to really use a stack in this case as a simple counter works fine:

bool isInLanguage(const std::string &str)
{
    std::size_t count = 0;
    for (const auto &c : str) {
        if (c == 'a') {
            ++count;
        } else if (c == 'b') {
            --count;
        } else {
            return false;
        }
    }

    return count == 0;
}