7
\$\begingroup\$

I wanted to write a JavaScript function that checked for balanced braces. I'd be grateful for any feedback on correctness and style.

var invert = {
    '}': '{',
    ']': '[',
    ')': '(',
};

/**
 * Returns `true` if braces are balanced. 
 * `false` otherwise.
 * Usage: `isBalanced('{{[(')`
 */
function isBalanced(str) {
    var arr, count, curr;

    arr = splitAndFilter(str);

    /**
     * For strings containing 
     * no relevant characters, 
     * return true.
     */
    if (!arr.length) {
        return true;
    }

    count = {
        '(': 0,
        '[': 0,
        '{': 0,
    };

    for(;(curr = arr[0]) && curr; arr = rest(arr)) {
        if (isOpening(curr)) {
            count[curr] += 1;
        } else if (isPrematureClosing(curr, count)) {
            count[invert[curr]] -= 1;
            break;
        } else {
            count[invert[curr]] -= 1;
        }
    }

    return Object.keys(count)
        .every(k => count[k] === 0);
}

function splitAndFilter(str) {
    return str.split('')
        .filter(i => isOpening(i) || isClosing(i));
}

function rest(arr) {
    return arr.slice(1);
}

function isPrematureClosing(c, count) {
    return isClosing(c) && (count[invert[c]] === 0);
}

function isOpening(c) {
    return /[\{\[\(]/.test(c);
}

function isClosing(c) {
    return /[\}\]\)]/.test(c);
}

console.log('true: ', isBalanced(''));
console.log('true: ', isBalanced('({[]})'));
console.log('true: ', isBalanced('{}[]()'));
console.log('true: ', isBalanced('{{}}[[{}]]()'));
console.log('true: ', isBalanced('({})[]'));
console.log('false: ', isBalanced('())'));
console.log('false: ', isBalanced('()))'));
console.log('false: ', isBalanced('(()))'));
console.log('false: ', isBalanced('()))('));
console.log('false: ', isBalanced('()))({'));
console.log('false: ', isBalanced('({[})'));
console.log('false: ', isBalanced('({}){'));
console.log('false: ', isBalanced('()}{'));
\$\endgroup\$
  • 1
    \$\begingroup\$ Related question here \$\endgroup\$ – Flambino Nov 2 '15 at 10:34
  • 2
    \$\begingroup\$ Note that Flambino's solution in the linked question is rather neat and elegant compared to solutions presented here so far. :-) \$\endgroup\$ – holroy Nov 2 '15 at 15:37
4
\$\begingroup\$

Now assuming that we just ignore other characters, and just balance braces, then...

The first problem I see is during the parsing of the expression. Your test calls isOpening and isClosing to determine if it's a valid brace. The problem here is that on each call, you create a regular expression. They're potentially heavy, and very slow. An alternative would be to have a string of valid braces, and use indexOf to see if they're in there. There's also that rest function you call on your for loop which is slicing an array. slice creates a new shallow copy of the original array. You don't want to be creating arrays for each iteration.

Next is your algorithm which is... uhm... ok. However, your function parses all the way to the end even when there's an error in the middle. It doesn't bail out. Next is there's no debugging. I will know that it's not balance, but do I know where exactly? A thrown error is good since it makes no sense proceeding if you know it's not balance.

For an alternative solution, the simplest solution for this is using a stack. When you see an opening, you push to the stack. When it's a closing, you pop from the stack. An imbalance would be simply be:

  • An empty stack when you still encountered a closing brace (excess closing)
  • A non-empty stack when you already parsed everything (lack closing)
  • Or a mismatch of popped value and the closing value.

Here's my take on it:

function isBalanced(expression){
  
  // Our "stack" which is just an array.
  var stack = [];
  
  // Used to determine the correct closer for the popped opener
  var pairs = {
    '{': '}',
    '[': ']',
    '(': ')',
  };
  
  // The reason for not filtering is we need the index for error reporting.
  expression.split('').forEach(function(brace, index){
    
    // Since index starts with zero, we increment to make sense.
    var position = index + 1;
    
    if(!~'({[)}]'.indexOf(brace)){
      
      // If it's not a brace, return early. It doesn't affect anything.
      // We just need to take them into account for positioning.
      return;
      
    } else if(~'({['.indexOf(brace)){
      
      // If it's an opening, push to the stack      
      stack.push(brace);
      
    } else if(!stack.length){
      
      // We have exhausted the stack but we have a closer
      throw new Error('Syntax Error: Unexpected ' + brace + ' at ' + position);
      
    } else if(~')}]'.indexOf(brace)){
      
      var braceToClose = stack.pop();
      var expectedCloser = pairs[braceToClose];
      
      // If there was a mismatch in closing
      if(brace !== expectedCloser){
        throw new Error('Syntax Error: Expecting ' + braceToClose + ' at ' + position);
      }
    }
  });
  
  // If we still need closing, throw an error with the next brace to close
  if(stack.length){
    throw Error('Syntax Error: Expecting ' + pairs[stack.pop()] + ' at ' + expression.length);
  }
  
  return true;
  
}

