boolean string function to determine if the parentheses are balanced

[Paul]

A problem I've just solved is to write a boolean function to determine if the parentheses in the string are balanced. My solution is substantially different from my text's suggested solution and I'd like people to offer opinions as to which solution they prefer.

Thank you.

Paul.

My solution:

#include <string>

using namespace std;

bool isBracket(char c)
{
return c=='(' || c == ')' ;
}


// A function which returns true if the parentheses in a string are balanced and false otherwise.

bool balanced(string str)
{
if(str.empty())
return true;

if(!isBracket(str[0]))
return balanced(str.substr(1, str.size()-1));

if(!isBracket(str[str.size()-1]))
return balanced(str.substr(0, str.size()-1));

return str[0] == '(' && str[str.size()-1] == ')' && balanced(str.substr(1, str.size()-2));
}

Text solution:
#include <string>
#include <stack>

using namespace std;

bool is_par_balanced(const string input)
{

stack<char> par_stack;
for(auto & c : input)
{

if(c == ')')
{

if(par_stack.empty())
return false;

else if (par_stack.top() == '(' )
par_stack.pop();

}

else if(c == '(' )
par_stack.push(c);

}


return par_stack.empty();

}

[Christopher Pisz]

Text solution is faster and uses way less memory. You are essentially
taking one string and making new string copies for each character.
Consider what is happening in both if the string is say 10MB long.

I would pass the argument as const string & input though rather than by
value, for the text solution.


--
I have chosen to troll filter/ignore all subthreads containing the
words: "Rick C. Hodgins", "Flibble", and "Islam"
So, I won't be able to see or respond to any such messages
---

[Martin Shobe]

On 5/11/2015 1:30 PM, Paul wrote:

> A problem I've just solved is to write a boolean function to determine if the parentheses in the string are balanced. My solution is substantially different from my text's suggested solution and I'd like people to offer opinions as to which solution they prefer.
>
> Thank you.
>
> Paul.
>
> My solution:
>
> #include <string>
>
> using namespace std;
>
> bool isBracket(char c)
> {
> return c=='(' || c == ')' ;
> }
>
>
> // A function which returns true if the parentheses in a string are balanced and false otherwise.
>
> bool balanced(string str)
> {
> if(str.empty())
> return true;
>
> if(!isBracket(str[0]))
> return balanced(str.substr(1, str.size()-1));
>
> if(!isBracket(str[str.size()-1]))
> return balanced(str.substr(0, str.size()-1));
>
> return str[0] == '(' && str[str.size()-1] == ')' && balanced(str.substr(1, str.size()-2));
> }

While premature optimization can be a problem, one still shouldn't be
wasteful of ones resources. This will make a copy of (part of) the
string for each non-parenthesis in the string. There's no need to copy
any of it at all. Even if you want to keep the recursive algorithm, pass
iterators into the string instead of copies.

> Text solution:
> #include <string>
> #include <stack>
>
> using namespace std;
>
> bool is_par_balanced(const string input)
> {
>
> stack<char> par_stack;
> for(auto & c : input)
> {
>
> if(c == ')')
> {
>
> if(par_stack.empty())
> return false;
>
> else if (par_stack.top() == '(' )
> par_stack.pop();
>
> }
>
> else if(c == '(' )
> par_stack.push(c);
>
> }
>
>
> return par_stack.empty();
>
> }

Again, there's some unnecessary resource use. The only characters that
can be pushed onto the stack are '('. Therefore, we can get by with just
counting the number of unmatched '(' so far, return false if that count
ever goes negative or if it's non-zero when we reach the end of the string.

As a bonus, using iterators (Warning: not tested)

#include <string>

using namespace std;

bool is_par_balanced(string::const_iterator start,
string::const_iterator end)
{
string::size_type unmatchedParens{0};

while (start != end)
{
if (*start == ')')
{
if (unmatchedParens == 0)
{
return false;
}

--unmatchedParens;
}
else if (*start == '(' )
{
++unmatchedParens;
}

++start;
}

return unmatchedParens == 0;
}

Martin Shobe

[Jorgen Grahn]

On Mon, 2015-05-11, Paul wrote:

> A problem I've just solved is to write a boolean function to
> determine if the parentheses in the string are balanced. My solution
> is substantially different from my text's suggested solution and I'd
> like people to offer opinions as to which solution they prefer.

Neither.

> My solution:
>
> #include <string>
>
> using namespace std;
>
> bool isBracket(char c)
> {
> return c=='(' || c == ')' ;
> }
>
>
> // A function which returns true if the parentheses in a string

