WAP to Verify Balanced Parentheses In Java

Verify Balanced Parentheses In Java: This Java program checks whether the given expression contains balanced pairs of brackets and parentheses. It uses a stack data structure to efficiently track and verify the correctness of the pairs and their orders.

Verify Balanced Parentheses In Java

package com.softwaretestingo.interviewprograms;
import java.util.Stack;
public class InterviewPrograms36 
{
	// Given an expression string exp, write a program to examine whether the pairs and the orders of “{“, “}”, “(“, “)”, “[“, “]” are correct in exp.
	// Example: 
	// Input: exp = “[()]{}{[()()]()}” 
	// Output: Balanced
	// {},[],{]
	// Input: exp = “[(])” 
	// Output: Not Balanced
	public static void main(String[] args) 
	{
		String equ = "[()]{}{[()()]()}";
		Stack<Character> stack = new Stack<>();
		for (int i =0 ; i< equ.length() ; i++) 
		{
			if (equ.charAt(i) == '{' || equ.charAt(i) == '[' || equ.charAt(i) == '(') 
			{
				stack.push(equ.charAt(i));
			}
			else if (!stack.isEmpty() && ( (equ.charAt(i) == ']' && stack.peek() == '[') || (equ.charAt(i) == '}' && stack.peek() == '{') || (equ.charAt(i) == ')' && stack.peek() == '(')))
			{
				stack.pop();
			}
			else 
			{
				stack.push(equ.charAt(i));
			}
		}
		if (stack.empty())
		{
			System.out.println(stack.toString());
			System.out.println("balanced");
		}
		else 
		{
			System.out.println(stack.toString());
			System.out.println("Not balanced");
		}
	}
}

Output

[]
balanced

Here’s a breakdown of the program:

1. Define the main method:
   • The entry point of the program is the main method.
2. Initialize the input expression:
   • The input expression equ is initialized with the value “[()]{}{()()}”.
3. Check for balanced pairs using a stack:
   • The program uses a Stack<Character> named stack to store the opening brackets and parentheses.
   • It iterates through each character of the input expression using a for loop.
   • If the current character is an opening bracket or parenthesis (‘{‘, ‘[‘, or ‘(‘), it is pushed onto the stack.
   • If the current character is a closing bracket or parenthesis (‘]’, ‘}’, or ‘)’), the program checks if the stack is not empty and whether the top of the stack contains the corresponding opening bracket or parenthesis. If this condition is met, it pops the top element from the stack, indicating a balanced pair.
   • If the current character does not match the expected pair, it is pushed onto the stack.
4. Determine if the expression is balanced:
   • After processing all characters, the stack will contain any unbalanced brackets or parentheses that were not matched.
   • If the stack is empty, the expression is balanced, and the program prints “balanced.”
   • If the stack is not empty, the expression is not balanced, and the program prints “Not balanced.”

Overall, this program uses a stack to check whether the given expression contains balanced pairs and orders of brackets and parentheses. For the input “[()]{}{()()}”, the output will be “balanced” as all pairs are correctly matched and ordered. For the input “[(])”, the output will be “Not balanced” as the pair “(]” is not balanced. The program effectively demonstrates how to use a stack for bracket and parenthesis matching.

Alternative Way 1:

This Java program checks whether the given expression contains balanced pairs of brackets and parentheses using a stack implemented using a LinkedList. It also uses a HashMap to store the opening and closing brackets to efficiently check for balanced pairs.

package com.softwaretestingo.interviewprograms;
import java.util.HashMap;
import java.util.LinkedList;
public class InterviewPrograms36_1 
{
	// Given an expression string exp, write a program to examine whether the pairs and the orders of “{“, “}”, “(“, “)”, “[“, “]” are correct in exp.
	// Example: 
	// Input: exp = “[()]{}{[()()]()}” 
	// Output: Balanced
	// {},[],{]
	// Input: exp = “[(])” 
	// Output: Not Balanced

	static HashMap<String, String> bracketDetails=new HashMap<String, String>();
	public static void main(String[] args) 
	{
		storeBracketStartAndEnd();
		String testString = "[{()}](){()}";
		boolean status = true ;
		LinkedList<String> l1 = new LinkedList<String>();
		testString = testString.replaceAll("[^\\(\\{\\[\\)\\}\\]]", "");
		for ( int i = 0 ; i < testString.length(); i++ )
		{
			String element = String.valueOf(testString.charAt(i));
			if (element.equalsIgnoreCase("(")||element.equalsIgnoreCase("{")||element.equalsIgnoreCase("["))
			{
				l1.addFirst (bracketDetails.get(element));
			}
			else 
			{
				if (! element.equalsIgnoreCase(l1.getFirst())) 
				{
					status = false;
					break;
				} 
				else 
				{
					l1.removeFirst();
				}
			}

		}
		if (status) 
		{
			System.out.println ("All brackets are balanced");
		} 
		else 
		{
			System.out.println("Brackets are not balanced");
		}
	}
	public static void storeBracketStartAndEnd() 
	{
		bracketDetails.put("(",")");
		bracketDetails.put("{","}");
		bracketDetails.put("[","]");
	}
}

Output

All brackets are balanced

Here’s a breakdown of the program:

1. Define the main method:
   • The entry point of the program is the main method.
2. Initialize the input expression:
   • The input expression testString is initialized with the value “{()}{()}”.
3. Create a HashMap for bracket details:
   • The program uses a static HashMap named bracketDetails to store the opening and closing brackets.
4. Process the input expression and create a stack:
   • The program removes any characters from testString that are not brackets or parentheses using replaceAll(“[^\\(\\{\\[\\)\\}\\]]”, “”).
   • It creates a LinkedList named l1 to act as the stack to store the opening brackets and parentheses.
5. Check for balanced pairs using the stack:
   • The program iterates through each character of the testString.
   • If the character is an opening bracket or parenthesis (‘(‘, ‘{‘, or ‘[‘), it is added to the front of the LinkedList l1.
   • If the character is a closing bracket or parenthesis (‘)’, ‘}’, or ‘]’), the program checks whether the first element of l1 (top of the stack) matches the corresponding opening bracket or parenthesis using the bracketDetails HashMap. If it matches, the first element is removed from l1 (popped from the stack).
   • If the stack does not contain the correct opening bracket or parenthesis, the program sets the status variable to false, indicating unbalanced pairs.
6. Print the result:
   • After processing all characters, if the status variable is true, the program prints “All brackets are balanced,” indicating that all pairs are correct.
   • If the status variable is false, the program prints “Brackets are not balanced,” indicating that there is an issue with the pairs in the expression.

Overall, this program demonstrates how to use a stack (implemented as a LinkedList) and a HashMap to efficiently check for balanced pairs of brackets and parentheses in the given expression. For the input “{()}{()}”, the output will be “All brackets are balanced,” indicating that all pairs are correctly matched and ordered. For the input “[(])”, the output will be “Brackets are not balanced” as the pair “(]” is not balanced.