Match a simple balanced language using a queue

Question

I asked a similar question here which is:

The language L={aⁿbⁿ} where n ≥ 1, is a language of all words with the following properties:

• The words consist of strings of a’s followed by b’s.
• The number of b’s is equal the number of a’s.
• Examples of words that belong to L are:

ab, where n=1;

aabb, where n=2;

aaabbb, where n=3;

aaaabbbb, where n=4.

One way to test if a word w belong to this language L is to use a stack to check if the number of a’s balances the number of b’s. Use the following header and write a function isInLanguageL2 that uses a stack to test if any word belongs to L. If w belongs to L then the isInLanguageL2 should return true otherwise isInLanguageL2 should return false.

bool isInLanguageL(string w);

Note the following:

• Only words belonging to L should be accepted.
• The word bbaa does not belong to L.
• Do not count the number of a’s or b’s.

A follow up to that question asks to redo the question using queues (I realize a queue probably isn't the best way to do this, however that's not the point of the exercise):

Repeat the previous question using the following header:

bool isInLanguageL(queueType< char> & w);

My solution for doing this without actually counting the a's and b's is below. It uses two queues. I "copy" all the a's from the original queue into a temp queue and remove them from the original queue which should have only b's remaining. I then iterate through the temp queue and pop the original queue for every a that is in the temp queue. After checking through the temp queue and if both queues are empty at the end, then the word is valid.

My question: How can I accomplish this using a single queue as I think using a temporary queue would be a waste of memory.

My code:

bool isInLanguageL(linkedQueueType<char> &w){

    linkedQueueType<char> temp;

    if(w.front() != 'a')    //queue must start with an a
        return false;

    while(w.front() == 'a'){ //iterate through the a's and add them to temp queue
        temp.addQueue(w.front());
        w.deleteQueue();    //remove a's from original queue
    }

    while(!temp.isEmptyQueue() && !w.isEmptyQueue()){    //delete b for each a
        if(w.front() != 'b')    //only b's should remain in original queue
            return false;
        else{
            w.deleteQueue();
            temp.deleteQueue();
        }
    }

    //both stacks must be empty then number of b=a and word is valid
    if(w.isEmptyQueue() && temp.isEmptyQueue())
        return true;
    return false;
}

int main()
{

    linkedQueueType<char> wordQueue;
    std::string word;

    std::cout << "Enter a word belonging to language L. ";
    std::cin >> word;

    for(int i = 0; i < word.length(); i++){
        wordQueue.addQueue(word[i]);
    }

    if(isInLanguageL(wordQueue))
        std::cout << word << " is a valid word.";
    else
        std::cout << word << " is not a valid word.";

    return 0;
}

Answer 1

As Konrad Rudolph points out in comments on the other question, this is probably about Pushdown Automata, for which the wikipedia page has some useful examples, and this stackoverflow answer is very helpful.

---

Using a stack

The stack is used to preserve data while iterating along the input. We move left-to-right from character to character, making a decision based on the current character, and the contents of the stack.

If the input becomes invalid at a certain point (e.g. it contains a 'c', or has too many 'b's, etc.), we can reject it. Otherwise we continue until we have processed the entire input.

For the instructions you've been given, we don't actually need a stack. A counter would suffice. However, a stack would allow balancing multiple sets of characters (e.g. balancing strings of parentheses ([]())[]).

At every 'a' we encounter, we push it onto the stack. At every 'b' we encounter, we pop one off the stack. If we are ever attempting to pop something off an empty stack, the input is not balanced. At the end of the input, the stack must be empty (we popped off the same number of 'b's as the number of 'a's we pushed on).

bool is_balanced(std::string const& input)
{
    if (input.empty()) // n == 0
        return false;

    std::stack<char> stack;
    bool is_first_word = true;

    for (auto c : input)
        if (!pda(stack, is_first_word, c))
            return false;

    return stack.empty();
}

---

The queue

As you noticed, having the input contained in a queue limits how it can be processed. We don't know the length of the input in advance. We can only pop off one character at a time and process it.

More usually in C++, input like this would come from a stream of some sort.

Note, however, that the core of the algorithm remains exactly the same:

bool is_balanced(std::queue<char>& input)
{
    if (input.empty()) // n == 0
        return false;

    std::stack<char> stack;
    bool is_first_word = true;

    while (!input.empty())
    {
        auto c = input.front();
        input.pop();

        if (!pda(stack, is_first_word, c))
            return false;
    }

    return stack.empty();
}

---

Making Decisions

The details of the pda function are left to the reader ;) , but it looks something like this:

bool pda(std::stack<char>& stack, bool& is_first_word, char c)
{
    if (c == 'a')
    {
        // check the stack, push / pop, return true / false
    }
    else if (c == 'b')
    {
        // check the stack, push / pop, return true / false
    }
    else
        return false; // invalid character
}

It checks the current character 'c', checks the stack, and pushes / pops if necessary. It returns true if we should keep processing input, and false otherwise.

---

Weird Things

There are a few slightly unusual things about the instructions you've been given:

• Empty input is invalid (n must be >= 1). Often an empty input would be considered a balanced string. This is a simple check to make though.
• Only 'a' and 'b' characters means the stack is technically redundant. Usually one would think about balancing parentheses, as in the linked stackoverflow question.
• The wording implies that inputs like "abab" are invalid, as this would be considered more than one "word" in the specified language. This is the reason for the is_first_word boolean above. It might be simpler to just ignore this to start with.