> // are balanced and false otherwise.

>
> bool balanced(string str)
> {
> if(str.empty())
> return true;
>
> if(!isBracket(str[0]))
> return balanced(str.substr(1, str.size()-1));
>
> if(!isBracket(str[str.size()-1]))
> return balanced(str.substr(0, str.size()-1));
>
> return str[0] == '(' && str[str.size()-1] == ')' && balanced(str.substr(1, str.size()-2));
> }

Recursion. Looks complicated -- especially when you touch both ends
of the string -- and I'm not convinced it's correct.

It probably is though: you're saying when you've shaved off
non-brackets at both ends, the string is either empty or you have a
balanced string enclosed in (), or it's not balanced at all.

On second thought, it's not. Try "(foo)(bar)". You can't claim
"foo)(bar" is balanced, can you?

> Text solution:
> #include <string>
> #include <stack>
>
> using namespace std;
>
> bool is_par_balanced(const string input)
> {
>
> stack<char> par_stack;

Weird. Whose text is that? What's wrong with this one? Seems pretty
straightforward, once you've defined your terms.

/**
* True if parenthesis are balanced in [a, e), meaning no group is
* closed which isn't started, and no group is left unclosed in the
* end.
*/
template<class Iter>
bool balanced(Iter a, Iter e)
{
unsigned d = 0;
while(a != e) {
if (*a == '(') {
d++;
}
if (*a == ')') {
if(d==0) return false;
d--;
}
a++;
}
return d==0;
}

Way more efficient and general than your solution. And unless I'm
mistaken, correct too.

/Jorgen

--
// Jorgen Grahn <grahn@ Oo o. . .
\X/ snipabacken.se> O o .

[Paavo Helde]

Paul <peps...@gmail.com> wrote in
news:91246830-921f-4ae3...@googlegroups.com:

> A problem I've just solved is to write a boolean function to determine
> if the parentheses in the string are balanced. My solution is
> substantially different from my text's suggested solution and I'd like
> people to offer opinions as to which solution they prefer.
>
> Thank you.
>
> Paul.
>
> My solution:
>
> #include <string>
>
> using namespace std;
>
> bool isBracket(char c)
> {
> return c=='(' || c == ')' ;
> }
>
>
> // A function which returns true if the parentheses in a string are
> balanced and false otherwise.
>
> bool balanced(string str)
> {
> if(str.empty())
> return true;
>
> if(!isBracket(str[0]))
> return balanced(str.substr(1, str.size()-1));
>
> if(!isBracket(str[str.size()-1]))
> return balanced(str.substr(0, str.size()-1));
>
> return str[0] == '(' && str[str.size()-1] == ')' &&
> balanced(str.substr(1, str.size()-2));
> }

This is extremely inefficient (recursion plus zillions of string copies).

> Text solution:
> #include <string>
> #include <stack>
>
> using namespace std;
>
> bool is_par_balanced(const string input)
> {
>
> stack<char> par_stack;
> for(auto & c : input)
> {
>
> if(c == ')')
> {
>
> if(par_stack.empty())
> return false;
>
> else if (par_stack.top() == '(' )
> par_stack.pop();
>
> }
>
> else if(c == '(' )
> par_stack.push(c);
>
> }
>
>
> return par_stack.empty();
>
> }

This is also a bit inefficient. There is no need to use a stack, a simple
integer counter which is incremented and decremented would be enough.

This kind of stack would become handy if there are more than one kind of
parens and one wants to check that they are matched correctly. Most
probably this will be discussed in the next chapter of the textbook and
that's the only reason to use a stack here.

Cheers
Paavo

[Paavo Helde]

Paul <peps...@gmail.com> wrote in
news:91246830-921f-4ae3...@googlegroups.com:

> A problem I've just solved is to write a boolean function to determine
> if the parentheses in the string are balanced. My solution is
> substantially different from my text's suggested solution and I'd like
> people to offer opinions as to which solution they prefer.
>
> Thank you.
>
> Paul.
>
> My solution:
>
> #include <string>
>
> using namespace std;
>
> bool isBracket(char c)
> {
> return c=='(' || c == ')' ;
> }
>
>
> // A function which returns true if the parentheses in a string are
> balanced and false otherwise.
>
> bool balanced(string str)
> {
> if(str.empty())
> return true;
>
> if(!isBracket(str[0]))
> return balanced(str.substr(1, str.size()-1));
>
> if(!isBracket(str[str.size()-1]))
> return balanced(str.substr(0, str.size()-1));
>
> return str[0] == '(' && str[str.size()-1] == ')' &&
> balanced(str.substr(1, str.size()-2));
> }

Oh, and it fails on "(a+b)*(c+d)".

Cheers
Paavo

[Richard]

[Please do not mail me a copy of your followup]

Paul <peps...@gmail.com> spake the secret code
<91246830-921f-4ae3...@googlegroups.com> thusly:

>A problem I've just solved is to write a boolean function to determine
>if the parentheses in the string are balanced. My solution is
>substantially different from my text's suggested solution and I'd like
>people to offer opinions as to which solution they prefer.

The functional problems with your code would easily have been
discovered by writing some unit tests. If you don't know how to do
this, look at my presentation from C++ Now! 2014:
<https://github.com/boostcon/cppnow_presentations_2014/tree/master/files/test_driven>

>bool isBracket(char c)
>{
> return c=='(' || c == ')' ;
>}

This is a misleading name. A better name: isParenthesis. Here you've
chosen camelCase identifiers for your function and later you choose
underscore_words identifiers for your function. Pick one identifier
convention and use it consistently.

Even in this one line you're not using whitespace consistently.
Either omit the whitespace around comparison operators, or use it
around them consistently. For some reason you've also got extra
whitespace before the semi-colon, but nowhere else.

>bool balanced(string str)

Strings should be passed by const reference.

> if(!isBracket(str[0]))
> return balanced(str.substr(1, str.size()-1));

Even when strings are passed by const reference, this makes a copy of
the entire string every time you invoke your routine recursively. As
already suggested, using a pair of iterators would be an algorithm
that more naturally fits with the standard library. I might have a
std::vector<char> or std::list<char> that I'd like to know if it's
balanced. With your code I'd first have to copy that into a string,
just to know a read-only property of the sequence. That seems
wasteful and awkward.

Also, I see no justification for stripping the trailing character
simply because the first character is a parenthesis. Why isn't
"(foo) " balanced?

>Text solution:
>#include <string>
>#include <stack>
>
>using namespace std;
>
>bool is_par_balanced(const string input)
>{
>
> stack<char> par_stack;
> for(auto & c : input)
> {
>
> if(c == ')')
> {
>
> if(par_stack.empty())
> return false;
>
> else if (par_stack.top() == '(' )
> par_stack.pop();
>
> }
>
> else if(c == '(' )
> par_stack.push(c);
>
> }
>
>
> return par_stack.empty();
>
>}

It's still doing unnecessary data copying, but this solution is better
than yours because it's only copying the parenthesis around and not
the entire string. In this case the stack is only acting as a counter
and a boolean (was the last thing an open paren or a close paren?) and
it would be clearer to me if the code simply tracked the count and a
boolean. This solution also feels easier to understand than yours
because your code is using misleading identifiers (what's a bracket
got to do with a parenthesis?) and syntactically noisy substring
extraction that is not only irrelevant to the problem, but also
erroneous.

If I was interviewing candidates for a job and this was a question I'd
asked them to cdoe for me, I'd prefer the book over you for the job.
--
"The Direct3D Graphics Pipeline" free book <http://tinyurl.com/d3d-pipeline>
The Computer Graphics Museum <http://computergraphicsmuseum.org>
The Terminals Wiki <http://terminals.classiccmp.org>
Legalize Adulthood! (my blog) <http://legalizeadulthood.wordpress.com>

[Juha Nieminen]

What exactly would be the problem in simply going through the string
in a simple loop, and counting opening and closing parentheses?

If you encounter an opening parenthesis, increase the counter. If you
encounter a closing parenthesis, decrease it. If the counter at any
point gets negative, it's unbalanced. If the counter is not zero at
the end, it's unbalanced.

--- news://freenews.netfront.net/ - complaints: ne...@netfront.net ---

[Paul]

On Tuesday, May 12, 2015 at 8:08:02 AM UTC+1, Juha Nieminen wrote:
> What exactly would be the problem in simply going through the string
> in a simple loop, and counting opening and closing parentheses?
>
> If you encounter an opening parenthesis, increase the counter. If you
> encounter a closing parenthesis, decrease it. If the counter at any
> point gets negative, it's unbalanced. If the counter is not zero at
> the end, it's unbalanced.

Yes, I did that here, and it's along the lines of Jorgen Grahn's code. I've become a bit obsessed with recursion. My recursion seemed to work (although actually it doesn't work) so I didn't feel a need to try something else. Many thanks to everyone on this thread. All your comments are helpful. This is my latest attempt which people are also welcome to comment on.

