In this example, we are going to see how to check whether a String is a balanced string or not?
Example
Input: ([{}{}{}]{})
Output: Given string is Balanced
Input: {}[}[}}
Output: Given string is Not Balanced
A string is a Balanced String or not?
I am going to solve this problem by using ArrayDeque; we can also use Stack either.
Approach:
- Here I am sticking to (),[],{} characters, if you wish to have more characters you can free to add these characters into the logic.
- I am adding all open symbols into an array.
- Create a Map containing all corresponding open and close symbols.
- Read String from System.in
- Loop through each character from the String.
- Check each character, whether it contained in open symbol array or not. If it does not contain, insert the symbol into it ArrayDequeue (Stores only open symbols).
- So for a certain point in time, all the open symbols will sit into the ArrayDequeue.
- Now for closed symbols (else case), pop each element from ArrayDqueue and get the corresponding popped element value from the open_close map. If the map doesn’t contain the value of the popped element, we can say the provided string is not balanced.
- This loop will go through the end of the string length, so by the end of the loop, ArrayDeque should be empty, as we are popping for each iteration.
- If it is not empty, we can also say that the provided string is not balanced.
- Let’s see in practice.
A string is a Balanced String or not?
BalancedString.java
import java.util.*;
public class BalancedString {
private char smallOpen = '(';
private char smallClose = ')';
private char midOpen = '[';
private char midClose = ']';
private char bigOpen = '{';
private char bigClose = '}';
List<Character> openList = Arrays.asList(smallOpen, midOpen, bigOpen);
Map<Character, Character> open_closeMap = new HashMap<>();
{
open_closeMap.put(smallOpen, smallClose);
open_closeMap.put(midOpen, midClose);
open_closeMap.put(bigOpen, bigClose);
}
public static void main(String[] args) {
BalancedString balancedString = new BalancedString();
Scanner sc = new Scanner(System.in);
System.out.println("Enter any String..");
String s = sc.nextLine();
System.out.println(balancedString.isBalanced(s) ? "Given string is Balanced" : "Given string is Not Balanced");
}
public boolean isBalanced(String str) {
Deque<Character> deque = new ArrayDeque<>();
for (int i = 0; i < str.length(); i++) {
char c = str.charAt(i);
if (openList.contains(c)) {
deque.push(c);
} else {
if (deque.isEmpty()) {
return false;
}
char pop = deque.pop();
if (open_closeMap.get(pop) != c) {
return false;
}
}
}
return deque.isEmpty();
}
}
Output
([{}{}{}]{})
Given string is Balanced
Happy Learning 🙂