Program to Check Balanced Parentheses in Java

Overview

In these tutorials, we will write a program that will check the balanced parentheses in a given string.

Parentheses include brackets (), curly braces {}, and square brackets []. Our program should check each opening parentheses must have similar closing parentheses. 

Example

Input: s = “{{{[]()}}}“
Output: Balanced
Input: s = “}{}()[]”
Output: Not Balanced

Let’s see the first input from the example. The string contains a pattern where each opening parentheses has its corresponding closing parentheses.

Balanced parentheses must have an order i.e closing parentheses should not come before their corresponding parentheses.

Check balance parentheses using Stack

Stack data structure follows LIFO principle. lets see how we can use it.

  • In the first iteration, if closing parentheses encountered, then it is not balanced.
  • If it is opening parenthesis then push it into the stack.
  • If the character is closing parentheses in the next iteration, and the top of the stack are corresponding opening parentheses, remove the element from the stack.
  • So on, after the end of the iteration, if the stack is empty then the given string is balanced.

Here is the implemented code:

package test2;

import java.util.Stack;

public class BalancedBrace {
	
	public static int isBalanced(String str) {
		
		if(str.isEmpty()) {
			return -1;
		}
		
		//create Dequeue object
		Stack<Character> stack = new Stack<>();
		
		//loop the string
		for(int i = 0 ; i < str.length(); i++) {
			
			//get char at the index
			char current = str.charAt(i);
			
			//insert into stack if string contains
			if(current == '{' || current == '(' || current == '[') {
				stack.push(current);
			}
			
			if(stack.isEmpty() &&( current == '}' || current == ']' || current == ')')) {
				return 0;
			}
			
			//compare peek of the stack and current char 
			if(!stack.isEmpty() && ((stack.peek() == '{' && current == '}') 
						|| (stack.peek() == '(' && current == ')') 
						|| (stack.peek() == '[' && current == ']'))) {
					
					stack.pop();
			}
			
		}
		return stack.isEmpty()?1:0;
		
	}
	
	
	public static void main(String[] args) {
		String expression1 = "{}{{{(({{[[[[]]]]}}))}}}";
		String expression2 = "{}{([])}";
		int isValid = isBalanced(expression1);
		
		if(isValid == 1) {
			System.out.println("Balanced");
		}else if(isValid == -1) {
			System.out.println("Empty string");
		}else {
			System.out.println("Not balanced");
		}
	}

}
balanced

Conclusion

In this post, we wrote a program that will check balanced parentheses from a string containing an expression.

If you find better solution or have a suggestion please comment below.

Recommended:

Leave A Reply

Your email address will not be published.