Balanced Brackets
Imagine being an engineer at Google and working on the backend of their search engine. Your job is to check every line of code for efficiency, reliability, and freedom from bugs. One day, you encounter a problem that appears very easy on paper yet is critical for your system to work: to ensure each bracket in your code is balanced. While it may be small, unbalanced brackets have serious repercussions: from crashes to processing incorrect data. In the fast-moving world of technology, in which every millisecond counts toward efficiency, checking for balanced brackets is essential to ensuring that one has written resilient code.
Challenge
Just as Google does, many tech companies face the challenge of checking for balanced brackets in their code. Be it some complex algorithm or just validating user input, one of the most basic tasks is to make sure that your brackets are balanced. In this blog, we will see how we can check for balanced brackets in C++, Java, and Python using various approaches. We shall emphasize the keywords repeatedly so you understand how important balanced brackets are and how to treat them appropriately in your code.
Why balanced brackets are important
Brackets help to structure and give the flow in any kind of coding. Hence, in any programming language, the brackets—either parentheses (), curly braces {}, or square brackets []—should be well-paired and -nested. Balanced bracket expression means every opening bracket has its corresponding closing one, showing up in that particular order.
In many programming scenarios, unbalanced brackets may result in syntax errors, logical errors, or even runtime failures. For this reason, checking for balanced brackets is not a best practice; it is finally a step necessary to ensure that code is well-formed and error-free.
Problem: Check for balanced brackets
The problem at hand is to write a program to check whether a given expression contains balanced brackets. By balanced brackets, we mean for any open bracket, there exists a corresponding closing bracket in the proper order.
Now, let us see different techniques to check for balanced brackets using C++, Java, and Python.
Approach 1: Checking balanced brackets using a stack
One of the most common and efficient ways to check for balanced brackets is by using a stack. A stack is a data structure following the Last In, First Out working policy, which makes it very convenient in managing pairs of brackets.
Steps to Implement:
- Initialize a Stack: Create a stack for storing the opening brackets while going through the expression.
- Traverse the Expression: For each character in the expression:
- If it's an opening bracket, push it onto the stack.
- If it's a closing bracket, check whether the bracket on top of the stack matches it. If it does, pop the stack; otherwise, the brackets are not balanced.
- Final Check: After the expression has been traversed, if the stack is empty, the brackets will be balanced; otherwise, they will not be.
Example in C++:
1#include <bits/stdc++.h>
2using namespace std;
3
4bool areBracketsBalanced(string expr) {
5stack<char> temp;
6 for (int i = 0; i < expr.length(); i++) {
7 if (temp.empty()) {
8 temp.push(expr[i]);
9 } else if ((temp.top() == '(' && expr[i] == ')')
10|| (temp.top() == '{' && expr[i] == '}')
11 || (temp.top() == '[' && expr[i] == ']')) {
12 temp.pop();
13} else {
14 temp.push(expr[i]);
15 }
16 }
17 return temp.empty();
18}
19
20int main() {
21 string expr = "{()}[]";
22 if (areBracketsBalanced(expr))
23 cout << "Balanced";
24 else
25cout << "Not Balanced";
26 return 0;
27}Example in Java
1import java.util.Stack;
2
3public class BalancedBrackets {
4
5 public static boolean areBracketsBalanced(String expr) {
6 Stack<Character> stack = new Stack<>();
7 for (char ch : expr.toCharArray()) {
8if (ch == '(' || ch == '{' || ch == '[') {
9 stack.push(ch);
10 } else if (ch == ')' && !stack.isEmpty() && stack.peek() == '(') {
11stack.pop();
12 } else if (ch == '}' && !stack.isEmpty() && stack.peek() == '{') {
13 stack.pop();
14} else if (ch == ']' && !stack.isEmpty() && stack.peek() == '[') {
15 stack.pop();
16 } else {
17return false;
18 }
19 }
20 return stack.isEmpty();
21 }
22
23 public static void main(String[] args) {
24String expr = "{()}[]";
25 if (areBracketsBalanced(expr))
26 System.out.println("Balanced");
27 else
28 System.out.println("Not Balanced");
29 }
30}Example in Python:
1def are_brackets_balanced(expr):
2 stack = []
3for char in expr:
4 if char in ["(", "{", "["]:
5 stack.append(char)
6 else:
7 if not stack:
8return False
9 current_char = stack.pop()
10 if current_char == '(' and char != ")":
11 return False
12If current_char == "{" and char!="}":
13 return False
14 if current_char == "[" and char!"]=
15return False
16 return not stack
17
18expr = "{()}[]"
19if are_brackets_balanced(expr):
20 print("Balanced")
21else:
22 print("Not Balanced")This solution would work using a stack to check for balanced brackets, for the simple reason that each opening bracket will be matched with its correct corresponding closing bracket in the proper order. Further, this solution is broad and very efficient.
Approach 2: Checking balanced brackets without using a stack
Another approach to the balanced bracket problem would involve using counters instead of a stack. It is not common but might be helpful in some cases.
Steps to Implement:
- Use Counters: For each type of bracket, create a counter; that means counters for each kind of bracket are to be initialized.
- Traverse the Expression: For every character in the expression, increment the counter for the opening bracket and decrement for the closing bracket.
- Check for Unbalanced Brackets: If at any time the counter of a closing bracket exceeds the counter of the opening bracket, then the brackets are unbalanced.
- Final Check: At the end of scanning the expression, if all counters are zero, then the brackets are balanced.
Example in C++:
1#include <iostream>
2using namespace std;
3
4bool areBracketsBalanced(string expr) {
5 int open_paren = 0, open_curly = 0, open_square = 0;
6 for (char ch : expr) {
7if (ch == '(') open_paren++;
8 if (ch == '{') open_curly++;
9 if (ch == '[') open_square++;
10 if (ch == ')') open_paren--;
11 if (ch == '}') open_curly--;
12if (ch == ']') open_square--;
13 if (open_paren < 0 || open_curly < 0 || open_square < 0)
14 return false;
15 }
16 return open_paren == 0 && open_curly == 0 && open_square == 0;
17}
18
19int main() {
20string expr = "{()}[]";
21 if (areBracketsBalanced(expr))
22 cout << "Balanced";
23 else
24 cout << "Not Balanced";
25 return 0;
26}Example in Java:
1public class BalancedBrackets {
2
3 public static boolean areBracketsBalanced(String expr
4int openParen = 0, openCurly = 0, openSquare = 0;
5 for(char ch : expr.toCharArray()){
6 if(ch == '(') openParen++;
7 if(ch == '{') openCurly++;
8if (ch == '[') openSquare++;
9 if (ch == ')') openParen--;
10 if (ch == '}') openCurly--;
11 if (ch == ']') openSquare--;
12if (openParen < 0 || openCurly < 0 || openSquare < 0)
13 return false;
14 }
15 return openParen == 0 && openCurly == 0 && openSquare == 0;
16}
17
18 public static void main(String[] args) {
19 String expr = "{()}[]";
20 if (areBracketsBalanced(expr))
21 System.out.println("Balanced");
22 else
23 System.out.println("Not Balanced");
24}Example in Python:
1def are_brackets_balanced(expr):
2 open_paren, open_curly, open_square = 0, 0, 0
3 for char in expr:
4 if char == '(':
5 open_paren += 1
6 if char == '{':
7open_curly += 1
8 if char == '[':
9 open_square += 1
10 if char == ')':
11 open_paren -= 1
12if char == '}':
13 open_curly -= 1
14 if char == ']':
15 open_square -= 1
16if open_paren < 0 or open_curly < 0 or open_square < 0:
17 return False
18 return open_paren == 0 and open_curly == 0 and open square == 0
19
20expr = "{()}[]"
21if are_brackets_balanced(expr):
22 print("Balanced")
23else:
24 print("Not Balanced")Conclusion: Balancing brackets
Balanced brackets are a part of any well-written code. Be it in the implementation of a sophisticated algorithm or simply for the sustainability of a structure, checking the balanced brackets is very essential. Clearly, the most common and most efficient way to do it is by using a stack, though other ways may be relevant for some purposes, like using counters.
FAQs
What is a parenthesis checker?
How do you identify parentheses?
What is parenthesis ()?
How do you show parentheses?
Sign-in First to Add Comment
Leave a comment 💬
All Comments
No comments yet.