Validate that brackets are balanced

Question

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;
}

Answer 1

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.

Answer 2

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;

Answer 3

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.

Answer 4

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

Answer 5

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