Match a simple balanced language

Question

I apologise if the title is not very descriptive. If someone can recommend a clearer one I'll edit it. I have an exercise question as:

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.

I've written the following code which solves the problem.

bool isInLanguageL2(string w){
 linkedStackType<string> wordStack;
 int size = w.length();
 int a = 0;
 int b = 0;
 if(size % 2 != 0) //word length must be an equal number
 return false;
 else{
 //read first half of word
 for(int i = 0; i < size/2; i++){ //check if the first half consists of A's
 if(w[i] != 'a' && w[i] != 'A')
 return false;
 else
 wordStack.push(string(1, w[i])); //convert char to string and push to stack if the letter is valid
 }
 //read second half of word
 for(int i = size/2; i < size; i++){ //check if the second half consists of B's
 if(w[i] != 'b' && w[i] != 'B')
 return false;
 else
 wordStack.push(string(1, w[i])); //convert char to string and push to stack if the letter is valid
 }
 }
 //check number of A's and B's in the stack
 while(!wordStack.isEmptyStack()){
 if(wordStack.top() == "b" || wordStack.top() == "B"){
 b++;
 wordStack.pop();
 }
 else{
 a++;
 wordStack.pop();
 }
 }
 //check if number of B's is equal to number of A's
 if(b==a)
 return true;
}

However, since the question says "Do not count the number of a’s or b’s.", I've instead created two stacks and just compared their lengths. Is there a way to do this using a single stack since the question mentions using a stack without explicitly counting the A's and B's to test the word.

bool isInLanguageL2(string w){
 linkedStackType<string> wordStackA, wordStackB;
 int size = w.length();
 int a = 0;
 int b = 0;
 if(size % 2 != 0) //word length must be an equal number
 return false;
 else{
 //read first half of word
 for(int i = 0; i < size/2; i++){ //check if the first half consists of A's
 if(w[i] != 'a' && w[i] != 'A')
 return false;
 else
 wordStackA.push(string(1, w[i])); //convert char to string and push to stack if the letter is valid
 }
 //read second half of word
 for(int i = size/2; i < size; i++){ //check if the second half consists of B's
 if(w[i] != 'b' && w[i] != 'B')
 return false;
 else
 wordStackB.push(string(1, w[i])); //convert char to string and push to stack if the letter is valid
 }
 }
 //check if number of B's is equal to number of A's
 if(wordStackA.length() == wordStackB.length());
 return true;
}

Also, I have a follow up to this question. A sort of extension. Should I add it here or create a new question for it as it might make this question rather long.

• Toby Speight: I wonder if the intent of the exercise is for you to push when you see an a, and pop when you see a b. It's an error if the stack underflows or is not empty at the end. But that would allow abab, for instance, which seems to be prohibited.
• Mike Borkland: Making a stack of a's and a stack of b's and then comparing their size is equivalent to counting them.
• Mike Borkland: I would push all the a's on the stack until a non-a character is found. Then, iterate through the remaining characters. For every remaining character, if it is not a b or the stack is empty, return false. Otherwise, pop the stack. When there are no more characters, if the stack is not empty, return false. Otherwise, return true.
• Mast: Please do not update the code in your question to incorporate feedback from answers, doing so goes against the Question + Answer style of Code Review. This is not a forum where you should keep the most updated version in your question. Please see what you may and may not do after receiving answers . Feel free to post a follow-up question instead.
• user931018: @Mast Apologies. I was not aware. Thanks for that link.

Answer 1

This exercise is somewhat unsettling. On the one hand, a stack, as part of a pushdown automaton, is the canonical way to decide balanced languages such as this one; on the other hand, there are much more efficient, idiomatic and practical ways to solve that particular exercise. It is unclear whether it's a computer science exercise or a language learning exercise, one to make concepts sink in or one to discover C++'s expressiveness.

A stack would have been more easily justified if the function argument had been a std::istream& for instance, since it can be traversed only once; or if starting / ending tags had come of different kinds (if they're all the same an integer makes for a perfect stack and counting shouldn't be discriminated).

As @Mike Borland said, the trick to answer that question is to avoid explicit counting by popping the stack filled with as while you iterate over the rest of the string. Something along the lines:

#include <stack>
#include <string>
bool is_ab_balanced(const std::string& str) {
 if (!str.size()) return false; 
 auto it = str.begin();
 std::stack<char> as;
 while (it != str.end() && *it == 'a') as.push(*it++);
 while (!as.empty()) {
 if (it == str.end() || *it != 'b') return false;
 as.pop(); ++it;
 }
 return it == str.end();
}

By the way, you'll notice that:

1. it always is better to use standardized containers unless you need customized behavior: std::stack is certainly better optimized and tested than linkedStackType<>

