Given an expression string, write a python program to find whether a given string has balanced parentheses or not.
Examples:
Input : {[]{()}}
Output : Balanced
Input : [{}{}(]
Output : Unbalanced
Approach #1: Using stack One approach to check balanced parentheses is to use stack. Each time, when an open parentheses is encountered push it in the stack, and when closed parenthesis is encountered, match it with the top of stack and pop it. If stack is empty at the end, return Balanced otherwise, Unbalanced.
Python3
# Python3 code to Check for # balanced parentheses in an expressionopen_list = ["[","{","("]close_list = ["]","}",")"]# Function to check parenthesesdef check(myStr): stack = [] for i in myStr: if i in open_list: stack.append(i) elif i in close_list: pos = close_list.index(i) if ((len(stack) > 0) and (open_list[pos] == stack[len(stack)-1])): stack.pop() else: return "Unbalanced" if len(stack) == 0: return "Balanced" else: return "Unbalanced"# Driver codestring = "{[]{()}}"print(string,"-", check(string))string = "[{}{})(]"print(string,"-", check(string))string = "((()"print(string,"-",check(string)) |
{[]{()}} - Balanced
[{}{})(] - Unbalanced
((() - Unbalanced
Time Complexity: O(n), The time complexity of this algorithm is O(n), where n is the length of the string. This is because we are iterating through the string and performing constant time operations on the stack.
Auxiliary Space: O(n), The space complexity of this algorithm is O(n) as well, since we are storing the contents of the string in a stack, which can grow up to the size of the string.
Approach #2: Using queue First Map opening parentheses to respective closing parentheses. Iterate through the given expression using ‘i’, if ‘i’ is an open parentheses, append in queue, if ‘i’ is close parentheses, Check whether queue is empty or ‘i’ is the top element of queue, if yes, return “Unbalanced”, otherwise “Balanced”.
Python3
# Python3 code to Check for # balanced parentheses in an expressiondef check(expression): open_tup = tuple('({[') close_tup = tuple(')}]') map = dict(zip(open_tup, close_tup)) queue = [] for i in expression: if i in open_tup: queue.append(map[i]) elif i in close_tup: if not queue or i != queue.pop(): return "Unbalanced" if not queue: return "Balanced" else: return "Unbalanced"# Driver codestring = "{[]{()}}"print(string, "-", check(string))string = "((()"print(string,"-",check(string)) |
{[]{()}} - Balanced
((() - Unbalanced
Time Complexity: O(n)
Auxiliary Space: O(n)
Approach#3: Elimination based In every iteration, the innermost brackets get eliminated (replaced with empty string). If we end up with an empty string, our initial one was balanced; otherwise, not.
Python3
# Python3 code to Check for # balanced parentheses in an expressiondef check(my_string): brackets = ['()', '{}', '[]'] while any(x in my_string for x in brackets): for br in brackets: my_string = my_string.replace(br, '') return not my_string # Driver codestring = "{[]{()}}"print(string, "-", "Balanced" if check(string) else "Unbalanced") |
{[]{()}} - Balanced
Time Complexity: O(n)
Auxiliary Space: O(n)
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 neveropen!
