Balanced Parentheses in Java (with code)

 

Parentheses, brackets, and braces are used extensively to group and organize expressions, conditions, and code blocks. When these parentheses are not balanced correctly, it can lead to syntax errors, logical inconsistencies, and even program crashes. In this article, we will discuss everything about Balanced Parentheses in Java.

What are Balanced Parentheses? 

Balanced parentheses refer to a state where every opening parenthesis has a corresponding closing parenthesis, and they are properly nested within each other. In other words, the number of opening and closing parentheses should match, and the order of their appearance should follow a well-defined structure.

Consider the following examples :

{[]}) – Unbalanced parentheses

{()} [] –  Balanced Parentheses

Here is the problem statement we will solve here: We are given a string s that contains the characters ‘(‘, ‘)’, ‘{‘, ‘}’, ‘[‘ and ‘]’. We need to determine if the input string has balanced parentheses or not.

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.

How to Check for Balance Parentheses in Java?

Here is the step-by-step approach to check for balance paratheses:

1. In order to check the balancing of parentheses the best data structure to use is stack.
2. Now, we loop over all the characters of the string and one-by-one push them onto the stack.
3. So if the stack is empty we push the bracket or character of string into the stack.
4. Now if the character of the string is an open parentheses we push it into the stack.
5. If we encounter closed parentheses, we check if the top of the stack contains parentheses of the same type or not. If it doesn’t, we return false else we continue. 
6. At the end, if the stack is empty, implies that the parentheses were balanced, so we return true.

Below is the Java Program to implement the above algorithm:

import java.util.*;

class HelloWorld {
   public static void main(String[] args) {
       String s1 = "()[]{}";
       String s2 = "({)}[]";
 
       if(isValid(s1)) System.out.println(s1 + " has Balanced Parentheses");
       else System.out.println(s1 + " doesn't have Balanced Parentheses");
       if(isValid(s2)) System.out.println(s2 + " has Balanced Parentheses");
       else System.out.println(s2 + " doesn't have Balanced Parentheses");
   }

   public static boolean isValid(String s) {
       Stack<Character> stack = new Stack<>();
       for(int i =0 ;i < s.length(); i++){
           char ch = s.charAt(i);
           if(stack.size() == 0){
               stack.push(ch);
               continue;
           }
           if(ch == '{' ||ch == '(' ||ch == '['){
               stack.push(ch);
           }else{
               char ch1 = stack.peek();
               if(ch1 == '(' && ch == ')'){
                   stack.pop();
               }
               else if(ch1 == '{' && ch == '}'){
                   stack.pop();
               }
               else if(ch1 == '[' && ch == ']'){
                   stack.pop();
               }else{
                   stack.push(ch);
               }
           }
       }
       if(stack.size() == 0){
           return true;
       }
       return false;
   }
}

Output:

()[]{} has Balanced Parentheses

({)}[] doesn’t have Balanced Parentheses

Illustration with Example

Given a string s, say, “([{}])”.

As the stack is empty, we push 1st character, i.e. ‘(‘ into the stack.

Now, as the next character is open parentheses,i.e. ‘[‘, we push it into the stack.

Again, the next character is open parentheses,i.e., ‘{‘ we push it into the stack.

Now we encounter closed parentheses,i.e., ‘}’.We peek into the stack, and as the top of the stack contains open parentheses of the same type, we pop it from the stack.

Again we encounter closed parentheses, i.e., ‘]’. As the top contains parentheses of the same type, we pop.

Again we encounter closed parentheses, i.e., ‘)’. As the top contains parentheses of the same type, we pop.

As the stack gets empty, we return true.

Time and space Complexity 

The time complexity for checking balanced parentheses is O(n), where n is the length of the input string. This is because the code iterates over each character in the string exactly once.

The space complexity of the code is O(n), where n is the length of the input string. This is because the code uses a stack to store the opening parentheses encountered. In the worst case, if all the characters in the string are opening parentheses, the stack will have a maximum of n/2 elements.

Role of Balanced Parentheses in Programming

Here are the main use cases you should know about:

• Syntax Validation: One of the primary roles of balanced parentheses is to validate the syntax of programming languages. They define the correct structure and grouping of code elements. A missing or misplaced parenthesis can lead to syntax errors that prevent the code from compiling or executing.
• Precedence and Evaluation: Balanced parentheses enforce the order of precedence in mathematical expressions. They determine which sub-expressions are evaluated first, ensuring the desired outcome. Without balanced parentheses, the evaluation may produce incorrect or unexpected results.
• Code Blocks and Control Flow: Parentheses are used to define code blocks within conditional statements and loops. A well-balanced structure ensures that the appropriate code is executed based on the condition’s outcome. Incorrectly balanced parentheses can lead to logical errors or unintended program behavior.

Conclusion

Balanced parentheses are fundamental in programming, ensuring code integrity and proper execution. They validate syntax, govern precedence, and control the flow of code blocks. Still confused? no worries, connect with our experts online for any type of Java homework help. We are always happy to assist you!