Check for Balanced Parentheses in an Expression

https://www.prepbytes.com/data-structures-in-java

Problem statement

Given an expression containing only ‘(‘, ’)’, ’{‘, ‘}’, ‘[‘, ‘]’ , check whether the expression is balanced or not.

An expression is balanced if each opening bracket is closed by the same type of closing bracket in the exact same order.

Input: A string representing the given expression
Output: Boolean value

Test cases:
Input 1:
“({[]})”

Output 1:
true

Input 2:
“(){}](“

Output 2:
false

Approach – Using Stack

The idea is to use the LIFO functionality of the stack. As a stack is LIFO data structure, we will remove every opening bracket (‘(‘, ‘{‘, ‘[‘), whenever we encounter the same type of closing bracket (‘)’, ‘}’, ‘]’).
If for any opening bracket we don’t have a closing bracket, the opening bracket will remain in the stack forever.
Similarly if we only have a closing bracket without a preceding opening bracket we will just push the closing bracket into the stack and it will remain there forever.
So, at last after traversing the whole expression, if the stack is empty then it will mean that the given expression is balanced, otherwise if the stack contains elements that would mean the given expression was unbalanced.

Algorithm

1. Initialize an empty stack.
2. Iterate i from 0 to length(expression).
   a. Store the current character in a variable ‘ch’.
   b. If stack is empty: Push ‘ch’ to the stack
   c. Else if current character is a closing bracket and of the top of the stack contains an opening bracket of the same type
   Remove the top of the stack: Else, push ‘ch’ to the stack
3. If the stack is empty, return true, else false.

Dry Run

Input: “({[]})”
Output: true

As the stack is empty, hence the given expression was balanced.

Code Implementation:

import java.util.*;
public class Main
{
	public static void main(String[] args) {
		String exp = "({[]})";
		System.out.println(isBalanced(exp));
	}
	// Function to check whether given expression is balanced or not
	public static boolean isBalanced(String exp) {
        Stack<Character> st = new Stack<>();
        
        // Traverse over the expression
        for(int i = 0; i < exp.length(); i++){
            
            // Get the current character 
            char ch = exp.charAt(i);
            
            // If the stack is empty, push the current character into the stack
            if(st.isEmpty()){
                st.push(ch);
            }
            
            // Otherwise if the current character is a closing bracket 
            // and of the top of the stack contains an opening bracket of the same type
            // then remove the top of the stack
            else if((ch==')' && st.peek() == '(')||(ch=='}' && st.peek() == '{')||(ch==']' && st.peek() == '[')){
                st.pop();
            }
            else{
                st.push(ch);
            }      
        }
        
        // If after traversing the whole expression the stack is empty
        // then it means the given expression is balanced else unbalanced
        return (st.isEmpty());
    }
}

Output:
true

Time complexity: O(n). We can observe that every character is pushed and removed from the stack at most once. Hence, the total operations being performed is 2n and O(2n) = O(n) because we don’t consider constant terms during asymptotic analysis of time complexity.

Space Complexity: O(n). O(n) space is required for the input and output array. The auxiliary space complexity is also O(n) as we are using a stack. At any point of time the stack can contain at most n elements.

So, in this blog, we have tried to explain the efficient way to check for balanced parentheses in an expression. Hope this blog helps you understand and solve the problem. To practice more problems you can check outMYCODE | Competitive Programming at Prepbytes.