ExpressJS - Parenthesis Matching Problem in JavaScript @ The Hacking School Hyd

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

Write a balancedParenthesis function that takes a string as input and returns a boolean - if the parentheses in the input string are ‘balanced’, then return true, else return false. For example, the program should print true for exp = “[()]{}{()()}” and false for exp = “[(])”

Algorithm

Declare a character stack.

Now traverse the expression string exp.

If the current character is a starting bracket (‘(‘ or ‘{‘ or ‘[‘) then push it to stack.

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.

After complete traversal, if there is some starting bracket left in stack then “not balanced”

Here’s the implementation..

Here’s another simple implementation with stack data structure.

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.

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 using ES6