3
\$\begingroup\$

I've done a test for a job (which I failed) and I'd like to know in which ways my code could've been better.

Here are the questions and my answers, it's not very long.

1) Make a program that checks if a string has balanced parentheses or brackets.

  • Braces: (), [], <>
  • For every closing brace, there must've been an opening, and for every open there must be a closure
  • return 1 if it's balanced, or 0 if it isn't

My code:

const verify = (string) => {

    // Array of the type of braces
    var braces = ["(", ")", "[", "]", "<", ">"];
    // Array half the length of braces Array
    var balanced = Array.apply(null, {length: braces.length/2}).map(function() { return 0; });

    for(let i = 0; i < string.length; ++i) {
        let char = string[i], braceIndex = braces.indexOf(char);

        if ( braceIndex == -1 ) { 
            // If current char is not any type of brace, continue.
            continue;
        }

        // Get the index of the brace found halved and floored
        let braceBalancingIndex = braceIndex / 2, braceFloor = Math.floor( braceBalancingIndex );

        // If the halved index is equal to the index, then it must be an opening, else it must be a closing
        if (braceBalancingIndex == braceFloor) {
            balanced[braceFloor]++;
        }
        else {
            balanced[braceFloor]--;
        }

        // If at any type being, the balance is negative, there was a closing without opening
        for(let j = 0; j < balanced.length; ++j) {
            if (balanced[j] < 0) return 0;
        }

    }

    // If at the end the string is not balanced, there where more openings than closings
    for(let i = 0; i < balanced.length; ++i) {
        if (balanced[i] != 0) return 0;
    }

    return 1;
}
\$\endgroup\$
  • \$\begingroup\$ Note that the accepted solution actually does not work. \$\endgroup\$ – Mike Brant Nov 18 '16 at 18:06
0
\$\begingroup\$

I don't have a lot of experience with JavaScript, so I'll write a pseudo-code algorithm for you that would be a little more efficient.

function IsBalanced(inputString) {

    var parenCount, bracketCount, angleCount = 0;

    for (var i = 0; i < inputString.Length; i++) {

        var checkChar = inputString[i];

        parenCount += (checkChar == '(' ? 1 : 0);
        parenCount -= (checkChar == ')' ? 1 : 0);
        bracketCount += (checkChar == '[' ? 1 : 0);
        bracketCount -= (checkChar == ']' ? 1 : 0);
        angleCount += (checkChar == '<' ? 1 : 0);
        angleCount -= (checkChar == '>' ? 1 : 0);

        if (parenCount < 0 || bracketCount < 0 || angleCount < 0)
            return 0;
    }

    return ((parenCount + bracketCount + angleCount) != 0 ? 0 : 1);
}

Or, without the ternary operators:

function IsBalanced(inputString) {

    var parenCount, bracketCount, angleCount = 0;

    for (var i = 0; i < inputString.Length; i++) {

        var checkChar = inputString[i];

        if (checkChar == '(') parenCount++;
        if (checkChar == ')') parenCount--;
        if (checkChar == '[') bracketCount++;
        if (checkChar == ']') bracketCount--;
        if (checkChar == '<') angleCount++;
        if (checkChar == '>') angleCount--;

        if (parenCount < 0 || bracketCount < 0 || angleCount < 0)
            return 0;
    }

    if (parenCount != 0) return 0;
    if (bracketCount != 0) return 0;
    if (angleCount != 0) return 0;

    return 1;
}

So what is happening here is you know that for every open bracket there must be a close, so if we count all the opens, and subtract all the closes, that resulting number must equal zero.

