Java Program To Check For Balanced Brackets In An Expression (Well-Formedness) Using Stack
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: BalancedInput: exp = β[(])β
Output: Not Balanced
Algorithm:
- Declare a character stack S.
- Now traverse the expression string exp.
- If the current character is a starting bracket (β(β or β{β or β[β) then push it to stack.
- If the current character is a closing bracket (β)β or β}β or β]β) then pop from stack and if the popped character is the matching starting bracket then fine else brackets are not balanced.
- After complete traversal, if there is some starting bracket left in stack then βnot balancedβ
Below image is a dry run of the above approach:
Below is the implementation of the above approach:
Java
// Java program for checking // balanced brackets import java.util.*; public class BalancedBrackets { // function to check if brackets are balanced static boolean areBracketsBalanced(String expr) { // Using ArrayDeque is faster than using Stack class Deque<Character> stack = new ArrayDeque<Character>(); // Traversing the Expression for ( int i = 0 ; i < expr.length(); i++) { char x = expr.charAt(i); if (x == '(' || x == '[' || x == '{' ) { // Push the element in the stack stack.push(x); continue ; } // If current character is not opening // bracket, then it must be closing. So stack // cannot be empty at this point. if (stack.isEmpty()) return false ; char check; switch (x) { case ')' : check = stack.pop(); if (check == '{' || check == '[' ) return false ; break ; case '}' : check = stack.pop(); if (check == '(' || check == '[' ) return false ; break ; case ']' : check = stack.pop(); if (check == '(' || check == '{' ) return false ; break ; } } // Check Empty Stack return (stack.isEmpty()); } // Driver code public static void main(String[] args) { String expr = "([{}])" ; // Function call if (areBracketsBalanced(expr)) System.out.println( "Balanced " ); else System.out.println( "Not Balanced " ); } } |
Output
Balanced
Time Complexity: O(n)
Auxiliary Space: O(n) for stack.
Please refer complete article on Check for Balanced Brackets in an expression (well-formedness) using Stack for more details!