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;
}

• papagaga: The answer is exactly the same as the one to your other question. Since there is no difference in reading "aaa..." from left to right or right to left, it doesn't matter whether you use a FIFO queue or a LIFO stack. Just change std::stack to std::queue and you're done.
• user931018: In the previous question I could use the length of the string to iterate through the stack and pop it. But using the queue, the amount of elements is unknown to me so I can't follow the same approach. Using the Queue ADT class provided to me by the textbook I cannot determine the length of the queue without writing a count() function to count the number of elements which I believe I'm not supposed to do.
• papagaga: Oh, yes, sorry, queue replaces string, not stack. But why would you need to know how many chars are in the queue? Just push into the stack the as popped out of the queue; then pop bs from the queue and as from the stack and test if they're emptied out at the same time.
• user931018: @papagaga Knowing the size of the queue would make it easy to iterate through, as in my previous question where I used the stack. I suppose I could use a stack as you suggest, but again it leaves me using two data structures, so I might as well be using two queues like I already am. You pretty much suggested what I'm already doing, but replacing one of the queues with a stack. (However I think this might be my fault for not stating the question with more clarity. I want to know if it's possible to accomplish the task using only queues, but only using a single queue).

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.