Paul

#include <string>

using namespace std;

// A function which returns true if the parentheses in a string are balanced and false otherwise.
bool balanced(string str)
{

int num_open_bracket = 0;
int num_closed_bracket = 0;

for(int i = 0; i < str.size(); i++)
{
if(str[i] == '(')
num_open_bracket++;

if(str[i] == ')')
num_closed_bracket++;

if(num_closed_bracket > num_open_bracket)
return false;
}

return num_open_bracket == num_closed_bracket;
}

[Paul]

Sorry, the signature should have been bool balanced(const string& str) as others have said. I was listening to the thread commenters. Sometimes I get obsessed on some parts of the problem and ignore other elements.

Paul

[Richard]

[Please do not mail me a copy of your followup]

Paul <peps...@gmail.com> spake the secret code

<9d6ff177-69a6-4ea5...@googlegroups.com> thusly:

>This is my latest attempt which people are also
>welcome to comment on.

This is much better. A few minor suggestions still.

(By the way, this sort of "do something and get feedback from peers"
is exactly what exercism.io is all about. I implemented the C++
language track there. This discussion inspired me to add a
"Balanced parenthesis" problem to exercism.)

>// A function which returns true if the parentheses in a string are
>balanced and false otherwise.

>bool balanced(const string &str)

A better name might be:

bool balanced_parenthesis(const string &str)

Then the comment is redundant because the intention is revealed in the
name of the function.

>{
> int num_open_bracket = 0;
> int num_closed_bracket = 0;
>
> for(int i = 0; i < str.size(); i++)
> {
> if(str[i] == '(')
> num_open_bracket++;
>
> if(str[i] == ')')
> num_closed_bracket++;
>
> if(num_closed_bracket > num_open_bracket)
> return false;
> }
>
> return num_open_bracket == num_closed_bracket;
>}

There's nothing here that really depends on the container being a
std::string, so you can generalize this algorithm with iterators:

template <typename Iter>
bool balanced_parenthesis(Iter begin, Iter end)

{
int num_open_bracket = 0;
int num_closed_bracket = 0;

for (; begin != end; ++begin)
{
if (*begin == '(')
{
num_open_bracket++;
}

if (*begin == ')')
{
num_closed_bracket++;
}

if (num_closed_bracket > num_open_bracket)

{
return false;
}
}

return num_open_bracket == num_closed_bracket;
}

I've modified the formatting slightly: control structures are not
function calls, so don't write them like function calls and statement
blocks should always be enclosed in {}'s as per CERT security
guidelines.
<https://www.securecoding.cert.org/confluence/pages/viewpage.action?pageId=42729941>

You can collapse the two local variables into one:

template <typename Iter>
bool balanced_parenthesis(Iter begin, Iter end)
{
int depth = 0;

for (; begin != end; ++begin)
{
if (*begin == '(')
{
depth++;
}

if (*begin == ')')
{
depth--;
}

if (depth < 0)
{
return false;
}
}

return depth == 0;
}

As a general rule, we should prefer prefix increment and decrement
operators over postfix operators when we don't need the old value:

template <typename Iter>
bool balanced_parenthesis(Iter begin, Iter end)
{
int depth = 0;

for (; begin != end; ++begin)
{
if (*begin == '(')
{
++depth;
}

if (*begin == ')')
{
--depth;
}

if (depth < 0)
{
return false;
}
}

return depth == 0;
}

The current character can never be both an open paren and a closing
paren, so testing both of these one after another is redundant:

template <typename Iter>
bool balanced_parenthesis(Iter begin, Iter end)
{
int depth = 0;

for (; begin != end; ++begin)
{
if (*begin == '(')
{
++depth;
}
else if (*begin == ')')
{
--depth;
}

if (depth < 0)
{
return false;
}
}

return depth == 0;
}

The depth can only be negative if we just decremented it:

