Checking if parentheses are balanced

Question

This script checks if parentheses are balanced. I wonder if there is something that can be improved here including ES6 features.

function isBalanced(str) {
    var stack = [];
    const allowedSymbols = '()[]<>';

    for(let i = 0, l = str.length; i < l; i++) {
        var c = str[i];
        var isOpen;
        var symbolPosition = allowedSymbols.indexOf(c);

        if(!~symbolPosition) {
            continue;
        }

        isOpen = symbolPosition % 2 ? false : true;

        if(isOpen) {
            stack.push(c);
        } else {
            if(stack.length < 1 || allowedSymbols.indexOf(stack.pop()) !== symbolPosition - 1) {
                return false;
            }
        }
    }

    return stack.length < 1;
}

console.log('()', isBalanced('()')); //true
console.log(')(', isBalanced(')(')); //false

()( looks balanced, but not well-formed. (And if (!~allowedSymbols.indexOf(c)) continue; suggests significant rather than allowed.) — greybeard
– greybeard, Commented Oct 9, 2016 at 14:42

Community · Accepted Answer · 2017-04-13 12:40:41Z

I linked to a very related question in a comment, and this will repeat some points from my answer to that other question. Still, there are some other things here.

Don't do stack.push(c). Do stack.push(symbolPosition + 1) instead. I.e. push the expected position, not the current character. When you just push the character, you have to call indexOf again later to get that character's symbol position when you pop it off of the stack. By just pushing the position to the stack to begin with, you avoid that. And by adding 1 when pushing it, you get a cleaner conditional, since you can just do stack.pop() !== symbolPosition
If you do the above, you don't need stack.length < 1 before the stack.pop() call either. Nothing will break if the stack's empty; pop() will just return undefined which won't match any symbol position, and thus trigger the return false.
I'd skip the isOpen variable. Sure, it might help explain what that modulo operation means, but you only need the result once. I'd rather put the explanation in a comment, and skip the single-use variable.
Similarly, I'd skip the c variable, which - if you follow the first point above - is also only used once (and whose single-letter name doesn't help explain much), and just do indexOf(str[i]).
I'd change the last line to return stack.length === 0 just to be explicit. Yes the result is the same, but the intent is clearer in my opinion. "Is the stack empty?" versus "Is the stack's length less than 1?". You could also do return !stack.length but that's unnecessarily cryptic.

In the end you get something like:

function isBalanced(str) {
    var stack = [];
    const allowedSymbols = '()[]<>';

    for(let i = 0, l = str.length; i < l; i++) {
        var symbolPosition = allowedSymbols.indexOf(str[i]);

        if(!~symbolPosition) {
            continue;
        }

        if(symbolPosition % 2 === 0) {
            stack.push(symbolPosition + 1);
        } else {
            if(stack.pop() !== symbolPosition) {
                return false;
            }
        }
    }

    return stack.length === 0;
}

As others have pointed out, you can do some tweaking with regard to const vs let vs var, but I'll leave that to you.

Joshua Dawson · Accepted Answer · 2016-10-08 20:24:10Z

Great work!

However, you're going to run into problems if you test your code on strings like:

isBalanced("if (i <= 10) { }");

Personally, I find allowedSymbols = "()[]{}"; more practical

The keyword const

You can use const stack = []; since your pointer never changes from the initial array. The keyword const only cares if the variable is assigned something else. It doesn't matter if the thing it points to is mutated.

Code clarity

I think you could format some of your code more clearly. Specifically, inside the for loop:

for (let i = 0; i < str.length; i++) {
  let c = str[i];
  let symbolPosition = allowedSymbols.indexOf(c);

  if (symbolPosition !== -1) {
    let isOpen = symbolPosition % 2 === 0;

    if (isOpen) {
      stack.push(symbolPosition);
    }
    else {
      let lastPosition = stack.pop(); // If you call pop() on an empty array, it returns undefined.

      if (allowedSymbols.indexOf(lastPosition) !== symbolPosition - 1) {
        return false;
      }
    }
  }
}

This way you avoid using continue, and you don't call pop inside an if statement's conditional.

I would also recommend shorter variable names. Your code is not that long, and a lot of the information about a variable can be deduced from its initialization.

function isBalanced(str) {
  const stack = [];
  const brackets = '()[]<>';

  for (let i = 0; i < str.length; i++) {
    const b = brackets.indexOf(str[i]);

    if (b !== -1) {
      if (b % 2 === 0) { // is open bracket
        stack.push(b);
      }
      else {
        const last = stack.pop();

        if (brackets.indexOf(last) !== b - 1) { // if brackets don't match
          return false;
        }
      }
    }
  }

  return stack.length === 0;
}

Unit Tests

Here's an easy to use, basic testing suite for your code:

// Basic testing suite
function testIsBalanced(input, expectedOutput) {
  if (isBalanced(input) !== expectedOutput) {
    throw "Failed test for input: " + input;
    // console.error("Failed test for input: " + input);
  }
}

testIsBalanced("[]", true);
testIsBalanced("()", true);
testIsBalanced("{}", true);
testIsBalanced("({}[])", true);
testIsBalanced("({([{({()})}])})", true);
testIsBalanced("[&](param1){ std::cout << param1 << std::endl; }", true);
testIsBalanced("{if (x) {objects[i][key] === correct()} else { } {([])} }", true);

testIsBalanced("{[}]", false);
testIsBalanced("{", false);
testIsBalanced(")", false);
testIsBalanced("[{]", false);

console.log("all tests passed");

ES6

If you're feeling frisky, you could use Array.prototype.forEach, and an arrow function for your string to iterate through the chars, but I wouldn't recommend it.

let str = "Hello World";
Array.prototype.forEach.bind(str)((c)=>{
  console.log(c);
});

The biggest reason against it is code clarity. Another reason is that the code runs less efficiently since forEach has to call the lambda (the arrow function) at each step of the iteration.

SoEzPz · Accepted Answer · 2016-10-10 15:26:43Z

If you could include a bit more test cases we could be sure to assist you in refactoring your code snippet with a little more clarity.

As it stands now, if we run your function isBalanced we get the following

isBalanced('()') => true;
isBalanced(')') => false;
isBalanced('(') => false;
isBalanced(')(') => false;

// Same behavior for [] and <> as stated above.

*****BUT********
isBalanced('{}') => true;
isBalanced('') => true;
isBalanced("}{") => true;
isBalanced("lajghashgjkhsag") => true;
isBalanced(null) => "Uncaught TypeError: Cannot read property 'length' of null(…)"

I'm going to assume this is not what you wanted to do. Instead, I will assume that you want to check that the following pairs match and if not always return false and don't bomb out because null was passed in.

// ES 6
function isBalanced(str){
  return ["()", "[]", "<>"].includes(str);
}

// ES 5
function isBalanced(str){
  return ["()", "[]", "<>"].some(function(match){
    return match === str;
  });
}

RESULTS

isBalanced('()') => true;
isBalanced(')') => false;
isBalanced('(') => false;
isBalanced(')(') => false;

// Same behavior for [] and <> as stated above.

*****AND********
isBalanced('{}') => false;
isBalanced('') => false;
isBalanced("}{") => false;
isBalanced("lajghashgjkhsag") => false;
isBalanced(null) => false

Stack Exchange Network

Checking if parentheses are balanced

3 Answers 3

You must log in to answer this question.

Linked

Hot Network Questions

Checking if parentheses are balanced

3 Answers 3

You must log in to answer this question.

Linked

Related

Hot Network Questions