\$\endgroup\$
  • 1
    \$\begingroup\$ Thanks! This is the idea, but each brace type must have its own balance, I mean, you can't close ( with > \$\endgroup\$ – Aramil Rey Nov 17 '16 at 2:21
  • \$\begingroup\$ You are right, let me modify it... \$\endgroup\$ – Ron Beyer Nov 17 '16 at 2:22
  • 1
    \$\begingroup\$ This is good too, but in the case that during the string there where closing brackets without openings this would return true. For example, the string ']][[' would evaluate as balanced, but it isn't. I get the idea, in concept is very similar to what I've done but more specific to the braces asked alone. For every closing brace, there must've been an opening \$\endgroup\$ – Aramil Rey Nov 17 '16 at 2:31
  • 1
    \$\begingroup\$ In JavaScript, it should be inputString.length, not inputString.Length. Also, by convention, the function name should be isBalanced. \$\endgroup\$ – 200_success Nov 17 '16 at 3:08
  • 2
    \$\begingroup\$ This doesn't work. Consider {[(])} In this case, none of your counters would ever go below 0 in your loop to trigger failure, but all counters would end up at 0, giving a false positive. Counters are not enough. Order in which opening/closing brackets are encountered matters. The thought of simply iterating over the string is the directionally correct approach however. \$\endgroup\$ – Mike Brant Nov 18 '16 at 18:01
6
\$\begingroup\$

At its heart, this is a stack problem. You can get O(n) worst-case performance and O(n) space complexity by simply iterating the string in place, pushing opening brackets onto a stack and when encountering a closing bracket, popping the last item off stack to compare against.

You need to end up with an empty stack, and you can never have a case where you try to read out of an empty stack. This in addition, of course to making sure items you are comparing out of the stack match appropriately. So, there are three failure scenarios.

The solution I present might technically be optimized by hard-coding the opening and closing bracket values into conditionals and such, but I find this solution more flexible and easier to maintain from a code standpoint, as you have decoupled the bracket "configuration" from the code logic.

var balanced = '({[test string](test [string])})';
var unbalanced = '{()}]';
var empty = '';

var bracketConfig = [
    { left: '{', right: '}' },
    { left: '[', right: ']' },
    { left: '(', right: ')' }
];

function isBalanced(subject, bracketConfig) {
    // not shown - perhaps validate subject as string and error out if failing

    // build bracket arrays from config
    var openingChars = [];
    var closingChars = [];
    bracketConfig.forEach( (item) => {
        openingChars.push(item.left);
        closingChars.push(item.right);
    });

    var stack = [];
    for (var i = 0, len = subject.length; i < len; i++) {
        var char = subject[i];
        var openIdx = openingChars.indexOf(char);
        var closeIdx = closingChars.indexOf(char);
        if (openIdx > -1) {
            stack.push(openIdx);
        } else if (closeIdx > -1) {            
            if (stack.length === 0) return 0;
            lastIdx = stack.pop();
            if(lastIdx !== closeIdx) return 0;
        }
    }

    if (stack.length !== 0) return 0;
    return 1;     
}

// run tests
console.log(isBalanced(balanced, bracketConfig));
console.log(isBalanced(unbalanced, bracketConfig));
console.log(isBalanced(empty, bracketConfig));

JSFiddle of this example

My guess is that, for your interview, they were really looking to see that you could identify this as a stack problem and come up with a reasonable implementation.

\$\endgroup\$
  • \$\begingroup\$ It's worth pointing out that the specification never explicitly states that the delimiters must nest properly, even though that is a requirement in the classic balanced-delimiters problem. Perhaps the poster failed the interview for failing to seek clarification about the requirements. \$\endgroup\$ – 200_success Nov 19 '16 at 16:30
  • \$\begingroup\$ Why is lastIdx a global variable? \$\endgroup\$ – 200_success Nov 19 '16 at 16:33
3
\$\begingroup\$

Simple balanced brace checker.

The quickest way to solve the problem is to use the Javascript RegExp (regular expression) It is used to search strings. It is a complicated object to master but well worth the effort as it will save you 100's of lines of code.

To solve if some string str has balanced braces you need two regular expressions and some assumptions

  • If there are no brace characters then the string is balanced
  • If the total number of braces is an odd number the string can not be balanced
  • If after removing all non brace characters you can not find a pair of facing braces (eg facing pair []) then it is not balanced
  • A balanced str with non brace characters removed will always have at least one facing pair of braces.

