I just implemented the balanced parentheses problem in JavaScript. For those of you who are new to this problem, a statement of it would be:
Give a string of parentheses (including braces and square brackets), check to see if they are opened and closed in order. The last opened parens should be closed first before others. '[()]{}{()()}' is balanced. However, '( (] ([)]' is not.
Here is my solution:
Algorithm
Take a string input, such as '{([])}'. (Let's call each of the characters a 'paren'.)
- We validate the input, check if it is a string and has at least one paren.
- We initialize a stack and iterate through the string input.
- If the character is a closing paren, we check to see if it is the matching, closing paren of the top stack element. Note: This checks for the order, as the latest open parens have to be closed first in a balanced string of parens.
- If the character is an open paren, we push it onto the stack.
- If step 3 fails, even once, return false.
- After the loop, if the stack is empty, return true. (If all open parens were closed in order, the stack will be empty.)
var parenthesesAreBalanced = function(str) {
var stack = new Stack(), l = str.length,
currentVal, position, parenType,
parentheses = '[]{}()';
/* If it is not a string, return false */
if(typeof str != 'string') {
return false;
}
var foundParen = str.split('').some(function(el) {
return (parentheses.indexOf(el) > -1);
});
/* If there is not a single instance of a paren, return false */
if(!foundParen) return false;
for(var i = 0; i < l; i++) {
currentVal = str[i];
position = parentheses.indexOf(currentVal);
if(position === -1) {
continue;
}
var parenType = (position % 2) ? 'closed' : 'open';
if(parenType == 'closed') { /* 2. */
var el = stack.pop();
if(parentheses.indexOf(el) !== position - 1) {
return false;
}
} else { /* 3. */
stack.push(currentVal);
}
}
/* 5. */
return !stack.length();
};
I would appreciate any feedback on the performance and correctness of this implementation.
It looks like the time complexity is \$O(N)\$. How can it be improved with respect to the multiple, \$k\$, in \$O(N)\$?
What are some edge cases I should be testing? I tested the empty string, non-string values, and non-paren characters.
str.split()
,indexOf
are not single instructions. their complexity must be included when you are calculating an algorithms. Just the single expression str.split('') makes you function O(n) and if you consider that the parentheses themselves are part of the input (eg Uppercase lowercase for open close, MSBit on or off), you definitely have a have a 0(n^2) \$\endgroup\$