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