A Parenthetical Algorithm

Admittedly, I ran out of time this week to attack another algorithm in computer science, so I wanted to introduce a JavaScript problem I recently solved for a technical interview. The purpose of the algorithm is take an input of a string and return true or false based on whether or not the string has used parenthesis properly. Basically,

isValid(“(hello)”) // true
isValid("(hello") //false
isValid(")hello") //false

Take a minute and see if you can solve it.

The Solution

Here’s one solution to the problem:

Let me break it down for you. To begin with, we declare number of variables at the top of the function; namely, a parens variable that houses the valid parenthesis pairs (note that this algorithm was even extended to check for valid brackets and braces, too). There is also an empty stack variable as well as one for the current character and its position.

Then we enter into a loop that runs through every character of the string passed in. The character variable is assigned the character at string[i].

Then the position is calculated by calling .indexOf(character) on the parens array. This method will check the array and if the character exists in the array it will return the index of that character. Otherwise, it will return -1.

From there, we check if the position is -1. This allows the algorithm to pass over characters other than parenthesis, braces, and brackets.

The if/else clause checks to see if position modulo 2 is equal to 0. The reason for this is because all opening parens exist at an even numbered position within the array or are at 0. All closing parens are odd. We push the position + 1 to the stack because it allows to easily check later for a matching closing parenthesis.

Thus, when the if statement isn’t true we execute the else statement, which is another if statement. This one compares the position pushed to the stack with the next position of a paren character. If they match, we have found a closing parenthesis. Otherwise, we return false.

Finally, we must return a statement outside the parenthesis in order to take care of any outlying problems. This one returns the Boolean result of whether the stack.length === 0. The reason for this is there are instances where false is never fired in our if/else statement, but are still invalid. These instances will have left at least one position remaining in the queue, which we can easily verify.

In the case of a valid string, it will always be true because the stack should always be of a length of 0.

Conclusion

There you have it! Make sure to look over the algorithm until you understand it since I’ve seen this one constantly in tech interviews. Until next time. Cheers!