Using those rules a simple function can quickly work out if a string is balances. It will not have to iterate (the do while loop) any more than the depth of the deepest nested braces.

As a complete function

function parenthesesAreBalanced (str) {
    var len;
    var reduceRegExp = /(\[\])|(\(\))|(<>)/g; // to remove facing pairs

    str = str.replace(/[^\[\]\(\)<>]+/g,""); // remove all non parentheses
    if (str.length === 0) { return 1; }      // no braces balanced
    if (str.length % 2) { return 0; }        // odd length then not balanced.
    do { // Remove facing pairs until there are no more to remove.
        len = str.length;
        str = str.replace(reduceRegExp, ""); // remove all facing pairs
    } while (len !== str.length)
    if (str.length === 0) { return 1; }      // Balanced and good. :)
    return 0;                                // UnBalanced and bad. :(
} 

As a parallel solution.

With not to much effort the regexp searches can be done on the GPU via webGL making this solution a highly parallel solution.

Thus the max cycle count is the depth of the deepest matching pair + 1. That can be no more than str.length / 2 + 1;

\$\endgroup\$
  • \$\begingroup\$ I wish I could master regular expressions, thanks for the contribution. \$\endgroup\$ – Aramil Rey Nov 17 '16 at 19:05
  • 1
    \$\begingroup\$ This would seem to unnecessarily iterate over the subject string. There is no reason you should ever need to read the characters out of the string more than once, as is happening here by repeated calls to replace(). Also while regex certainly give you a powerful tool for working with strings, I don't know that it is needed here. Depending on javascript engine running this code, the regex may or may not introduce unnecessarily slow approach vs. simple string manipulation. \$\endgroup\$ – Mike Brant Nov 18 '16 at 17:48
  • \$\begingroup\$ @MikeBrant for those that know how to use regExp this function is less complex than other solutions. I have a reasonable assumption that any string manipulation technique will not perform as well. This would be more so if the set of parentheses were to be extended and function seen as of n characters check if n types of open/close delimiters are balanced. Personally the c++ answer is by far the best here but sadly javascript is not a safe language for recursion (until tail call optimization is standard). I will test all the functions here for performance. \$\endgroup\$ – Blindman67 Nov 18 '16 at 18:09
  • 1
    \$\begingroup\$ @Blindman67 My concern is not so much the regex performance itself, but rather the repeated iteration over the string that is inherent in this approach. Every time you call the replace() function you iterate the string (or what remains of it), meaning that you can end up "touching" (reading out, comparing against regex, etc.) each of the bracket characters in the string multiple times, which isn't really necessary. On complex strings with many levels of bracket nesting this could begin to show performance problems compared to single iteration through string. But as always, test and see. \$\endgroup\$ – Mike Brant Nov 18 '16 at 18:28
  • 1
    \$\begingroup\$ @Blindman67 Great conversation. I ran some test cases as well, and I can validate your findings. I am convinced that (at least on my Chrome browser) that the uses cases where regex really shines are the larger more complex balanced input strings. Where the string iteration approach seems to potentially perform better are for unbalanced inputs where the breaking syntax error happens earlier in the string (I would need to run more randomized tests to better understand where a "breakeven" point may be). So it might come down to testing with data the OP really expects the application to handle. \$\endgroup\$ – Mike Brant Nov 18 '16 at 19:48
-1
\$\begingroup\$

The solution that I presented was using stack push and pop method. There are some givens that we know it going to fail:

  1. The last bracket must be a closing bracket otherwise, it fails.
  2. The first bracket must be an opening bracket otherwise, it fails.
  3. It must be an even number since bracket must be in pairs.

The solution I implemented was to push from last closing bracket into balanced stack until it reaches opening bracket, then it must pair up with with closing bracket in the balanced stack, if it doesn't match at top of balanced stack then it fails. If it matches then pop the closing bracket off the balanced stack. The balanced stack only stores closing brackets. arr is an array that stores all brackets that need to be iterated through from last to first bracket. The balanced bracket must be empty at the end in order to pass.

