This is again a classic problem of detecting matching parenthesis. In fact, the title even tells you the appropriate data structure to use in order to solve this problem. The solution relies on the fact that if a left bracket (by bracket in this post I mean ‘(‘, ‘[‘ or ‘{‘) is found we can push it on to the stack and eventually whenever the corresponding right bracket (‘)’, ‘]’ or ‘}’) is found then we would be popping it off the stack. If the stack is empty after we are done with the entire input then we know that the input string was balanced properly.
The code I have written should be easy to understand but is a bit lengthy. In retrospect I could have refactored the checking and comparing part into a function so it looks nicer.
FYI this is what all those characters are actually called:
( ) – Parenthesis
{ } – Braces
[ ] – Brackets
Problem: https://www.hackerrank.com/challenges/ctci-balanced-brackets
Solution:
import java.io.*;
import java.util.*;
import java.text.*;
import java.math.*;
import java.util.regex.*;
public class Solution {
public static boolean isBalanced(String expression) {
LinkedList<Character> stack = new LinkedList<>();
char[] input = expression.toCharArray();
for (int i=0; i<input.length; i++) {
if (stack.isEmpty()) {
stack.push(input[i]);
} else {
if (stack.peek() == '{') {
if (input[i] == ']' || input[i] == ')') {
return false;
} else if (input[i] == '}') {
stack.pop();
} else {
stack.push(input[i]);
}
} else if (stack.peek() == '[') {
if (input[i] == '}' || input[i] == ')') {
return false;
} else if (input[i] == ']') {
stack.pop();
} else {
stack.push(input[i]);
}
} else if (stack.peek() == '(') {
if (input[i] == ']' || input[i] == '}') {
return false;
} else if (input[i] == ')') {
stack.pop();
} else {
stack.push(input[i]);
}
}
}
}
return stack.isEmpty();
}
public static void main(String[] args) {
Scanner in = new Scanner(System.in);
int t = in.nextInt();
for (int a0 = 0; a0 < t; a0++) {
String expression = in.next();
System.out.println( (isBalanced(expression)) ? "YES" : "NO" );
}
}
}