6
\$\begingroup\$

Firstly I was using regex to get if the number of parentheses in a string is balanced or not, but the performance was quite slow when any large string was passed to the regex. So I created this custom method, which returns whether a string contains balanced parentheses or not. Please review this code and point out any mistakes and improvements.

checkBalancedBrackets(str) {
    var b1 = [];
    var b2 = [];
    for ( var i=0; i < str.length; i++ ) {
        var ch = str.charAt(i);
        if (ch == "(" ) b1.push(ch);
        else if ( ch == "[" ) b2.push(ch);
        else if ( ch == ")" ) {
            if (b1.length < 1) {
                return false;
            } else {
                b1.pop();
            }
        }
        else if ( ch == "]" ) {
            if (b2.length < 1) {
                return false;
            } else {
                b2.pop();
            }
        }
    }
    return b1.length == 0 && b2.length == 0;
}
\$\endgroup\$
  • \$\begingroup\$ codereview.stackexchange.com/questions/147259/… see this. \$\endgroup\$ – aviboy2006 Jan 14 at 11:34
  • \$\begingroup\$ Also this actually: codereview.stackexchange.com/q/45991/14625 \$\endgroup\$ – konijn Jan 14 at 11:49
  • \$\begingroup\$ 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. Please consider waiting for a day and posting a follow-up question with the new code linking back to this one instead. \$\endgroup\$ – Mast Jan 14 at 12:59
  • 1
    \$\begingroup\$ oops, will keep that in mind next time \$\endgroup\$ – New Coder Jan 14 at 13:03
  • \$\begingroup\$ Make a copy of the string, omitting any character that is not [](). While [] or () are present in the copy, remove them. If any characters remain in the copy, the original string was not balanced. \$\endgroup\$ – John Gordon Jan 14 at 22:10
5
\$\begingroup\$

A short review;

  • checkBalancedBrackets("([)]") returns true, not sure that was the intention
  • b1 and b2 are not great names, what does the b stand for?
  • Using arrays is not needed, all the code does is counting numbers, you can just use numbers
  • The inconsistent use of curly braces in your if and else if clauses is not good
|improve this answer|||||
\$\endgroup\$
  • 2
    \$\begingroup\$ "You can just use numbers" — only if [(]) should really count as balanced. Otherwise you do need an array. \$\endgroup\$ – Roland Illig Jan 14 at 18:46
1
\$\begingroup\$

You have the right idea, and your function almost works, but your code is only checking that ( is balanced with ), and [ is balanced with ]. So it will handle cases like aaa(bbb[ccc]ddd)eee correctly. But it will also accept aaa(bbb[ccc)ddd]eee, and that is wrong.

You should only have a single stack, and you should push all the opening brackets onto it. When you get a closing bracket, pop off the most recent opening bracket and make sure it matches.

Here I've taken your code and replaced the two stacks with one, which I've given a more meaningful name.

def checkBalancedBrackets(str) {
    var bracketStack = [];
    for (var i=0; i < str.length; i++) {
        var ch = str.charAt(i);
        // For opening brackets, we push the character that will match them
        if      (ch == "(") bracketStack.push(")");
        else if (ch == "[") bracketStack.push("]");
        else if (ch == ")" || ch == "]") {
            if (bracketStack.length < 1) {
                return false;
            } else {
                match = bracketStack.pop();
                if (ch != match) {
                    return false
                }
            }
        }
    }
    return bracketStack.length == 0;
}
|improve this answer|||||
\$\endgroup\$
0
\$\begingroup\$

The only numbers one should use in coding are 0, 1, and many.

This code implicitly uses 2, the number of special cases, "[]" and "()", for which you wrote code. So right away you know the fundamental design is wrong.

If this were a real program and next week your boss told you to handle "<>" as well, you'd have to write another section of code. Then next year you're asked to handle "«»" too. If it had been written properly, each time you'd only have to add those characters to a table and not make any changes to the actual code. As it is, you'll have to make extensive changes to the code, especially if you've already corrected it to check for proper nesting (e.g. "[(])" is wrong).

The key to writing this is keeping track of what state your string is in at any point: which bracket type is it immediately within. Hint: try stacking the opening characters as you encounter them.

|improve this answer|||||
\$\endgroup\$
  • \$\begingroup\$ Why should I "only use numbers 0, 1, many", and not, say, 12 or 365 or 100, which are all well-known? \$\endgroup\$ – Roland Illig Jan 14 at 18:47
  • \$\begingroup\$ @RolandIllig, because numbers might need to be changed in the future. If you define something like: [ [ '[', ']'], ['(', ')'] ] and your code works with that, you'll only have to add , ['<', '>'] to make it work with angle-brackets. If your code knows that there are two pairs of brackets, you'll have to significantly change it in order to make it work with additional kinds of brackets. \$\endgroup\$ – Ray Butterworth Jan 14 at 19:51
  • \$\begingroup\$ @RolandIllig, It's okay to use numbers that are part of a well-known formula and not intrinsic to the code. But generally most numbers can be computed. E.g. monthNames.length. One reason is if the data changes someday, the code won't break. It's unlikely we'll add another month, but what if there is another number that can change and it has the same value? "12" could occur for other purposes, and searching for all instances of "12" won't make it easy to determine which ones need to change and which ones don't. If the raw number "12" never occurs, nothing needs to be done. \$\endgroup\$ – Ray Butterworth Jan 14 at 19:52
  • 2
    \$\begingroup\$ I think there is a good start of an answer in here somewhere, but it's written a bit convoluted. It starts by stating a truth that isn't generally considered a truth (so a source might be in order). The idea of using characters in a table or map is sound and would majorly improve maintainability if done right, but then you start talking about states of string. You can't make a state machine without violating your first statement, adding to the unclarity. I'm sure it can be salvaged. \$\endgroup\$ – Mast Jan 14 at 20:40
  • \$\begingroup\$ @Mast, I don't understand your last statement. How does "if it is an open character, push it; if it is a close character, if it matches the top of the stack, pop it, otherwise it's a mismatch" violate my first statement? \$\endgroup\$ – Ray Butterworth Jan 15 at 0:49

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.