[7급 국가직 자료구조론 2021년 18번]

입력받은 수식의 괄호쌍이 맞는지 스택 $S$를 이용하여 판단하는 알고리즘 DDD를 작성하였다. 수식에 존재하는 괄호는 소괄호 ‘()’이며, 다른 괄호는 수식에 존재하지 않는다. 수식의 길이는 n이며, 배열 X에 저장되어 입력된다. 알고리즘 DDD는 X를 입력받아 X에 저장된 수식의 괄호쌍이 맞으면 true, 그렇지 않으면 false를 반환하는 함수이다. ㉠ ～ ㉢에 들어갈 코드를 바르게 연결한 것은? (단, $S.push(c)$는 스택 $S$에 문자 $c$를 삽입하는 연산, $S.pop()$은 $S$에서 삭제하는 연산, $S.empty()$는 $S$가 비어 있으면 true, 아니면 false를 반환하는 함수이다)

Algorithm $DDD(X,n)$
Let $S$ be an empty stack
for $i\leftarrow 0$ to $n-1$ do
  if $X[i]$ = ‘(’ then 
    $S.push(X[i])$
  else if $X[i]$ = ‘)’ then
    if $S.empty()$ then
             ㉠       
    end if
    $S.pop()$
  end if
end for
if $S.empty()$ then
         ㉡       
else 
         ㉢       
end if

㉠ ㉡ ㉢