Sometimes, while working with Python data, we can have a problem in which we need to pair all the elements with the suitable closing brackets, and can have data associated with pairing. This kind of problem is classic application of Stack Data Structure and can have usage across many domains. Let’s discuss a certain way in which this task can be done.
Input : test_list = [(‘(‘, 1), (‘(‘, 2), (‘)’, 3), (‘)’, 4)]
Output : [(2, 3), (1, 4)]Input : test_list = [(‘(‘, 1), (‘)’, 4)]
Output : [(1, 4)]
Method #1: Using stack DS + loop The combination above functionalities can be used to solve this problem. In this, we make a new pair with each opening bracket and when the corresponding closing bracket comes using LIFO technique, we form a pair with that closing bracket.
Python3
# Python3 code to demonstrate working of # Matching Pairs of Brackets# Using stack DS + loop# initializing listtest_list = [('(', 7), ('(', 9), (')', 10), (')', 11), ('(', 15), (')', 100)]# printing original listprint("The original list is : " + str(test_list))# Matching Pairs of Brackets# Using stack DS + loopstck = []res = []for ele1, ele2 in test_list: if '(' in ele1: stck.append((ele1, ele2)) elif ')' in ele1: res.append((stck.pop()[1], ele2))# printing result print("The paired elements : " + str(res)) |
The original list is : [('(', 7), ('(', 9), (')', 10), (')', 11), ('(', 15), (')', 100)]
The paired elements : [(9, 10), (7, 11), (15, 100)]
Time Complexity: O(n*n) where n is the number of elements in the list “test_list”. stack DS + loop performs n*n number of operations.
Auxiliary Space: O(n*n), extra space is required where n is the number of elements in the list
Method: Using a dictionary + loop
Step-by-step approach:
- Initialize an empty dictionary named brackets_dict with the following key-value pairs: ‘(‘ : ‘)’, ‘{‘ : ‘}’, ‘[‘ : ‘]’.
- Initialize an empty stack named stack.
- Initialize an empty list named result.
- Loop through each tuple t in the test_list.
- If the first element of t is an opening bracket (i.e., ‘(‘, ‘{‘, or ‘[‘), then push t onto the stack.
- If the first element of t is a closing bracket (i.e., ‘)’, ‘}’, or ‘]’), then do the following:
- If the stack is empty, then print an error message and exit the loop.
- Pop the top element top from the stack.
- If the second element of top is not the matching closing bracket for the first element of t, then print an error message and exit the loop.
- Otherwise, append a tuple (top[1], t[1]) to the result list.
- If the loop completes without errors, then return the result list.
Python3
# Python3 code to demonstrate working of # Matching Pairs of Brackets# Using a dictionary + loop# initializing listtest_list = [('(', 7), ('(', 9), (')', 10), (')', 11), ('(', 15), (')', 100)]# printing original listprint("The original list is : " + str(test_list))# Matching Pairs of Brackets# Using a dictionary + loopbrackets_dict = {'(': ')', '{': '}', '[': ']'}stack = []result = []for ele1, ele2 in test_list: if ele1 in brackets_dict.keys(): stack.append((ele1, ele2)) elif ele1 in brackets_dict.values(): if not stack: print("Error: closing bracket without opening bracket") break top = stack.pop() if ele1 != brackets_dict[top[0]]: print("Error: mismatched brackets") break result.append((top[1], ele2))# printing result print("The paired elements : " + str(result)) |
The original list is : [('(', 7), ('(', 9), (')', 10), (')', 11), ('(', 15), (')', 100)]
The paired elements : [(9, 10), (7, 11), (15, 100)]
Time complexity: O(n), where n is the number of elements in the test_list.
Auxiliary space: O(n), where n is the number of elements in the test_list.
