[2 Ways] Java Program To validate the Bracket Expression

This program checks for the valid bracket string expression and returns true/false. Basically we need to use stack effectively to check the valid brackets.

 

Algorithm/Idea is:

• Keep the list of allowed brackets (predefined) in some collections, here we are using the map<character, character> to keep the open and closed brackets of different types.
• Iterate the string expression character by character and check whether the character is of only allowed brackets (either open / close)
• If the bracket is open type then just add it to the stack using stack.push().
• If the bracket is close type then it just performs stack.pop().
• If any other character is encountered in between just perform the iterations for the next available brackets/till the end accordingly return true/false.

package com.ngdeveloper;

import java.util.HashMap;
import java.util.Map;
import java.util.Stack;

/**
 * This file contains the BracketsExpressionCheck.java class.
 * 
 *
 * @author NAVEENKUMAR G
 */
public class BracketsExpressionCheck {
  public static boolean isValidExpression(String input) {
    boolean response = true;
    Map<Character, Character> expressionInputMap = new HashMap<Character, Character>();
    expressionInputMap.put('(', ')');
    expressionInputMap.put('{', '}');
    expressionInputMap.put('[', ']');
    Stack<Character> stack = new Stack<>();
    char[] inputCharArray = input.toCharArray();
    for (int i = 0; i < inputCharArray.length; i++) {
      // if block just checks only the (, {, [ characters and adds to stack
      if (expressionInputMap.keySet().contains(inputCharArray[i])) {
        stack.push(inputCharArray[i]);
      } // if no open bracket, then it just checks for the close brackets and pop out from the stack
      else if (expressionInputMap.values().contains(inputCharArray[i])) {
        if (expressionInputMap != null && expressionInputMap.size() > 0 && !stack.isEmpty()
            && expressionInputMap.get(stack.peek()) == inputCharArray[i]) {
          stack.pop();
        } else {
          return false;
        }
      }
    }
    return response;
  }

  public static void main(String[] args) {
    String input = "{[]()}";
    System.out.println(isValidExpression(input));
  }
}

 

Input:

{[]()}

Output:

true

 

 

Input:

{abc)]

Output:

false

Way 2 [With simple for loop]

package com.ngdeveloper.algorithms.stack;

import java.util.Stack;

public class BracketExpressionWay2 {

    public static void main(String[] args) {
        String input = "[({}]";
        System.out.println(isExpressionValid(input));
    }

    private static boolean isExpressionValid(String input) {
        Stack<Character> stack = new Stack<>();
        for (int i = 0; i < input.length(); i++) {
            if (input.charAt(i) == '(' || input.charAt(i) == '{'
                    || input.charAt(i) == '[') {
                stack.push(input.charAt(i));
            } else {
                if (stack.isEmpty()) {
                    return false;
                }

                Character ch = Character.MIN_VALUE;
                switch (input.charAt(i)) {
                    case ')':
                        ch = stack.pop();
                        if (ch == '[' || ch == '{') {
                            return false;
                        }
                        break;
                    case ']':
                        ch = stack.pop();
                        if (ch == '(' || ch == '{') {
                            return false;
                        }
                        break;
                    case '}':
                        ch = stack.pop();
                        if (ch == '(' || ch == '[') {
                            return false;
                        }
                        break;

                }
            }
        }
        return stack.isEmpty();
    }

}

Output:

[({}] -> false
[({})] -> true

Feel free to write your comments in the below comments section.