Parentheses.java

Parentheses.java

import java.util.Stack;

/*
Using a Stack
Traverse the string expression
- If the current character is a opening bracket ('(' or '{') then push it to stack
- If the current character is a closing bracket (')' or '}') then pop from stack
  and
  if the popped character is the matching opening bracket then balanced
  else
  parenthesis are unbalanced
If there is some starting bracket left in stack then it's unbalanced
*/

class Parser {

  public static boolean checkParenthesesBalance(String input) {

    Stack<String> stack = new Stack<String>();

    boolean isBalanced = false;

    for(int i=0; i < input.length(); i++) {

      String str = "" + input.charAt(i);

      // if opening
      if (str.equals("(") || str.equals("{")) {
        stack.push(str);
      }

      // if closing pop and find pair
      if (str.equals(")") || str.equals("}")) {

        // if stack becomes empty in between then its not balanced
        if(stack.isEmpty()) {
          return false;
        }

        String opening = stack.peek();
        // find pairs
        if(str.equals(")") && opening.equals("(")) {
          stack.pop();
        }
        if(str.equals("}") && opening.equals("{")) {
          stack.pop();
        }
      }
    }

    // if empty stack then its balanced
    if(input.length() > 0 && stack.isEmpty()) {
      isBalanced = true;
    }

    return isBalanced;
  }

}