2. you shouldn't take a string by value as an argument, unless you intend to modify it while keeping the original string unchanged. Here, there's no modification, so use a const reference instead.

3. you should get rid of unused variables (see a and b in your second version). Those superfluous variables probably are a by-product of bad habits: declaring variables too far ahead of their use, and not enabling all warnings when you compile your code.

4. iterators are a better way to iterate over a range: it's more idiomatic, it's necessary to leverage the power of the STL, and it also avoids that extra size variable.

5. A few more key-strokes are better than using namespace std, which is is a bad idea

But, as I said, a good exercise should look more like real life. In real life, you use a stack only if it is the best way to go. So how would you check if a string belongs to the language if you could choose without restriction?

My take on that would be:

#include <string>
#include <algorithm>
using Iterator = std::string::iterator;
bool is_balanced(Iterator first, Iterator last) {
 auto middle = std::next(first, std::distance(first, last) / 2);
 return std::equal(first, middle, middle, last, [](auto a, auto b) {
 return a == 'a' && b == 'b';
 });
}

Or, other more meaningful exercises would have been:

• how would you check if parenthesis are balanced in an expression (I wouldn't use a stack here either)?

• how would you check if html tags are correctly balanced (here using a stack is meaningful)?

• Jasper: Because that's the standard non-regular language that can be decided by a pushdown automaton.
• Mike Borkland: @Jasper Understood, but computers are limited by what a Turing machine can do, not by what a pushdown automaton can do. I can understand a problem asking to describe how a pushdown automaton would decide such a lanaguage, but forcing someone to write code that work on a computer without allowing them to take full advantage of what a Turing complete programming language can do doesn't make a whole lot of sense, in my opinion.
• Konrad Rudolph: I’m sorry, I have to downvote because the first sentence is flat out wrong and quite misleading. This is the standard way of matching such a language, as Jasper noted. Not knowing this is fine but it’s still the wrong answer. The code also invokes UB on some inputs. All in all I’m a bit disappointed that this is such a highly voted answer.
• Konrad Rudolph: @MikeBorkland People use a stack for it because it means they can implement it using a less powerful formalism. This is important when building usable and efficient compiler generators. Having a Turing complete scanner system has numerous drawbacks. For the same reason we’re using CSS to style websites, rather than C++.
• papagaga: @KonradRudolph: right, fixed it!

Answer 2

papagaga makes some good points.

A few things that I'd add are:

I like the initial check about string length. In terms of the intention of the underlying question, it's kind of cheating: if you're modelling a push down automaton you don't have access to the input length before you read it. Nevertheless it's the sort of quick check that is often worth having if you don't have to comply with such arbitrary restrictions: checks that can avoid doing a bunch of unnecessary work and can simplify the problem in a way that reduces the chance of hitting bugs.

You generally want to avoid using strings to hold individual characters, because it is unnecessarily slow and expensive in terms of memory. A standard c++ string holds at least the length of the string (which you don't need to hold because it's always 1 in the entries on your stack) on top of the actual string, which means you're using up at least five times as much memory as you need!

When you get a programming task the first thing you should do is check the specification for what input is actually allowed, because that informs how complicated you have to make the code. For example, I would expect from that description that the strings would not contain capital letters, and if they did then "A" would not be considered the same symbol as "a". As such, I'd avoid checking for the capital versions.

The most important thing, though, is to make sure that you understand what concept the question is trying to explore. Measuring the size of a stack is really just an expensive way of counting characters. The key thing to note about papagaga's first version is that it doesn't need a concept of how to compare integers, whether an overt b==a or the more subtle wordStackA.length() == wordStackB.length().

Answer 3

Although you already have some good remarks about your code and a short functional solution in the accepted answer, I'd like to offer an alternative procedural solution. The observation here is that you do not actually have to count the as and bs, you just have to go through the string in two directions and check that you only encounter as on one side and bs on the other. As long as the length is even (and not zero) this will give you the right answer too:

bool isInLanguageL2(string w) {
 int len = w.length();
 // Exclude the empty string and odd-length strings
 if(len == 0 || len % 2 == 1) { 
 return false; 
 }
 // Can do this with one counter until len/2, but then 
 // you need to check index i and len - 1 - i.
 for(int front = 0, back = len - 1; front < back; ++front, --back) {
 if(w[front] != 'a' || w[back] != 'b') { 
 return false; 
 }
 }
 return true;
}

• Konrad Rudolph: Like other answers (before being edited), this one misses the point of using a stack to solve this exercise. Alternative solutions like yours work for this very specific case but don’t generalise, whereas a pushdown automaton does generalise beautifully. It’s compiler theory 101, and that’s why it’s important.