Check for balanced parentheses in JavaScript

Question

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'.)

1. We validate the input, check if it is a string and has at least one paren.
2. We initialize a stack and iterate through the string input.
3. 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.
4. If the character is an open paren, we push it onto the stack.
5. If step 3 fails, even once, return false.
6. 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.

1. It looks like the time complexity is \$O(N)\$. How can it be improved with respect to the multiple, \$k\$, in \$O(N)\$?

2. What are some edge cases I should be testing? I tested the empty string, non-string values, and non-paren characters.

Answer 1

The algorithm looks fine to me, but I did not run it, as I do not have any stack implementation at hand. I expect most implementations to throw an exception when trying to pop from an empty stack, so your code may exhibit a weakness here.

Using a string as your preferred data structure to store and iterate parens looks a bit dubious. It implies repeated calls to indexOf() over the same values, and does not explicit well enough the nature of your parens (you need to track positions). Other approaches could be favored, e.g. maps. For instance, you could map opening tokens with their closing tokens, and conversely.

From a design point of view, your function mixes two things: the balance check itself and the parentheses which it should use to operate. I believe it would be cleaner to decouple these, for instance passing a list of Parens as argument to the function, each Parens indicating an opening token and a closing token. The design of your function would evolve in a good way, and you'd gain additional benefits as well (Open Closed Principle).