In this chapter, we will learn how to check whether the given parentheses is balanced or not.
In this chapter, we will learn how to check whether the given parentheses is balanced or not.
Given a string s
containing just the characters '('
, ')'
, '{'
, '}'
, '['
and ']'
, determine if the input string is balanced.
An input string is balanced if:
Example 1:
Input: s = "()[]{}"
Output: true
Example 2:
Input: s = "(]"
Output: false
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.
The algorithm works as follows:
(
, {
, or [
, we will push it onto the stack.)
, }
, 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.)
, then the stack top must be (
.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.
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
O(N)
as we are iterating the whole string.
O(N)
as in the worst case, we may end up storing all the elements in the stack present in the string.
© 2022 - All Rights Reserved.