Solution Review: Balance Parenthesis
This review provides a detailed analysis of the solution to determine whether or not an array contains balanced parenthesis.
We'll cover the following...
Solution: Using Recursion
function balanced(testVariable, startIndex = 0, currentIndex = 0) {// Base case1 and 2if (startIndex == testVariable.length) {return currentIndex == 0}// Base case3if (currentIndex < 0) { // A closing parenthesis did not find its corresponding opening parenthesisreturn false}// Recursive case1if (testVariable[startIndex] == "(") {return balanced(testVariable, startIndex + 1, currentIndex + 1)}// Recursive case2else if (testVariable[startIndex] == ")") {return balanced(testVariable, startIndex + 1, currentIndex - 1)}else {return false // the string contained an unrecognized character}}// Driver CodetestVariable = ["(", "(", ")", ")", "(", ")"]console.log("The array [\"(\", \"(\", \")\", \")\", \"(\", \")\"] is balanced: " + balanced(testVariable))testVariable = ["(", "(", ")"]console.log("The array [\"(\", \"(\", \")\"] is balanced: " + balanced(testVariable))
Explanation
Our task is to read an array of parentheses from left to right and decide whether the symbols are balanced.
To solve this problem, notice that the most recent opening parenthesis must match the following closing parenthesis. The first opening parenthesis processed will be saved until the very last parenthesis is processed to find its corresponding closing parenthesis.
Closing parentheses match opening parentheses in the reverse order of their appearance, meaning that they match from the inside out. This is a clue that recursion can be used to solve this problem.
Let’s investigate the code snippet above.
The two variables startIndex
and currentIndex
are important to note. startIndex
traverses the whole array. In each recursive call, it moves to the next element in the array. It is also used to check whether or not we have reached the end of the array.
The currentIndex
examines if each opening parenthesis has a corresponding closing parenthesis. If we encounter a closing parenthesis currentIndex
...