Skip to main content
Code Review

Return to Answer

avoid ub in is_ab_balanced
Source Link
papagaga
papagaga
  • 5.8k
  • 12
  • 25
#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();
}

#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 == 'a') as.push(*it++);
    while (!as.empty()) {
        if (it == str.end() || *it != 'b') return false;
        as.pop(); ++it;
    }
    return it == str.end();
}

#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();
}
taking Konrad Rudolph's and Jerry Coffin's remarks into account
Source Link
papagaga
papagaga
  • 5.8k
  • 12
  • 25

I'm not really fondThis 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, becauseone to make concepts sink in or one to discover C++'s expressiveness.

A stack would have been more easily justified if the usefunction 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 here is not only artificial but also unintuitiveand counting shouldn't be discriminated).

As @Mike Borland said, the ideatrick to answer that question is probably 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 == 'a') as.push(*it++);
    while (!as.empty()) {
        if (it == str.end() || *it != 'b') return false;
        as.pop(); ++it;
    }
    return it == str.end();
}

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)?

I'm not really fond of this exercise, because the use of a stack here is not only artificial but also unintuitive.

As @Mike Borland said, the idea is probably 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) {
    auto it = str.begin();
    std::stack<char> as;
    while (*it == 'a') as.push(*it++);
    while (!as.empty()) {
        if (it == str.end() || *it != 'b') return false;
        as.pop(); ++it;
    }
    return it == str.end();
}

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 == 'a') as.push(*it++);
    while (!as.empty()) {
        if (it == str.end() || *it != 'b') return false;
        as.pop(); ++it;
    }
    return it == str.end();
}

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)?

Source Link
papagaga
papagaga
  • 5.8k
  • 12
  • 25

I'm not really fond of this exercise, because the use of a stack here is not only artificial but also unintuitive.

As @Mike Borland said, the idea is probably 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) {
    auto it = str.begin();
    std::stack<char> as;
    while (*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';
    });
}