Balanced parentheses

Question

Given an expression string exp, write a program to examine whether the pairs and the orders of

"{","}","(",")","[","]"

are correct in exp.

For example, the program should print true for

exp = "[()]{}{[()()]()}"

and false for

exp = "[(])"

Complexity:

• Time complexity: \$O(n)\$ where \$n\$ is length of string
• Space complexity: \$O(\frac{n}{2})\$ where \$n\$ is length of string

I saw the Java version and thought "I want to submit a JavaScript version." Looking for code review, optimizations, and best practices.

In my version, the string can contain other characters than parentheses, "" is accepted as input, and I did not care about short circuiting odd length strings.

function parenthesesAreBalanced(s)
{
 var parentheses = "[]{}()",
 stack = [], //Parentheses stack
 i, //Index in the string
 c; //Character in the string
 for (i = 0; c = s[i++];)
 {
 var bracePosition = parentheses.indexOf(c),
 braceType;
 //~ is truthy for any number but -1
 if (!~bracePosition)
 continue;
 braceType = bracePosition % 2 ? 'closed' : 'open';
 if (braceType === 'closed')
 {
 //If there is no open parenthese at all, return false OR
 //if the opening parenthese does not match ( they should be neighbours )
 if (!stack.length || parentheses.indexOf(stack.pop()) != bracePosition - 1)
 return false;
 }
 else
 {
 stack.push(c);
 }
 }
 //If anything is left on the stack <- not balanced
 return !stack.length;
}
console.log('{}([]) true', parenthesesAreBalanced('{}([])'));
console.log('{{ false', parenthesesAreBalanced('{{'));
console.log('[(]) false', parenthesesAreBalanced('[(])'));
console.log("{}([]) true", parenthesesAreBalanced("{}([])"));
console.log("([}]) false", parenthesesAreBalanced("([}])"));
console.log("([]) true", parenthesesAreBalanced("([])"));
console.log("()[]{}[][]", parenthesesAreBalanced("()[]{}[][]"));

• Ananda: add this check as the first validation, If the length of the expression is an odd number we can return false right away.
• konijn: @Ananda this supports non braces, "abc" and "o[]" are balanced and odd length

Answer 1

This is almost all style suggestions; the code itself looks great.

Personally, I prefer the brace-on-same-line style for everything in JS, and I prefer proper blocks instead of inlining expressions. But those are just preferences. I've also skipped the bitwise trick, added some strict comparisons instead of !stack.length etc., moved the i++ over to its "usual" place, and lengthened a few variable names, just for clarity.

Again: This is all basically pointless, but I just like spelling things out.

The only real difference is that rather than push the opening brace onto the stack, I push the position of the expected closing brace. It just makes the conditional a bit cleaner later on.

function parenthesesAreBalanced(string) {
 var parentheses = "[]{}()",
 stack = [],
 i, character, bracePosition;
 for(i = 0; character = string[i]; i++) {
 bracePosition = parentheses.indexOf(character);
 if(bracePosition === -1) {
 continue;
 }
 if(bracePosition % 2 === 0) {
 stack.push(bracePosition + 1); // push next expected brace position
 } else {
 if(stack.length === 0 || stack.pop() !== bracePosition) {
 return false;
 }
 }
 }
 return stack.length === 0;
}

---

Update: Actually, you can skip one stack.length check in the inner conditional; stack.pop() will just return undefined if the stack's empty, so this is enough:

if(stack.pop() !== bracePosition) {
 return false;
}

• konijn: I very much like the idea of pushing the bracePosition+1, +1

Answer 2

I wrote a Node/JavaScript library called balanced that can do this and much more, but the main concept I used was using a stack, compiling a regexp of the open/close tags, and then doing 1 pass. It seemed to perform better than indexOf implementations.

The way you would write your isBalanced method using balanced is

function isBalanced(string) {
 return !!balanced.matches({source: string, open: ['{', '(', '['], close: ['}', ')', ']'], balance: true});
}

Here's a live example with exceptions: JSFiddle and heres an example ignoring comment blocks JSFiddle

For your example balanced will produce the following error

Balanced: mismatching close bracket, expected ")" but found "]" at 1:3
1: [(])
-----^

• Manjeet: I like your answer. But, there are some glitches. I think you should improve it and make it better to parse whole JS function or FILE. For example: On your JS fiddle i pasted a JS line containing .replace(/[{]/g, "").replace(/[}]/g, "") . And it failed.