Balanced brackets problem

Abhishek Kumar • Category: Data Structures • Tags: datastructures advanced stack

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.

balanced bracket example

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.

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')

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

Maximum area histogram

AUTHOR

Abhishek Kumar