Home/

...

/

Balanced Parentheses (hard)

Balanced Parentheses (hard)

Dry-run templates

This is the implementation of the solution provided for the problem posed in the Balanced Parentheses (hard) lesson:

Press + to interact
Python 3.5
from collections import deque
class ParenthesesString:
  def __init__(self, str, openCount, closeCount):
    self.str = str
    self.openCount = openCount
    self.closeCount = closeCount
def generate_valid_parentheses(num):
  result = []
  queue = deque()
  queue.append(ParenthesesString("", 0, 0))
  while queue:
    ps = queue.popleft()
    # if we've reached the maximum number of open and close parentheses, add to the result
    if ps.openCount == num and ps.closeCount == num:
      result.append(ps.str)
    else:
      if ps.openCount < num:  # if we can add an open parentheses, add it
        queue.append(ParenthesesString(
          ps.str + "(", ps.openCount + 1, ps.closeCount))
      if ps.openCount > ps.closeCount:  # if we can add a close parentheses, add it
        queue.append(ParenthesesString(ps.str + ")",
                                       ps.openCount, ps.closeCount + 1))
  return result
def main():
  print("All combinations of balanced parentheses are: " +
        str(generate_valid_parentheses(2)))
  print("All combinations of balanced parentheses are: " +
        str(generate_valid_parentheses(3)))
main()

Students may be encouraged to run through the provided solution with the following sample inputs:

Sample input #1

num:2

Iteration No.

Line No.

ps.str

ps.openCount

ps.closeCount

queue

result

-

12-14

-

-

-

[('',0,0)]

[]

1

16

''

0

0

[]

[]

1

22

''

0

0

[("(",1,0 )]

[]

2

16

