Solution Review: Balance Parenthesis

This review provides a detailed analysis of the solution to determine whether an array contains balanced parenthesis or not.

We'll cover the following

Solution: Using Recursion

Press + to interact
def balanced(testVariable, startIndex = 0, currentIndex = 0) :
  # Base case1 and 2
  if startIndex == len(testVariable) : 
    return currentIndex == 0
  # Base case3
  if currentIndex < 0 : # A closing bracket did not find its corresponding opening bracket
    return False
  # Recursive case1
  if testVariable[startIndex] == "(" : 
    return  balanced(testVariable, startIndex + 1, currentIndex + 1)
  # Recursive case2
  elif testVariable[startIndex] == ")" : 
    return  balanced(testVariable, startIndex + 1, currentIndex - 1)
# Driver Code
testVariable = ["(", "(", ")", ")", "(", ")"]
print(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 next closing parenthesis. Also, the first opening bracket processed may have to wait until the very last bracket for its match.

Closing brackets match opening brackets in the reverse order of their appearance, i.e., they match from the inside out. This is a clue that recursion can be used to solve this problem.

Let’s discuss the code snippet above.

The two variables: startIndex and currentIndex are particularly important to note. startIndex traverses the whole array. In each recursive call it moves on to the next element in the array. It also checks whether we have reached the end of the array or not.

The currentIndex takes care whether each opening bracket has a corresponding closing bracket or not. It is decreased by 11 if we encounter a closing bracket and increased by 11 if we encounter an opening bracket. If the currentIndex does not reach 00 at the end of the traversal, we return False.

Conditions of the array:

Our array can satisfy 5 conditions:

  1. startIndex == len(testVariable) and currentIndex == 0

    • In this situation the startingIndex has successfully traversed the whole array and the currentIndex has matched every starting bracket to a closing bracket and is, therefore, pointing at index 00. We can return True for this situation.

  2. startIndex == len(testVariable) and currentIndex != 0

    • In this situation the startingIndex has traversed the whole array but the currentIndex has not found a matching closing bracket for a starting bracket. We can return False for this situation.

  3. currentIndex < 0

    • In this situation, while traversing the array we encountered no opening bracket for a closing bracket. Remember we stated above that closing brackets match opening brackets in the reverse order of their appearance. Therefore, in this situation return False.

These 33 conditions will be our base cases.

  1. testVariable[startIndex] == "("

    • An opening bracket is found so increase both the startIndex and currentIndex and call function balanced(testVariable, startIndex + 1, currentIndex + 1)

  2. testVariable[startIndex] == ")"

    • A closing bracket is found so increase startIndex but decrease currentIndex and call function balanced(testVariable, startIndex + 1, currentIndex - 1)

Conditions 44 and 55 will be our recursive cases.

Let’s have a look at an example:

In the next lesson, we have another challenge for you to solve.