만드는 중입니다

아직 만드는 중이라 바뀔 수 있습니다

와일드카드 괄호 문자열

면접 대비

시간 제한1초메모리 제한1024 MB

요약
'(', ')', '?', '*'로 이루어진 문자열에서 '?'와 '*'를 채워 올바른 괄호 문자열을 만들 수 있는지 판별합니다.
난이도

보통10점 중 5점

유형
문자열, 그리디
정답자
아직 제출이 없습니다

문제

(와 )로 이루어진 문자열이 올바른 괄호 문자열이려면 다음 규칙을 따라야 합니다.

  • SS가 빈 문자열이면, SS는 올바른 괄호 문자열입니다.
  • SS가 올바른 괄호 문자열이면, (SS)도 올바른 괄호 문자열입니다.
  • SS와 TT가 올바른 괄호 문자열이면, 두 문자열을 이어 붙인 STST도 올바른 괄호 문자열입니다.
  • 위 세 규칙으로 만들 수 없는 문자열은 올바른 괄호 문자열이 아닙니다.

예를 들어, (())()와 ()()는 올바른 괄호 문자열이고, )(와 ())(는 올바른 괄호 문자열이 아닙니다.

(, ), ?, *로 이루어진 문자열 SS가 주어집니다. 각 ?를 ( 또는 )로 바꾸고, 각 *를 (와 )로 이루어진 길이 0 이상의 임의의 문자열로 바꿔서 SS를 올바른 괄호 문자열로 만들 수 있나요?

입력

첫 줄에 테스트케이스의 수 TT가 주어집니다. (1≤T≤10 000)(1 \le T \le 10\,000)

각 테스트케이스는 한 줄로, 길이가 1 이상 500 000500\,000 이하인 문자열 SS가 주어집니다. 모든 문자열 길이의 합은 500 000500\,000을 넘지 않습니다.

출력

각 테스트케이스마다 위의 치환으로 SS를 올바른 괄호 문자열로 만들 수 있으면 YES, 없으면 NO를 한 줄에 출력합니다.

예제1

  1. 예제 1

    입력
    4
()??))
())*(())
*)))(((*
?()(?*))(()?
    예상 출력
    YES
NO
YES
YES