(

1

0

[]

[]

2

22

(

1

0

[("((",2,0 )]

[]

2

26

(

1

0

[("((",2,0 ),("()",1,1 )]

[]

3

16

((

2

0

[("()",1,1 )]

[]

3

26

((

2

0

[("()",1,1 ),("(()",2,1 )]

[]

4

16

()

1

1

[("(()",2,1 )]

[]

4

22

()

1

1

[("(()",2,1 ),("()(",2,1 )]

[]

5

16

(()

2

1

[("()(",2,1 )]

[]

5

26

(()

2

1

[("()(",2,1 ),("(())",2,2 )]

[]

6

16

()(

2

1

[("(())",2,2 )]

[]

6

26

()(

2

1

[("(())",2,2 ),("()()",2,2 )]

[]

7

16

(())

2

2

[("()()",2,2 )]

[]

7

19

(())

2

2

[("()()",2,2 )]

['(())']

8

16

()()

2

2

[]

['(())']

8

19

()()

2

2

[]

['(())', '()()']

Sample input #2

Students may be encouraged to complete the dry-run with this input:

num:3

Iteration No.

Line No.

ps.str

ps.openCount

ps.closeCount

queue

result

-

12-14

-

-

-

[('',0,0)]

[]

1

16

''

0

0

[]

[]

1

22

''

0

0

[("(",1,0)]


2

16

(

1

0

[]


2

22

(

1

0

[("((",2,0)]


2

26

(

1

0

[("((",2,0),("()",1,1)]


3

16

((

2

0

[("()",1,1)]


3

22

((

2

0

[("()",1,1),("(((",3,0)]


3

26

((

2

0

[("()",1,1),("(((",3,0),("(()",2,1)]


4

16

()

1

1

[("(((",3,0),("(()",2,1)]


4

22

()

1

1

[("(((",3,0),("(()",2,1),("()(",2,1)]


5

16

(((

3

0

[("(()",2,1),("()(",2,1)]


5

22

(((

3

0

[("(()",2,1),("()(",2,1),("((()",3,1)]


6

16

(()

2

1

[("()(",2,1),("((()",3,1)]


6

22

(()

2

1

[("()(",2,1),("((()",3,1),("(()(",3,1)]


6

26

(()

2

1

[("()(",2,1),("((()",3,1),("(()(",3,1),("(())",2,2)]


...

...

...

...

...

...


Step-by-step solution construction

The solution keeps track of the partially created combinations in queue and keeps iterating it until all combinations with the required number of opening and closing parentheses are generated.

We start with an empty combination and for each iteration of the loop, we perform the following three main steps:

  1. Pop a combination from queue (line 34) and append an opening parenthesis to the existing combination if the number of opening parentheses is less than the required num. Append the newly formed combination to the queue(lines 37-40).

Note: The function print_queue is added to print the queue of ParenthesesString objects (lines 15-22). Also, notice the __str__ method in the class ParenthesesString (lines 9-13). It gets called automatically when we call print on an object of ParenthesesString.

Press + to interact
Python 3.5
from collections import deque
class ParenthesesString:
  def __init__(self, str, openCount, closeCount):
    self.str = str
    self.openCount = openCount
    self.closeCount = closeCount
  def __str__(self):
    if(self.str == ""):
      return "''"
    else:    
      return self.str
def print_queue(queue):
  print("\t\tUpdated queue: ",end=" ")
  for i in range(len(queue)):
    if(i == len(queue)-1): 
      print(queue[i],end="")
    else:
      print(queue[i],end=",")
  print()
def generate_valid_parentheses(num):
  result = []
  queue = deque()
  queue.append(ParenthesesString("", 0, 0))
  print("queue initilized to an an empty ParenthesesString object")
  iteration = 1
  while queue:
    print("\tIteration ",iteration)
    iteration +=1
    ps = queue.popleft()
    print("\t\tps.str: ",ps," ps.openCount: ",ps.openCount," ps.closeCount: ",ps.closeCount)
    print("\t\tPopped from queue: ",ps)
    if ps.openCount < num:  # if we can add an open parentheses, add it
        print("\t\topenCount is less than num. Adding \"(\" parentheses to the popped element")
        queue.append(ParenthesesString(
          ps.str + "(", ps.openCount + 1, ps.closeCount))
        print_queue(queue)
  return result
def main():
  nums = [2,3]
  for n in nums:
    print("Finding all combinations of balanced parentheses of size: ",n)
    result = generate_valid_parentheses(n)
    print("All combinations of balanced parentheses are: ",result)
    print("-"*100+"\n")
main()
  1. If the number of closing parentheses in the popped combination is less than the number of opening parentheses, append a closing parenthesis to the existing combination. Append the newly formed combination to the queue(lines 43-46).
Press + to interact
Python 3.5
from collections import deque
class ParenthesesString:
  def __init__(self, str, openCount, closeCount):
    self.str = str
    self.openCount = openCount
    self.closeCount = closeCount
  def __str__(self):
    if(self.str == ""):
      return "''"
    else:    
      return self.str
def print_queue(queue):
  print("\t\tUpdated queue: ",end=" ")
  for i in range(len(queue)):
    if(i == len(queue)-1): 
      print(queue[i],end="")
    else:
      print(queue[i],end=",")
  print()
def generate_valid_parentheses(num):
  result = []
  queue = deque()
  queue.append(ParenthesesString("", 0, 0))
  print("queue initilized to an an empty ParenthesesString object")
  iteration = 1
  while queue:
    print("\tIteration ",iteration)
    iteration +=1
    ps = queue.popleft()
    print("\t\tps.str: ",ps," ps.openCount: ",ps.openCount," ps.closeCount: ",ps.closeCount)
    print("\t\tPopped from queue: ",ps)
    if ps.openCount < num:  # if we can add an open parentheses, add it
      print("\t\topenCount is less than num. Adding \"(\" parentheses to the popped element")
      queue.append(ParenthesesString(
        ps.str + "(", ps.openCount + 1, ps.closeCount))
      print_queue(queue)
    if ps.openCount > ps.closeCount:  # if we can add a close parentheses, add it
      print("\t\topenCount is greater than closeCount. Adding \")\" parentheses to the popped element")
      queue.append(ParenthesesString(ps.str + ")",
         ps.openCount, ps.closeCount + 1))
      print_queue(queue)
  return result
def main():
  nums = [2,3]
  for n in nums:
    print("Finding all combinations of balanced parentheses of size: ",n)
    result = generate_valid_parentheses(n)
    print("All combinations of balanced parentheses are: ",result)
    print("-"*100+"\n")
main()

Step 1 and 2 should only be performed on the combinations where the number of closing and opening parentheses are less than num. Alternatively, if a combination has the required num of parenthesis, append the popped combination to the result array.

The code below adds the corresponding if condition to the code (lines 38-40). Also, Steps 1 and 2 are moved to the else (line 42-52) .

Press + to interact
Python 3.5
from collections import deque
class ParenthesesString:
  def __init__(self, str, openCount, closeCount):
    self.str = str
    self.openCount = openCount
    self.closeCount = closeCount
  def __str__(self):
    if(self.str == ""):
      return "''"
    else:    
      return self.str
def print_queue(queue):
  print("\t\tUpdated queue: ",end=" ")
  for i in range(len(queue)):
    if(i == len(queue)-1): 
      print(queue[i],end="")
    else:
      print(queue[i],end=",")
  print()
def generate_valid_parentheses(num):
  result = []
  queue = deque()
  queue.append(ParenthesesString("", 0, 0))
  print("queue initilized to an an empty ParenthesesString object")
  iteration = 1
  while queue:
    print("\tIteration ",iteration)
    iteration +=1
    ps = queue.popleft()
    print("\t\tps.str: ",ps," ps.openCount: ",ps.openCount," ps.closeCount: ",ps.closeCount)
    print("\t\tPopped from queue: ",ps)
    # if we've reached the maximum number of open and close parentheses, add to the result
    if ps.openCount == num and ps.closeCount == num:
      print("\t\topenCount and closeCount both equal num. Adding ",ps.str," to the result array")
      result.append(ps.str)
      print("\t\tUpdated result array: ",result)
    else:
      if ps.openCount < num:  # if we can add an open parentheses, add it
        print("\t\topenCount is less than num. Adding \"(\" parentheses to the popped element")
        queue.append(ParenthesesString(
          ps.str + "(", ps.openCount + 1, ps.closeCount))
        print_queue(queue)
      if ps.openCount > ps.closeCount:  # if we can add a close parentheses, add it
        print("\t\topenCount is greater than closeCount. Adding \")\" parentheses to the popped element")
        queue.append(ParenthesesString(ps.str + ")",
                                       ps.openCount, ps.closeCount + 1))
        print_queue(queue)
  return result
def main():
  nums = [2,3]
  for n in nums:
    print("Finding all combinations of balanced parentheses of size: ",n)
    result = generate_valid_parentheses(n)
    print("All combinations of balanced parentheses are: ",result)
    print("-"*100+"\n")
main()