There are situations when checking the balancing of brackets is very important especially while you are working with Mathematical Expressions or Programming Languages or parsing expressions with brackets as placeholders. This question is quite common among Interview Questions, and famous programming-related websites Hackerrank and LeetCode. This question can be solved using any programming language such as Java, Python, C++, C#, VB.NET, JavaScript, or other programming languages. The intention is to scan the expression and validate that the brackets found in the expression are balanced i.e., every opening bracket (, {, or [ have its associated closing ), }, or ] in the correct order. The best approach to solve this problem is using a Stack. You can use language built-in Stack or can implement your own Stack Data Structure.
Algorithm
- Create an Empty Stack.
- Scan the Expression letter by letter.
- If the letter is opening bracket (, {, or [, push it to the stack.
- If the letter is any closing bracket ), }, or ], then check if the stack is not empty.
- If the stack is empty, return false as it is an invalid expression.
- If the stack is not empty, then check the top element from the stack to match its associated closing bracket ( ), [ ], or { }.
- If they match continue scanning and checking the rest of the letters.
- If they don’t match, return false to indicate an invalid expression.
- Once the entire expression is scanned and validated, check the stack is empty or not. If the stack is not empty that indicates the expression is not valid.
- Otherwise, expression is valid and brackets are balanced.
Code
* Program: Check Balanced Brackets
*
* Programmer: CodingHelpLine
* Web: https://codinghelpline.org
*
* Description:
* Program to validate that the given expression has balanced braces. If
* the braces are balanced output Success Message or failure message otherwise.
*************************************************************************/
#include <iostream>
#include <string>
#include <stack>
using std::string;
using std::stack;
using std::cout;
using std::cin;
using std::endl;
// Function prototype
bool checkBrackets(string expression);
/**
* Main method - entry point of the program
*
* @return Success or Failure
*/
int main() {
//Let me write few expressions
string exp [5] = {"{()}",
"[2+{3*2+(3-2)}]",
"[a(b)c{d}{[}]]",
"{[{()}]}",
"{[(])}"
};
for(int i=0; i<5; i++) {
cout << "Expression: " << exp[i] << endl;
if(checkBrackets(exp[i])) {
cout << "Expression is balanced!" << endl;
} else {
cout << "Expression is not balanced!" << endl;
}
}
return EXIT_SUCCESS;
}
/**
* Function to check whether there are balanced brackets (), {}, []
* or not. If balanced, return true, otherwise return false.
*
* @param expression to validate
* @return indicate balanced or not
*/
bool checkBrackets(string expression)
{
// declare stack
stack<char> stack;
for(size_t i=0; i<expression.length(); i++)
{
char ch = expression[i];
if(ch == '(' || ch == '[' || ch == '{')
{
stack.push(ch);
}
else if(ch == ')' || ch == '}' || ch == ']')
{
if(!stack.empty()) {
char c = stack.top();
if( (ch == ')' && c == '(') || (ch == '}' && c == '{') || (ch == ']' && c == '[') ) {
stack.pop(); // remove opening combination
} else {
return false; // indicate expression is not balanced.
}
} else {
return false; // means no opening bracket to pair
}
}
}
// check if stack is empty
if(!stack.empty()) {
return false;
}
// reach here - means the expression has balanced brackets
return true;
}