Balanced parentheses

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("()[]{}[][]"));

• add this check as the first validation, If the length of the expression is an odd number we can return false right away. Oct 29 '18 at 9:37
• @Ananda this supports non braces, "abc" and "o[]" are balanced and odd length Oct 29 '18 at 12:48

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

• I very much like the idea of pushing the bracePosition+1, +1 Apr 2 '14 at 12:11

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: [(])
-----^

• 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. Sep 7 '18 at 15:50