Check for Balanced Parentheses in an Expression

Check for Balanced Parentheses in an Expression - Interview Problem

Level: Medium

Asked In: Amazon, Microsoft

Understanding the Problem:

Given an expression containing different open and close parentheses, your task is to find whether the expression has balanced parentheses or not. The expression can contain the following parentheses →’(’, ‘)’, ‘{‘, ‘}’, ‘[‘, ‘]’. The expression is said to be balanced if:

The order of the opening and closing brackets is same.
The opening bracket must be closed with the same type of closing bracket.

For Example →

Input:expression="[(())]"
Output: True

Input:expression="[(])"
Output: False

Possible follow up questions to ask →

Is it possible for the expression to have other characters except for brackets? ( Ans: For simplicity, consider other characters aren't present)

Solutions

We are going to discuss the different possible solutions for this question based on different approaches. The following are the proposed solutions:-

Brute Force Solution → This is a solution in which we will maintain a counter. The value of this counter should not be less than 0 at any point of time for balanced expressions.
Time Optimized Brute Force Solution → Here in this solution also we will use counter but we will keep replacing the matching pairs with *.
Solution Using Stack → In this solution we will use the concepts of the stack to find if the expression is balanced or not.

Brute Force Solution

Solution idea

The idea is to maintain a counter which is incremented whenever an opening bracket is encountered and decremented once the closing bracket is encountered. At any point in time if the value of the counter is less than 0, it signifies that the expression is not balanced. For every opening bracket at index i, if the closing bracket is at index j, we should take care that if any other pair of opening and closing brackets are present in between the initial matching pair then they should be strictly in between the initial opening and closing brackets. (Like in the second example shown in problem description)

Solution step

For every opening bracket we will look for the existence of closing bracket in the acceptable range, i.e. after the opening bracket and before the expression ends.
Same for every closing bracket we will look for the existence of the opening bracket from start of the expression up to the index of closing bracket.
When we get one matching pair, we will start looking for other brackets in between and checking if they are in acceptable range.

Pseudo-Code

int getClosing(string expression, int i, int j, char matchOpen , char matchClose)
{
   int counter=1 //we already have one opening bracket
   int index=i+1
   while(index<=j)
   {
     if(expression[i]==matchOpen)
        counter+=1
     else if(expression[i]==matchClose)
        counter-=1
     if(counter==0)
       return index
     index+=1
    }
    return index
}

int getOpening(string expression, int i, int j, char matchOpen , char matchClose)
{
   int counter=-1 //we already have one closing bracket
   int index=j-1
   while(index>=i)
   {
     if(expression[i]==matchOpen)
        counter+=1
     else if(expression[i]==matchClose)
        counter-=1
     if(counter==0)
       return index
     index-=1
    }
    return index
}

bool isBalancedExp(string expression, int size)
{
  int i, j
  for(i=0 to size-1;i=i+1)
  {
    if(expression[i]=='(')
       j=getClosing(expression, i, size-1, '(', ')')
    else if(expression[i]=='{')
       j=getClosing(expression, i, size-1, '{', '}')
    else if(expression[i]=='[')
       j=getClosing(expression, i, size-1, '[', ']')
    else
       {
         if(expression[i]==')')
            j=getOpening(expression, 0, i, '(', ')')
         else if(expression[i]=='}')
            j=getOpening(expression, 0, i, '{', '}')
         else if(expression[i]==']')
            j=getOpening(expression, 0, i, '[', ']')
         if(j<0 || j>=i)
            return False
         continue
       }
     if(j>=size || j<0)
        return False
    //If we have got one matching pair, we will check for other //pairs in between the opening and closing bracket
     int startBtw=i
     int endBtw=j
     int indexBtw, matchBtw
     for(indexBtw=startBtw+1 to endBtw-1;indexBtw+=1)
     {
        if(expression[indexBtw]=='(')
        {
          matchBtw=getClosing(expression, indexBtw, endBtw, '(', ')')
          if(matchBtw is not > indexBtw and matchBtw is not < endBtw)
              return False
        else if(expression[indexBtw]==')')
        {
          matchBtw=getOpening(expression, startBtw, indexBtw, '(', ')')
          if(matchBtw is not >startBtw and matchBtw is not < indexBtw)
            return False
        }
        if(expression[indexBtw]=='{')
        {
          matchBtw=getClosing(expression, indexBtw, endBtw, '{', '}')
          if(matchBtw is not > indexBtw and matchBtw is not < endBtw)
              return False
        }
        else if(expression[indexBtw]=='}')
        {
          matchBtw=getOpening(expression, startBtw, indexBtw, '{', '}')
          if(matchBtw is not >startBtw and matchBtw is not < indexBtw)
            return False
        }
        if(expression[indexBtw]=='[')
        {
          matchBtw=getClosing(expression, indexBtw, endBtw, '[', ']')
          if(matchBtw is not > indexBtw and matchBtw is not < endBtw)
              return False
        }
        else if(expression[indexBtw]==']')
        {
          matchBtw=getOpening(expression, startBtw, indexBtw, '[', ']')
          if(matchBtw is not >startBtw and matchBtw is not < indexBtw)
            return False
        }
      }
     }
     return True
}

Complexity Analysis

Time Complexity : O(N³), where N is the size of the expression.

Space Complexity: O(1)

Critical ideas to think!

Can you analyze the time complexity of the above code by dry running it?

Time Optimized Brute Force Solution

Solution idea

Since the time complexity of the above algorithm is too high, we will devise a new solution for solving the problem. Here also we are maintaining the counter variable and will increment and decrement it on encountering opening and closing brackets respectively. However, here once we will get the matching pair, we will replace it with ‘*’. This will help us to avoid taking care of those matched pairs. At last, we will check the value of the counter, if it is zero it means the expression is balanced.

Solution steps

For every closing bracket we will search for the opening bracket from last opening bracket to the index of this closing bracket.
Once there is a match of opening and closing bracket, we will replace the pair with ‘*’.
At last we will check the value of counter, if it is zero our expression is balanced.

Pseudo-Code

int hasOpeningBracket(string expression, int &i, int &j,char match, int &counter)
{
   counter=counter-1 //because this is a closing bracket whose opening is being searched
   if(s[j]==match)
   {
      i=i+1
      return 1
   }
   while(j>-1 && s[j]=='#')
   {
      j=j-1
      if(s[j]==match)
      {
        i=i+1
        return 1
      }
    }
   return 0
}

bool isBalancedExp(string expression, int size)
{
  if (size==0)
    return True
  int i, counter=0,hasOpening,j=-1
  for(i = 0 to size-1)
  { 
    switch(expression[i])
    {
      case ')':
           hasOpening=hasOpeningBracket(expression, i, j, '(', counter)
           if(hasOpening==0)
               return False
           break

      case ']':
           hasOpening=hasOpeningBracket(expression, i, j, '[', counter)
           if(hasOpening==0)
               return False
           break
      case '}':
           hasOpening=hasOpeningBracket(expression, i, j, '{', counter)
           if(hasOpening==0)
               return False
           break
      //Case when the bracket is opening
      default:
            j=i-1
            i=i+1
            counter=counter+1
     }
    
     if(counter==0)
       return True
     return False

Complexity Analysis

Time Complexity: O(N²)( Think! )

Space Complexity : O(1) Are you thinking about a data structure which can easily solve this problem?

Solution Using Stack

Solution idea

In this solution, we will use a stack data structure to evaluate an expression. Stack is a LIFO based data structure with only one entry and exit point. You can read about it here: Stack and its basic operations . When we will encounter an opening bracket we will push it into the stack and when we will encounter the closing bracket, we will compare the top element. If the top element is not a corresponding opening bracket, we will return False else we will pop the corresponding top opening bracket. For example, the given expression is “[{()}]”

1. Push [ to stack

Stack →[

2. Push { to stack

Stack →[ { ([ {

3. Push ( to stack

Stack →[ { (

4. Now we have ) and the item at top is ( , therefore we will pop.

Stack →[ {

5. Now again we have } and the item at top is { , therefore we will pop.

Stack →[

6. Again the last character is ] and the top item is [ , thus, we will pop.

Stack →Empty

Thus our expression is balanced.

Solution steps

If we get an opening bracket we will simply push it to stack.
If we get a closing bracket we will compare the top element.
If there is not a match of closing and opening brackets we can return False.
Else we will pop the top element and continue.
At last if the stack is empty, we can conclude that the expression is balanced.

Pseudo-Code

bool isBalancedExp(string expression, int size)
{
    stack S;
    for(int i=0 to size-1; i+=1)
    {
        if(expression[i] == '(' or '{' or '[')
            S.push(expression[i]);
        else if(expression[i] == ')' or '}' or ']')
        {
            if(S.empty())
                return False;
            char ch=S.top();
            S.pop();
            if(ch=='(' and expression[i]==')')
               continue;
            if(ch=='{' and expression[i]=='}')
               continue;
            if(ch=='[' and expression[i]==']')
                continue;
            else
                return false;
        }
            
    }
    if(S.empty())
        return True;
    else
        return False;
}