Java Program To validate the Bracket Expression

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

203 total views, 2 views today

Leave a Reply

Your email address will not be published. Required fields are marked *

This site uses Akismet to reduce spam. Learn how your comment data is processed.