Parenthesis Matching Problem in JavaScript @ The Hacking School Hyd

Image for post
Image for post

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

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

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 solution using the beauties of ES6.

Written by

MachineLearning | DataScience | DeepLearning. Previously Frontend Engineer. Ex International Banking Analyst. https://www.linkedin.com/in/rohan-paul-b27285129/

Get the Medium app

A button that says 'Download on the App Store', and if clicked it will lead you to the iOS App store
A button that says 'Get it on, Google Play', and if clicked it will lead you to the Google Play store