template <typename Iter>
bool balanced_parenthesis(Iter begin, Iter end)
{
int depth = 0;

for (; begin != end; ++begin)
{
if (*begin == '(')
{
++depth;
}
else if (*begin == ')')
{
--depth;
if (depth < 0)
{
return false;
}
}
}

return depth == 0;

[Victor Bazarov]

On 5/12/2015 1:38 PM, Richard wrote:
> [Please do not mail me a copy of your followup]
>
> Paul <peps...@gmail.com> spake the secret code
> <9d6ff177-69a6-4ea5...@googlegroups.com> thusly:
>
>> This is my latest attempt which people are also
>> welcome to comment on.
>
> This is much better. A few minor suggestions still.
>

> [..]

>
>> // A function which returns true if the parentheses in a string are
>> balanced and false otherwise.
>> bool balanced(const string &str)
>
> A better name might be:
>
> bool balanced_parenthesis(const string &str)

[..]

Just a nit-pick. A single parenthesis is never balanced. The plural
form is better:

bool balanced_parentheses(cosnt string &str)

V
--
I do not respond to top-posted replies, please don't ask

[Scott Lurndal]

r...@zedat.fu-berlin.de (Stefan Ram) writes:
> Distribution through any means other than regular usenet
>
> channels is forbidden. It is forbidden to publish this
>
> article in the world wide web. It is forbidden to change
>
> URIs of this article into links. It is forbidden to remove
>
> this notice or to transfer the body without this notice.
>X-No-Archive: Yes
>Archive: no
>X-No-Archive-Readme: "X-No-Archive" is only set, because this prevents some
>
> services to mirror the article via the web (HTTP). But Stefan Ram
>
> hereby allows to keep this article within a Usenet archive server
>
> with only NNTP access without any time limitation.

What is all this double-spaced scheisse?


> The second == is evaluated even if the first one was true.
> I'd use an »else« there.
>
>bool is_balanced( ::std::string const & s )
>{ auto top = s.size(); signed long long c{ 0 };
> for( int i = 0; i < top; ++i )
> { switch( s[ i ]){ case '(': ++c; break; case ')': --c; }
> if( c == LLONG_MAX || c == LLONG_MIN )
> throw ::std::overflow_error( "too many parentheses" );
> if( c < 0 )return 0; } return !c; }
>
> (untested). The optimizer might have accomplished this before,
> but not we can be sure that »s.size()« is only evaluated once
> and »s[ i ]« is only evaluated once per loop.
>
> Use s.at( i ) for an additional layer of security.
>
> Or using a pointer:
>
>bool is_balanced( ::std::string const & s )
>{ auto top = s.size(); signed long long c{ 0 };
> char const * b = s.c_str(); char const * e = b + top;
> for( char const * p = b; p < e; ++p )
> { switch( *p ){ '(': ++c; break; ')': --c; }
> if( c == LLONG_MAX || c == LLONG_MIN )
> throw ::std::overflow_error( "too many parentheses" );
> if( c < 0 )return 0; } return !c; }
>
> (untested). But this pointer style might be too low-level in C++.
>
> Maybe it should be a template?
>
>templace< typename C, typename T, typename A >
>bool is_balanced( ::std::basic_string< C, T, A >const & s )
>...
>
> (untested). Maybe it should be preceded by »constexpr«?
>

This is far more readable, yet untested.

bool balanced(std::string &str, char open = '(');

/**
* Return true if the enclosing characters are
* balanced.
*
* @note: A character will be considered regardless of
* whether or not it is quoted (with ', ", \, », or «).
*
* @param str A reference to the string to analyze
* @param open The opening character (one of '(', '[', or '{')
* @returns true if the character represented by 'open' is balanced.
*/
bool balanced(std::string &str, char open)
{
char closed = (open == '(')?open+1:open+2;
size_t count = 0ul;

if ((open != '(') && (open != '[') && (open != '{')) return false;

for(auto i: str) {
if (i == open) count++, continue;
if (i == closed) {
if (count == 0) return false;
--count;
}
}
return count == 0;
}

On an EBCDIC system:

uint8_t closed = (open == '[')?open+1:open+16;

[Scott Lurndal]

r...@zedat.fu-berlin.de (Stefan Ram) writes:

>legaliz...@mail.xmission.com (Richard) writes:
>>statement blocks should always be enclosed in {}'s
>

> What is a »statement block«?
>

AKA a compound statement. Richard is putting forth
a style guideline; don't cheat and eliminate the {}
when there is only a single statement.

e.g. He prefers:
if (fred)
{
i++;
}

instead of
if (fred) i++;


While I agree, generally, there is a large community of
developers (linux kernel engineers) who vociferously disagree.

(My preference comes from the punched card days when it was
easier to insert a statement when the {} (BEGIN/END in the day) were already there;
one wouldn't need to re-punch the control statement).

It does also make patches (diffs) look cleaner.

[Richard]

[Please do not mail me a copy of your followup]

Victor Bazarov <v.ba...@comcast.invalid> spake the secret code
<mitgu7$djq$1...@dont-email.me> thusly:

I like it!

[Richard]

[Please do not mail me a copy of your followup]

sl...@pacbell.net spake the secret code
<wSr4x.47936$cX.3...@fx28.iad> thusly:

> AKA a compound statement. Richard is putting forth
>a style guideline; don't cheat and eliminate the {}
>when there is only a single statement.

In the CERT coding standard, it is a recommendation. However, it is a
recommendation because there are actual security bugs that have been
caused by omitting the braces.

[Drew Lawson]

In article <aOr4x.47715$cX.3...@fx28.iad>

sl...@pacbell.net writes:
>r...@zedat.fu-berlin.de (Stefan Ram) writes:
>> Distribution through any means other than regular usenet
>>
>> channels is forbidden. It is forbidden to publish this
>>
>> article in the world wide web. It is forbidden to change
>>
>> URIs of this article into links. It is forbidden to remove
>>
>> this notice or to transfer the body without this notice.
>>X-No-Archive: Yes
>>Archive: no
>>X-No-Archive-Readme: "X-No-Archive" is only set, because this prevents some
>>
>> services to mirror the article via the web (HTTP). But Stefan Ram
>>
>> hereby allows to keep this article within a Usenet archive server
>>
>> with only NNTP access without any time limitation.
>
>What is all this double-spaced scheisse?

It is stuff that was in the message headers, and is not double
spaced at all. It is a Header line with continuation lines.

What client are you using that displays unimportant (i.e., X-)
headers?

--
Drew Lawson So risk all or don't risk anything
You can lose all the same

[Chris Vine]

Leaving that aside, it is a ridiculous copyright notice to put in a
newsnet post's headers because as you say it is illegible in most
readers, and would be breached by anyone including the body of the
posting in their reply ("It is forbidden to remove this notice or to
transfer the body without this notice").

It seems like somewhat typical rubbish from Stefan which can be
ignored. Minor academics do seem to waste their time on the most
trivial and absurd things.

Chris

[Scott Lurndal]

Indeed.

FWIW, my client (see headers) considers the headers to end when
there are two consecutive CRLF sequences in the article as fetched
from the news server. For whatever reason, Stefan's article
appeared to have two consecutive CRLF sequences in his added headers;
possibly a server error, possibly a posting client error, possibly
a reading client error. I've not the time to track it down.

[red floyd]

Not to mention web-based Usenet readers...

[Richard]

[Please do not mail me a copy of your followup]

sl...@pacbell.net spake the secret code

<uBJ4x.106952$Iw.2...@fx11.iad> thusly:

>FWIW, my client (see headers) considers the headers to end when
>there are two consecutive CRLF sequences in the article as fetched
>from the news server.

This isn't just your client's consideration; it's the definition of
the separation of headers from message body in the RFCs.

[Jason C. McDonald]

On 05/11/2015 11:30 AM, Paul wrote:
> A problem I've just solved is to write a boolean function to determine if the parentheses in the string are balanced. My solution is substantially different from my text's suggested solution and I'd like people to offer opinions as to which solution they prefer.
>
> Thank you.
>
> Paul.
>
> My solution:
>
> #include <string>
>
> using namespace std;
>
> bool isBracket(char c)
> {
> return c=='(' || c == ')' ;
> }

I've actually had to write this sort of function a few different times.
For me, the most efficient solution was closer to yours, except it only
required one loop, two branches, and an integer.

bool isBalanced(string str)
{
int b;

for(int i=0; i<str.length(); i++)

{
if(str[i] == '(')

b++;
else if(str[i] == ')')
b--;
}

return (b == 0);
}

The way it works is fairly simple, and it has the side-effect of being
able to determine exactly HOW it isn't balanced.

- If b = 0, the parenthesis are balanced.
- If b > 0, abs(b) is the number of extra opening parenthesis.
- if b < 0, abs(b) is the number of extra closing parenthesis.

(Incidentally, I'm neck-deep in writing a lexer for an interpreted
language on top of C++.)

--
Jason C. McDonald (CodeMouse92)
[CEO, Lead Dev @ MousePaw Games]

[Jason C. McDonald]

> bool isBalanced(string str)
> {
> int b;
>
> for(int i=0; i<str.length(); i++)
> {
> if(str[i] == '(')
> b++;
> else if(str[i] == ')')
> b--;
> }
>
> return (b == 0);
> }
>
> The way it works is fairly simple, and it has the side-effect of being
> able to determine exactly HOW it isn't balanced.
>
> - If b = 0, the parenthesis are balanced.
> - If b > 0, abs(b) is the number of extra opening parenthesis.
> - if b < 0, abs(b) is the number of extra closing parenthesis.
>

Ironically, I have to follow up to my OWN post, because USENET just
updated, and I noticed a good observation from someone else.

On 05/11/2015 12:12 PM, Jorgen Grahn wrote:> On Mon, 2015-05-11, Paul wrote:
> On second thought, it's not. Try "(foo)(bar)". You can't claim
> "foo)(bar" is balanced, can you?

Modifying my own code to account for that, one would need to throw an
error as soon as b < 0, as that would indicate that discrepancy.

Thus, rewriting.

bool isBalanced(string str)
{
int b;

for(int i=0; i<str.length(); i++)
{
if(str[i] == '(')
b++;
else if(str[i] == ')')
b--;

if(b < 0)
{
//Breaking is sufficient, as it will force
//the return of a negative b.
break;
}
}

//Ideally, we'd want to return an integer
//so we could specify what went wrong.
return (b == 0);

[Paavo Helde]

"Jason C. McDonald" <"i n d e l i b l e b l u e p e n "@ g m a i l . c
o m . i n v a l i d> wrote in news:mj0jad$3et$1...@dont-email.me:

> Thus, rewriting.
>
> bool isBalanced(string str)
> {
> int b;

Still not initialized...

[Jason C. McDonald]

On 05/13/2015 10:33 PM, Paavo Helde wrote:
> "Jason C. McDonald" <"i n d e l i b l e b l u e p e n "@ g m a i l . c
> o m . i n v a l i d> wrote in news:mj0jad$3et$1...@dont-email.me:
>> Thus, rewriting.
>>
>> bool isBalanced(string str)
>> {
>> int b;
>
> Still not initialized...

Ah, I can't believe I missed that. Should be `int b = 0;`. Thanks for
the catch.

[Juha Nieminen]

Richard <legaliz...@mail.xmission.com> wrote:
> template <typename Iter>
> bool balanced_parenthesis(Iter begin, Iter end)
> {
> int depth = 0;
>
> for (; begin != end; ++begin)
> {
> if (*begin == '(')
> {
> ++depth;
> }
> else if (*begin == ')')
> {
> --depth;
> if (depth < 0)
> {
> return false;
> }
> }
> }
>
> return depth == 0;
> }

If you allow your inner C hacker go wild, you can make it much shorter:

template <typename Iter>
bool balanced_parentheses(Iter begin, Iter end)

{
int depth = 0;
for(; begin != end; ++begin)

if((depth += (*begin == '(') - (*begin == ')')) < 0)

return false;
return depth == 0;
}

[Victor Bazarov]

I was thinking more in the line of making the "open" and "close" symbols
arguments of the function (or even the template) instead:

template<char open_c, char close_c, typename Iter>
bool balanced_(Iter begin, Iter end) ...

and make balanced_parentheses, balanced_quotes typedef'ed

template<class Iter> using balanced_parentheses
= balanced_<'(',')', Iter>;

:-)

[Richard]

[Please do not mail me a copy of your followup]

"Jason C. McDonald" <"i n d e l i b l e b l u e p e n "@ g m a i l . c o m . i n v a l i d> spake the secret code
<mj0ism$1vp$1...@dont-email.me> thusly:

>(Incidentally, I'm neck-deep in writing a lexer for an interpreted
>language on top of C++.)

Do checkout Boost.Spirit, it's really nice for writing lexers and
parsers.

[Richard]

[Please do not mail me a copy of your followup]

Juha Nieminen <nos...@thanks.invalid> spake the secret code
<mj21en$2t4q$1...@adenine.netfront.net> thusly:

>If you allow your inner C hacker go wild, you can make it much shorter:

I fired that guy around 1993 (Mr. "C hacker"). The goal of writing
code that is easy to understand isn't to minimize the number of tokens
present in the code. Otherwise everything would evolve into entries in
the obfuscated C contest. OH WAIT. That's why we fired Mr. C Hacker
in the first place.

[James Moe]

On 05/11/2015 11:30 AM, Paul wrote:
> bool isBracket(char c) {
> return c=='(' || c == ')' ;
> }
>

Since the test is indiscriminate about opening and closing parentheses,
your function will approve:

" )oops(."


--
James Moe
jmm-list at sohnen-moe dot com

[asetof...@gmail.com]

Juha wrote:"
template <typename Iter>

bool balanced_parentheses(Iter begin, Iter end)
{
int depth = 0;
for(; begin != end; ++begin)
if((depth += (*begin == '(') - (*begin == ')')) < 0)
return false;
return depth == 0;
}"

i32 pairedPar(u8* b, u8* fin )
{u8 *p;
i32 s;
if(b==0||fin==0||b>fin)
return -1;
for(p=b, s=0; p<fin; ++p)
{ if(*p=='(') ++s;
else if(*p==')') --s;
if(s<0) return 0;
if(s>0xFFFFFF)
return -1;
}
if(s>0) return 0;
return 1;
}

[Öö Tiib]

On Thursday, 14 May 2015 19:50:13 UTC+3, Richard wrote:
> [Please do not mail me a copy of your followup]
>
> Juha Nieminen <nos...@thanks.invalid> spake the secret code
> <mj21en$2t4q$1...@adenine.netfront.net> thusly:
>
> >If you allow your inner C hacker go wild, you can make it much shorter:
>
> I fired that guy around 1993 (Mr. "C hacker"). The goal of writing
> code that is easy to understand isn't to minimize the number of tokens
> present in the code. Otherwise everything would evolve into entries in
> the obfuscated C contest. OH WAIT. That's why we fired Mr. C Hacker
> in the first place.

The needless complexity in Juha's code is that assignment inside
of if that looks shorter but possibly actually even adds useless
branches in generated binary.

Both of codes (yours and Juha's) are mildly hackish in sense that
both reuse the "begin" iterator of range to iterate over range.
Modern compilers do such optimizations.

Predicate functions are easier to read when the name is the fact
that it returns (for example "parentheses_are_balanced").
It is like method "empty" of std containers has confusing name
because it is possible to interpret it as verb. Lot better
name: "is_empty".

[Jason C. McDonald]

On 05/14/2015 09:48 AM, Richard wrote:
> [Please do not mail me a copy of your followup]
>
> "Jason C. McDonald" <"i n d e l i b l e b l u e p e n "@ g m a i l . c o m . i n v a l i d> spake the secret code
> <mj0ism$1vp$1...@dont-email.me> thusly:
>
>> (Incidentally, I'm neck-deep in writing a lexer for an interpreted
>> language on top of C++.)
>
> Do checkout Boost.Spirit, it's really nice for writing lexers and
> parsers.
>

Hi Richard,

Thanks for the tip. I'll look into it, though I'll let you know that I'm
trying to avoid external libraries where possible. We have an unusually
ambitious backward comparability goal, so I generally avoid external
libraries for that reason.

[Juha Nieminen]

Richard <legaliz...@mail.xmission.com> wrote:
> Juha Nieminen <nos...@thanks.invalid> spake the secret code
> <mj21en$2t4q$1...@adenine.netfront.net> thusly:
>
>>If you allow your inner C hacker go wild, you can make it much shorter:
>
> I fired that guy around 1993 (Mr. "C hacker"). The goal of writing
> code that is easy to understand isn't to minimize the number of tokens
> present in the code. Otherwise everything would evolve into entries in
> the obfuscated C contest. OH WAIT. That's why we fired Mr. C Hacker
> in the first place.

Sounds rather nitpicky to me.

Sure, I wouldn't write that exact kind of code in an actual program
(instead using two conditionals), but wouldn't be extraordinarily
verbose either. Verbosity does not add readability.

And what's "hackish" and what's not can be a matter of opinion. For
example, consider the archetypal "C style" way of implementing strcpy:

void MyStrCpy(char* dest, const char* src)
{
while((*dest++ = *src++)) {}
}

This is, admittedly, quite a "C-hacker" style of coding, but anybody
with any kind of C/C++ experience would understand what it's doing.
Would there be any benefit in doing it more verbosely? If a maintenance
programmer does not have enough experience with the language to understand
that line, then perhaps he shouldn't be maintaining the program in
the first place? Would you hire a programmer who understands what that
line is doing, or one who doesn't?

Consider that even completely "kosher" C++ code can become a lot more
obscure than that. (Consider, for instance, more complex cases of
variadic template implementations.)

[Richard]

[Please do not mail me a copy of your followup]

"Jason C. McDonald" <"i n d e l i b l e b l u e p e n "@ g m a i l . c o m . i n v a l i d> spake the secret code

<mj2t8s$m3h$1...@dont-email.me> thusly:

Boost.Spirit is a header-only library, if that makes any difference.
It has a permissive license that is commercial software friendly.