content: package leetcode;
  
  import java.util.ArrayDeque;
  import java.util.Deque;
  
  public class ValidParentheses {
      public static boolean isValid(String s) {
          // Using ArrayDeque is faster than using Stack class
          Deque<Character> stack = new ArrayDeque<>();
  
          // Traversing the Expression
          for (int i = 0; i < s.length(); i++) {
              char x = s.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());
      }
  }
  