var open  = ['[','<','('];
var close = [']','>',')'];

var isBalanced = function(br){
  let balanced = [];

  let arr = br.replace(/[^\(\)\<\>\[\]]/g,'').split(''); //brackets only

    if(arr.length % 2 !== 0) return 0; // must be an even pair

    for(let i=arr.length-1; i>=0; i--){
        if(close.indexOf(arr[i])>=0) //check if it is a closing bracket
            balanced.push(arr[i]);
        else{  // if bracket match, then pop off balanced array
            if(open.indexOf(arr[i])!==close.indexOf(balanced[balanced.length-1]))
                return 0;
            else
                balanced.pop();
        }
    }
    return (balanced.length>0)?0:1;
};

console.log(isBalanced('<>[ccg[<a>]]b([09])'));   // 1
console.log(isBalanced('<[[<>>]]([])'));          // 0
console.log(isBalanced('][<>]]([])'));            // 0
console.log(isBalanced('foo(bar);'));             // 1
\$\endgroup\$
-1
\$\begingroup\$

a bit late but anyway, there is my vision. Absolutely straightforward, stack-based approach. Comparing with other stack-based solutions this one is easy to read and understand. Possibly one would like to add checking for subject string without braces at all (using RegExp or other means) to avoid unnecessary iterating through input string. Not sure however if using RegExp will be faster than iterating

function verify(txt)
{
    if (!txt) return 1;

    var stack = [];
    var n = txt.length;
    while (n--)
    {
        switch (txt.charAt(n))
        {
            case ')': stack.unshift(')'); break;
            case ']': stack.unshift(']'); break;
            case '>': stack.unshift('>'); break;
            case '<':
                if (stack.shift() === '>') break;
                return 0;
            case '[':
                if (stack.shift() === ']') break;
                return 0;
            case '(':
                if (stack.shift() === ')') break;
                return 0;
        }
    }
    return +(stack.length === 0);
}

UPD This solution is focused on the being as simple and straightforward (also easy to read and understand) as possible. For the 'under hood' logic you can check Mike Brant's answer above (or Ctrl+F for 'At its heart, this is a stack problem')

Because of its simplicity we also getting runtime gain 30% (FF.61) to 70% (Chromium 68.0), see jsperf:braces-balance

\$\endgroup\$
  • 3
    \$\begingroup\$ Welcome to Code Review! You have presented an alternative solution, but haven't reviewed the code. Please explain your reasoning (how your solution works and why it is better than the original) so that the author and other readers can learn from your thought process. Please read Why are alternative solutions not welcome? - From Review \$\endgroup\$ – Sᴀᴍ Onᴇᴌᴀ Sep 4 '18 at 21:05
  • \$\begingroup\$ Just down-voting will not help to improve the answer :( I propose that any careful reader did not miss great explanation of the 'magic' behind stack-based approach by Mike Brant (just scroll up a few or Ctrl+F for 'At its heart, this is a stack problem'). On the dark side Mike's solution is over engineered, and unexact as well (note OP question brackets pairs and Mike's solution pairs). One can want to compare runtime metrics of those two solutions jsperf: proposed solution has almost 30% gain comparing with original one (FF.61) \$\endgroup\$ – djfd Sep 6 '18 at 16:03
  • \$\begingroup\$ As for being over engineered I mean that there is an exact question for exact conditions, not looking for extensible one. And moreover, at when I was solving this exact question, there was an explicit statement: "You need to consider three kinds: (), [], <> and only these kinds". Imagine, chinese developer will add also add 【】pair, and maybe even 左右 pair. Indian guy will add something else, etc. We have an exact question and need to provide an exact solution. Again, the answer is focused on the being as straightforward and easy to read and understand as possible, as a bonus we get 30% gain \$\endgroup\$ – djfd Sep 6 '18 at 16:19

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.