import java.util.Stack;

class Solution {
  public boolean isValid(String s) {
      Stack<Character> stack = new Stack<>();

      for (int i = 0; i < s.length(); i++)
      {
          char c = s.charAt(i);

          if (c == '(' || c == '{' || c == '[')
          {
              stack.push(c);
          }
          else // it can only be the closed ones
          {
              if (stack.isEmpty())
              {
                  return false;
              }

              char popped = stack.pop();

              if ((popped == '(' && c != ')') || (popped == '{' && c != '}') || (popped == '[' && c != ']'))
              {
                  return false;
              }
          }
      }

      return stack.isEmpty();
  }
}