// Check console
console.log('true: ', isBalanced(''));
console.log('true: ', isBalanced('({[]})'));
console.log('true: ', isBalanced('{}[]()'));
console.log('true: ', isBalanced('{{}}[[{}]]()'));
console.log('true: ', isBalanced('({})[]'));
console.log('false: ', isBalanced('())'));
console.log('false: ', isBalanced('()))'));
console.log('false: ', isBalanced('(()))'));
console.log('false: ', isBalanced('()))('));
console.log('false: ', isBalanced('()))({'));
console.log('false: ', isBalanced('({[})'));
console.log('false: ', isBalanced('({}){'));
console.log('false: ', isBalanced('()}{'));

| improve this answer | |
\$\endgroup\$
4
\$\begingroup\$
function splitAndFilter(str) {
    return str.split('')
        .filter(i => isOpening(i) || isClosing(i));
}

function isPrematureClosing(c, count) {
    return isClosing(c) && (count[invert[c]] === 0);
}

function isOpening(c) {
    return /[\{\[\(]/.test(c);
}

function isClosing(c) {
    return /[\}\]\)]/.test(c);
}

These factors aren't useful. Although isClosing appears a second time in isPrematureClosing, that function only makes sense as a part of isBalanced. Folding all of these into isBalanced makes it more readable rather than less, and would increase repetition by one .test(c) call if you don't also reconsider your loop logic. splitAndFilter is especially poor: anyone reading that would have to find its definition to understand what it even means.

Without changing your algorithm, but with a cleaner loop, and with some very minor style changes:

var opens = /[{([]/,
    closes = /[})\]]/,
    invert = {
      '}': '{',
      ']': '[',
      ')': '('
    }

function isBalanced(str) {
  var arr = str.split('')
               .filter(c => opens.test(c) || closes.test(c))

  var count = {
    '(': 0,
    '[': 0,
    '{': 0
  }

  var curr
  while (curr = arr.shift()) {
    if (opens.test(curr)) count[curr]++
    else count[invert[curr]]--

    if (count[invert[curr]] < 0) break
  }

  return Object.keys(count)
               .every(k => count[k] === 0)
}
| improve this answer | |
\$\endgroup\$
2
\$\begingroup\$

There is a simpler, recursive approach that you might like:

  1. Remove characters irrelevant to the matching.
  2. Replace any instance of () or [] or {} with the empty string
  3. If the result is empty, return: The string is balanced
  4. If the result is unchanged, return: The string is unbalanced.
  5. Otherwise return to step 2.

Here's the code:

function isBalanced(str) {

  var cur = removeCruft(str), next;

  while (next = removeMatchedPairs(cur)) {
      if (next === cur) return false;
      cur = next;
  }
  return true; //if we've arrived here, `next` is empty

  function removeMatchedPairs(s) { return s.replace(/\(\)|\[\]|{}/g,'') }
  function removeCruft(s) { return s.replace(/[^(){}[\]]/g,'') }
}
| improve this answer | |
\$\endgroup\$
0
\$\begingroup\$

The implementation given in the question is unfortunately wrong. It fails for the following category of input:

isBalanced('([)]'); // returns true, but should be false

Ultimately, to solve this question you need a last-in first-out (LIFO) data structure to verify the correct positioning of closing brackets (or else some "complicated" object that can find this information for you).

The categories of errors possible in this problem are:

  • missing opener (e.g. ')', or '())')
  • missing closer (e.g. '(', or '()(')
  • mismatched closer (e.g. '(]', or '([)]')

This is the best I could come up with:

const OPEN = /^[\{\[\(]/;
const CLOSE = /^[\}\]\)]/;
const INVERT = {
    '}': '{',
    ']': '[',
    ')': '(',
};

function isBalanced(str) {
    var arr, curr, stack, opener;

    arr = str.split('');
    stack = []; // LIFO!

    while (arr.length) {
        curr = arr.shift();

        if (OPEN.test(curr)) {
            stack.push(curr); // We assume openers are OK (until reaching end of `arr`). 
        } else if (CLOSE.test(curr)) {
            if (!(stack.length)) {
                return false; // Closer without any opener in current nest ("missing opener")! 
            }

            opener = stack.pop(curr); // `opener` opened the current pair. `pop` reveals the previous opener! 

            if (opener !== INVERT[curr]) {
                return false; // "Mismatched closer".
            }
        }
    }

    return !(stack.length); // "Missing closer" if anything left on the stack, otherwise, balanced.
}
| improve this answer | |
\$\endgroup\$
  • \$\begingroup\$ Have you taken a look at Flambino's solution linked to your question, for a better and neater algorithm? \$\endgroup\$ – holroy Nov 3 '15 at 20:04
  • \$\begingroup\$ @holroy Yes I have. Thanks for pointing me to it. However, I wanted to re-implement the algorithm without reference to another implementation and this is what I came up with. There are no major errors in this implementation are there? I can see some performance-related improvements in Flambino's solution. \$\endgroup\$ – 52d6c6af Nov 3 '15 at 20:10
  • \$\begingroup\$ Depending on your use case, you should also consider whether it would be needed at some point to return at which position/index the mismatch happened... \$\endgroup\$ – holroy Nov 3 '15 at 20:13

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.