Given a parentheses expression, check if the pairs and orders of “(“, “)”, “{“, “}”, “[“, “]” are correct in the expression.
Example
Expression | Result |
[ ( ) ] { } { [ ( ) ( ) ] ( ) } | Balanced |
[ ( ] ) | Not Balanced |
Solution
After understanding the above problem, we can say that an expression will be balanced if “every opening parenthesis has a closing parenthesis in last opened, first closed order”. This can be computed using a stack. Below is a program in Java to demonstrate this.
import java.util.Stack;
public class Main {
public static void main(String[] args) {
String[] expressions = {
"[()]{}{[()()]()}",
"[(])",
"}"
};
for (String exp : expressions) {
System.out.println(String.format("%s is %s", exp, checkBalanced(exp) ? "Balanced" : "Not Balanced"));
}
}
private static boolean checkBalanced(String input) {
Stack<Character> stack = new Stack<>();
for (int i = 0; i < input.length(); i++) {
char ch = input.charAt(i);
switch (ch) {
case '(':
case '{':
case '[':
stack.push(ch);
break;
case ')':
case '}':
case ']':
if (stack.size() == 0 || !canBePopped(stack.peek(), ch)) {
return false;
} else {
stack.pop();
}
break;
}
}
return stack.size() == 0;
}
private static boolean canBePopped(char stackTop, char ch) {
if (ch == ')' && stackTop == '(') {
return true;
} else if (ch == '}' && stackTop == '{') {
return true;
} else if (ch == ']' && stackTop == '[') {
return true;
} else {
return false;
}
}
}
[()]{}{[()()]()} is Balanced [(]) is Not Balanced } is Not Balanced