Balanced Parentheses

Check for balanced parentheses in the expression

Scope

This article tells how to check balanced parentheses using stack.

In this article we will learn implementation in different programming language.

In this article we will learn time complexity of the stack approach.

Takeaways

Balanced parentheses means that each opening symbol has a corresponding closing symbol and the pairs of parentheses are properly nested.

Problem Statement

Given an input expression string of length n consisting of three types of parentheses – {,},(,),[,].Check for balanced parentheses in the expression (well-formedness) using Stack. Parentheses are balanced if:

1. The same kind of parentheses are used to close any open ones.
2. The proper sequence must be used to close any open parentheses.

Example

1. Input: expression = ~([]){}[[(){}]{}]
   Output: Yes, Balanced
2. Input: expression = [(]))
   Output: No, Not Balanced
3. It’s real life application is during the compilation of any code
   

Example Explanation

1. As in example 1, there is every closing bracket according to their corresponding opening brackets so yes this is balanced parentheses.
2. In the second example, it is observable that the parentheses are not balanced because the ( at the 2nd position in the expression should be closed before the closing of the ].
3. In the 3rd example, there is no { for the } that is in line number 8 of the code. Due to this, an error will be raised if we will try to run the code.

Constraints

• $1<=n<=10^3$
• All of characters in the sequence ∈ (,),{,},[,].

Approach

We must make an observation in order to resolve this problem. The most recent opening parenthesis must coincide with the subsequent closing symbol as you read symbols from left to right. Additionally, it’s possible that the very last symbol processed will be the one to match the first opening symbol. Opening and closing symbols are matched from the inside out, in the opposite order from which they first appear. This is a hint that the issue can be resolved using stacks.

Algorithm

• Declare an empty stack.
• Now start traversing the input string.
• If you come across an opening bracket while traversing the string, add it to the stack.
• Else the current character is a closing bracket. In this case, check to see if the top element of the stack is of the corresponding opening type and if it is then pop the top element from the stack and if not, then return false.
• If the stack is empty after traversing the string, return true; otherwise, return false.

Code Implementation

In C++

// CPP program for balancing the paranthesis
bool is_BalancedParentheses(string str) {
    int x = str.size(); // storing size of input expression
    stack<char> opening_Brackets;
    // iterating over the full expression using for loop
    for (int k = 0; k < x; k++) 
        {
        // if opening bracket encounters then directly push it into stack.
        if (str[k] == '{' || str[k] == '(' || str[k] == '[') {
	     opening_Brackets.push(str[k]);
		}
        else {
            // If stack is empty return false
            if (opening_Brackets.empty()) {
	        return false;
	     }
         // If ) is encountered then check if top of the stack have ( or not      
	    if (str[k] == ')') {
		char last = opening_Brackets.top();
		opening_Brackets.pop();
		if (last != '(') {
	            return false;
		   }
	     }
         // If } is encountered then check if top of the stack have { or not   
	    if (str[k] == '}') {
		char last = opening_Brackets.top();
		opening_Brackets.pop();
		if (last != '{') {
		    return false;
		   }
	     }
         // If ] is encountered then check if top of the stack have [ or not
	    if (str[k] == ']') {
               char last = opening_Brackets.top();
		opening_Brackets.pop();
		if (last != '[') {
                   return false;
			 	}
			}
		}
	}
	return opening_Brackets.empty();
}

In Java

// Java program for balancing the paranthesis
class Solution {
    boolean is_BalancedParentheses(String str) {
	int x = str.length(); // storing size of input expression
	Stack<Character> opening_Brackets = new Stack<>();
        // iterating over the full expression using for loop
	for (int k = 0; k < n; k++) {
            // if opening bracket encounters then directly push it into stack.
            if (str.charAt(k) == '{' || str.charAt(k) == '(' || str.charAt(k) == '[') {
				opening_Brackets.push(str.charAt(k));
			} 
            else {
                // If stack is empty return false
                if (opening_Brackets.empty()) {
		     return false;
		 }
                // If ) is encountered then check if top of the stack have ( or not       
		 if (str.charAt(k) == ')') {
	             char last = opening_Brackets.peek();
		      opening_Brackets.pop();
		      if (last != '(') {
		          return false;
			  }
		  }
                // If } is encountered then check if top of the stack have { or not   
	         if (str.charAt(k) == '}') {
		      char last = opening_Brackets.peek();
		      opening_Brackets.pop();
		      if (last != '{') {
			  return false;
		          }
	         }
                 // If ] is encountered then check if top of the stack have [ or not      
		  if (str.charAt(k) == ']') {
		      char last = opening_Brackets.peek();
		      opening_Brackets.pop();
		      if (last != '[') {
		          return false;
			  }
	         }
	    }
        }
		return opening_Brackets.isEmpty();
    }
}

In Python

# Python program for balancing the paranthesis
def is_BracketsBalanced(exp):
    st = [] # creating empty stack
    for ch in exp:
        if ch in ["{", "(", "["]:
            st.append(ch)
        else:
            # If stack is empty return false
            if not st:
                return False
            curr_char = st.pop()
            # If current char is { and top of the stack is not } then return false 
            if curr_ch == '{':
                if ch != "}":
                    return False
            # If current char is ( and top of the stack is not ) then return false 
            if curr_ch == '(':
                if ch != ")":
                    return False
            # If current char is [ and top of the stack is not ] then return false 
            if curr_ch == '[':
                if ch != "]":
                    return False
    # if any bracket still there in stack then return false
    if st:
        return False
    return True
 
if __name__ == "__main__":
    exp = "{()}[]"
    if is_BracketsBalanced(exp):
        print("Yes, Balanced")
    else:
        print("NO, Not Balanced")

Output

Yes, Balanced

Time Complexity:

As we are traversing over the expression of length n only once using the for loop so O(n) will be it’s time complexity.

Space Complexity:

As we are creating a new stack and the size of stack can grow upto the size of the input string which is n, so O(n) auxiliary space will be used.

Conclusion

• One can solve this balanced parentheses problem using stack.
• There is some sort of nested symbol in almost every type of notation that needs to match in a balanced order.
• O(n) time complexity and O(n) auxiliary space is consumed in this stack approach.