Balanced Parentheses

Table Of Contents

Problem Statement
Solution
Algorithm
Intuition
Code
Time Complexity
Space Complexity

Problem Statement

Given a string s containing just the characters '(', ')', '{', '}', '[' and ']', determine if the input string is balanced.

An input string is balanced if:

Open brackets must be closed by the same type of brackets.
Open brackets must be closed in the correct order.
Every close bracket has a corresponding open bracket of the same type.

Example 1:

Input: s = "()[]{}"
Output: true

Example 2:

Input: s = "(]"
Output: false

Solution

Most of the problems that involve parentheses are solved by using the Stack data structure.
One thing that we need to understand is, that whenever we encounter any closed bracket, there must have been an open bracket that could already be seen. Then only there can be a possibility for the given parentheses to be balanced.
Also, it is mandatory for all three different types of brackets.

Say, for example, if we encounter an open round bracket ( then an equivalent closed round bracket ) must already be seen. Similarly, if we encounter an open curly bracket { then an equivalent closed curly bracket } must already be seen and the same goes for square brackets as well.

So, to make sure of this, we would be using the Stack data structure.

Let’s try to understand it with visualization.

Algorithm

The algorithm works as follows:

We will create a stack of characters and visit the whole string starting from index 0 to the end.
If the character is either of the following (, {, or [, we will push it onto the stack.
If the character is either of the following ), }, or ], then we will pop from the stack. But we will have a separate check for the validation. Let’s understand it by an example.
- Suppose the character is ), then the stack top must be (.
- And this is to be validated for the rest of the two types of brackets also.

Intuition

As you know already that the stack top is the last visited character in the string. Therefore, if the current character is ) then the stack should have ( at its top. Hence we will need a separate validation for this. Let’s look at the code.

Code

Java

Python

C++

import java.util.Stack;

class Innoskrit {

    /* This function will return true only when the popped element matches the category of the closing 
    bracket. Otherwise, we will return false. */
    public static boolean isMatching(char openingBracket, char closingBracket) {
	if(openingBracket == '{' && closingBracket == '}')
	    return true;
	if(openingBracket == '(' && closingBracket == ')')
    	    return true;
	if(openingBracket == '[' && closingBracket == ']')
	    return true;
	return false;

    }

    public static boolean isBalanced(String expression) {    		
        Stack<Character> stack = new Stack<>();
		
	for(int i = 0; i < expression.length(); i++) {	
	    
	    // if expression is any of the opening brackets, push it onto the stack
	    if(expression.charAt(i) == '{' || expression.charAt(i) == '(' || expression.charAt(i) == '[') {
	        stack.push(expression.charAt(i));
	    } else {
		/* Check if stack is empty, return false directly.
		Because, having a closing bracket without any opening bracket doesn't mean balanced. */
	        if(stack.empty()) {
		    return false;
		} else if(!isMatching(stack.pop(), expression.charAt(i))){
		    return false;
		}
	    }
	}
		
	/* if everything is perfect till here and stack becomes empty, means the expression is balanced 
	otherwise, if stack doesn't become empty, then return false. */
        if(stack.empty())
	    return true;
			
        return false;
    }

    public static void main(String[] args) {
	System.out.println(Innoskrit.isBalanced("[[({})]]"));
	System.out.println(Innoskrit.isBalanced("[[))"));
    }
}

class Innoskrit:
    
    # This function will return true only when the popped element matches the category of the closing 
    # bracket. Otherwise, we will return false.
    	
    def is_matching(openingBracket, closingBracket):
    	if(openingBracket is '{' and closingBracket is '}'):
    		return True
    	if(openingBracket is '(' and closingBracket is ')'):
    		return True
    	if(openingBracket is '[' and closingBracket is ']'):
    		return True
    	return False
    
    
    def is_balanced(expression):
    
    	stack = []
    		
    	for i in range(len(expression)):
    	    if(expression[i] is '{' or expression[i] is '(' or expression[i] is '['):
    	        stack.append(expression[i])
    	    else:
    		# Check if stack is empty, return false directly.
    		# Because, having a closing bracket without any opening bracket doesn't mean balanced.
    		if(len(stack) == 0):
    		    return False
    
    		if(Innoskrit.is_matching(stack.pop(), expression[i]) is not True):
    		    return False
    
    	# if everything is perfect till here and stack becomes empty, means the expression is balanced 
    	# otherwise, if stack doesn't become empty, then return false.
    	if(len(stack) == 0):
    	    return True
    	return False

if __name__ == '__main__':
    print("true") if Innoskrit.is_balanced("[[()]]") else print("false")
    print("true") if Innoskrit.is_balanced("[[))") else print("false")

#include <bits/stdc++.h> 
using namespace std;

class Innoskrit {
public: 

    /* This function will return true only when the popped element matches the category of the closing 
	bracket. Otherwise, we will return false. */
    static bool isMatching(char openingBracket, char closingBracket) {
    	if(openingBracket == '{' && closingBracket == '}')
    	    return true;
    	if(openingBracket == '(' && closingBracket == ')')
    	    return true;
    	if(openingBracket == '[' && closingBracket == ']')
            return true;
    	return false;
    
    }
    
    static bool isBalanced(const string expression) {
    	stack<char> s;
    	
    	for(int i = 0; i < expression.length(); i++) {
    	    if(expression[i] == '{' || expression[i] == '(' || expression[i] == '[') {
    		s.push(expression[i]);
    	    } else {
    			
    		/* Check if stack is empty, return false directly.
    		Because, having a closing bracket without any opening bracket doesn't mean balanced. */
    		if(s.empty()) {
    	      	    return false;
    		} else if(!isMatching(s.top(), expression[i])){
    		    return false;
    		}
    		s.pop();
    	    }
    	}
    	
    	/* if everything is perfect till here and stack becomes empty, means the expression is balanced
    	otherwise, if stack doesn't become empty, then return false. */
    	if(s.empty())
    	    return true;
    	
    	return false;
    }
};

int main(int argc, char const *argv[]) {
    Innoskrit::isBalanced("[[({})]]") ? cout << "true" << endl : cout << "false" << endl;
    Innoskrit::isBalanced("[[))") ? cout << "true" << endl : cout << "false" << endl;
    return 0;
}