Check balanced parentheses using a stack.

boolean isValid(String s) {
  Deque<Character> st = new ArrayDeque<>();
  for (char c : s.toCharArray()) {
    if (c == '(' || c == '[' || c == '{') st.push(c);
    else {
      if (st.isEmpty()) return false;
      char o = st.pop();
      if (c == ')' && o != '(') return false;
      if (c == ']' && o != '[') return false;
      if (c == '}' && o != '{') return false;
    }
  }
  return st.isEmpty();
}