Balanced brackets problem
Balanced brackets problem is one of the famous problems based on the stack and it has been asked in many interviews. Here is the solution to this problem in python and JavaScript.
Problem-
A bracket is considered to be any one of the following characters: (, ), {, }, [, or ] and matching or pair of brackets are () or {} or [].
So, in the given string, the bracket should appear in such a way that each bracket has a corresponding matching bracket at the other side of string from the middle.
Example -
Input: {{[[(())]]}}
Output: Balanced
Input: {{[(]]}}
Output: Not Balanced
Solution-
To solve this problem we can use the stack data structure.
When we will encounter an opening bracket in the string, push it into the stack and continue to do it. If we will get the closing bracket in the string then check the top of the stack if the top of the stack is matching with coming closing bracket then continue otherwise return False.
Continue the same procedure for each bracket in the string. If everything goes fine till the end the return True.
Program
Python
def isBalanced(brackets):
opening_braces = ['{', '[', '(']
closing_braces = ['}', ']', ')']
stack = []
for bracket in brackets:
if bracket in opening_braces:
stack.append(bracket)
else:
if not stack:
return False
elif not closing_braces.index(bracket) == opening_braces.index(stack[-1]):
return False
else:
stack.pop()
if not stack:
return True
else:
return False
if isBalanced('{{[[(())]]}}'):
print('Balanced')
else:
print('Not Balanced')
JavaScript
function isBalanced(brackets) {
opening_braces = ['{', '[', '('];
closing_braces = ['}', ']', ')'];
stack = [];
for (let bracket of brackets) {
if (opening_braces.includes(bracket))
stack.push(bracket);
else {
if (stack.length <= 0)
return false;
else if (!(closing_braces.indexOf(bracket) == opening_braces.indexOf(stack[stack.length-1])))
return false;
else
stack.pop();
}
}
if (stack.length <= 0)
return true;
else
return false;
}
if (isBalanced('{{[[(())]]}}'))
console.log('Balanced')
else
console.log('Not Balanced')
Output
Balanced
