Handling the classic parenthesis matching problem in JavaScript with ES6

A classic problem — Check for balanced parentheses in an expression. Two brackets are considered to be a matched pair if the an opening bracket (i.e., (, [, or { ) occurs to the left of a closing bracket (i.e., ), ], or }) of the exact same type. There are three types of matched pairs of brackets: [], {}, and ().

Algorithm

1. Declare a character stack which will hold an array of all the opening parenthesis.
2. Now traverse the expression string exp.
3. If the current character is a starting bracket (‘(‘ or ‘{‘ or ‘[‘) then push it to stack.
4. If the current character is a closing bracket (‘)’ or ‘}’ or ‘]’) then pop from stack and if the popped character is the matching starting bracket then fine else parenthesis are not balanced.
5. After complete traversal, if there is some starting bracket left in stack then “not balanced”

Here’s the implementation..

sMatchingBrackets = function(str) {
    let stack = [];
    let map = {
        '(': ')',
        '[': ']',
        '{': '}'
    }
    for (let i = 0; i < str.length; i++) {
        // If character is an opening brace add it to a stack
        if (str[i] === '(' || str[i] === '{' || str[i] === '[') {
            stack.push(str[i]);
        }
        //  If that character is a closing brace, pop from the stack, 
       // which will also reduce the length of the stack each time a closing bracket is encountered.
        else {
            let last = stack.pop();
            //If the popped element from the stack, which is the last opening brace 
           // doesn’t match the corresponding closing brace in the map, then return false
            if (str[i] !== map[last]) {
                return false
            };
        }
    }
    // By the completion of the for loop after checking all the brackets of 
   // the str, at the end, if the stack is not empty then fail
    if (stack.length !== 0) {
        return false
    };
    return true;
}
console.log(isMatchingBrackets("(){}")); // returns true
console.log(isMatchingBrackets("[{()()}({[]})]({}[({})])((((((()[])){}))[]{{{({({({{{{{{}}}}}})})})}}}))[][][]")); 
// returns true

console.log(isMatchingBrackets("({(()))}}")); // returns false

Here’s another simple implementation with stack data structure.

let isParenthesisMatching = (str) => {
    let stack = [];

    let open = {
        '{': '}',
        '[': ']',
        '(': ')'
    };

    let closed = {
        '}': true,
        ']': true,
        ')': true
    }

    for (let i = 0; i < str.length; i++) {

        let char = str[i];

        if (open[char]) {
            stack.push(char);
        } else if (closed[char]) {
            if (open[stack.pop()] !== char) return false;
        }
    }
    return stack.length === 0;
}

First, I assign an object with opening and closing key-value pair. Then under the for loop, while traversing the given string argument passed to the function, I push to the ‘stack’ array, only the closing braces for each opening braces found in the passed-in argument. So, the stack array will be an array of closed braces.

If a ‘closed’ char is found, check if the matching closed parenthesis of the last element that is popped off the stack (i.e. for the last open parenthesis symbol found in the passed-in string) is not equal to the current chr. And if the chr isn’t the matching closed parenthesis for the last open parenthesis from the stack, then we return false because we have an imbalanced input.

Time Complexity -

The above solution iterates the length of the input string, so our time cost will grow in linear proportion to the growth of the string length. Or, for each character that is added to the input string, the algorithm will take 1 time unit longer to complete (worst case). All other operations in our algorithm are constant time because we are using object-property lookup to find our comparison values and the pop method of a Stack data structure to keep track of all the parenthesis pairs that get opened.

And then below is a much more beautiful and shorter solution using Array.reduce() method.

let isBalancedParenthesis = (str) => {
    
    return !str.split('').reduce((uptoPrevChar, thisChar) => {
        if(thisChar === '(' || thisChar === '{' || thisChar === '[' ) {
            return ++uptoPrevChar;
        } else if (thisChar === ')' || thisChar === '}' || thisChar === ']') {
            return --uptoPrevChar;
        }

        return uptoPrevChar
    }, 0);
}

// Test Cases
console.log(isBalancedParenthesis("[()]{}{[()()]()}"));  // returns true
console.log(isBalancedParenthesis("[{()()}({[]})]({}[({})])((((((()[])){}))[]{{{({({({{{{{{}}}}}})})})}}}))[][][]"));  // returns true
console.log(isBalancedParenthesis("({(()))}}"));  // returns false

Basically, the above function just increments the variable uptoPrevChar for each opening parenthesis and reduces it for each closing parenthesis. And ultimately I should just get zero for a balance string.

However, I have to return a boolean output — so I put a logical not ( ! ) at the very front of str. So for numerical return value of 0 for variable ‘uptoPrevChar’ — I return true.

Just paste this code, in Chrome DevTool > Source > Snippets > Put a breakpoint at the return value of ‘uptoPrevChar’ on the second else if iteration > right click on the snippets and run > The continue clicking on ‘resume script execution’

And another variation of the above solution using the beauties of ES6.

function isBalanced([...str]) {return str.reduce((uptoPrevChar, thisChar) => {
    ((thisChar === '(' && uptoPrevChar++ || thisChar === ')' && uptoPrevChar--)) &&
    ((thisChar === '{' && uptoPrevChar++ || thisChar === '}' && uptoPrevChar--)) &&
    ((thisChar === '[' && uptoPrevChar++ || thisChar === ']' && uptoPrevChar--));

    return uptoPrevChar;
}, 0) === 0 }