Balanced Parentheses

In this chapter, we will learn how to check whether the given parentheses is balanced or not.

Problem Statement

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

An input string is balanced if:

1. Open brackets must be closed by the same type of brackets.
2. Open brackets must be closed in the correct order.
3. 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:

1. We will create a stack of characters and visit the whole string starting from index 0 to the end.
2. If the character is either of the following `(`, `{`, or `[`, we will push it onto the stack.
3. 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

``````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;
}``````

Output:

``````true
false``````

Time Complexity

`O(N)` as we are iterating the whole string.

Space Complexity

`O(N)` as in the worst case, we may end up storing all the elements in the stack present in the string.

Innoskrit

We're building a next-level EdTech Startup.