validate brackets

Problem

Given a string containing just the characters '(', ')', '{', '}', '[' and ']', determine if the input string is valid.

An input string is valid if:

Open brackets must be closed by the same type of brackets.

Open brackets must be closed in the correct order.

Note that an empty string is also considered valid.  

For example: the following is valid

({}{[ ]} )

the following is invalid

({}{[ ]}} )

Solution

If we observe the valid pattern, a right bracket should always have a matching left bracket. 

For example 

({}{[ ]} )

[] is a pair, if we remove it 

({}{} )

the next pair is {}

remove it

({} )

the next pair is {}

remove it

( )

the next pair is

()

This is a valid expression.

We can use a stack to remove the matching pairs from the expression. we push the left bracket into the stack. Whenever a right bracket is met, we pop an element from the stack and check. Once we exampled all the characters, the stack should be empty. 

A detail is to prevent the stack to throw exceptions, we need to check isEmpty before pop.

import java.util.*;
class Validator {
  public static boolean validate(char[] a) {
    Stack<Character> stack = new Stack<>();
    //({}{[ ]} )
    //
    for(int i = 0; i < a.length; i++) {
      char v = a[i];
      if(v == '(' || v == '{' || v == '[') {
        stack.push(v);
      } else if(v == ')' || v == '}' || v == ']') {
        char w = stack.iEmpty() ? '#': stack.pop();
        if(v == '}' && w != '{')
          return false;
        if(v == ']' && w != '[')
          return false;
        if(v == ')' && w != '(')
          return false;
      } else if(v == ' '){
          //do nothing
      } else {
        System.out.println("unexpected character" + v);
      }
    }
    if(stack.isEmpty())
      return true;
    else
      return false;
  }
  public static void main(String...args) {
    String str = "({}{[ ]} )";
    System.out.println(validate(str.toCharArray()));
  }
}

The time complexity is to iterate the array O(N), the space complexity is bound by the stack size, which is O(N)