입력받은 수식의 괄호쌍이 맞는지 스택 S를 이용하여 판단하는 알고리즘 … | [7급 국가직 자료구조론] 21년 1회차 기출문제 상세 페이지

입력받은 수식의 괄호쌍이 맞는지 스택 $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←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
㉠　　㉡　　㉢

return true　　return true　　return false

return false　　return true　　return false

return true　　return false　　return true

return false　　return false　　return true

㉠ return false, ㉡ return true, ㉢ return false이다.
‘(’는 스택에 넣고 ‘)’를 만나면 짝이 되는 ‘(’를 꺼낸다. ‘)’를 만났는데 스택이 비어 있으면 짝 없는 닫는 괄호이므로 즉시 false이고, 끝까지 읽은 뒤 스택이 비어 있으면 true, 남아 있으면 닫히지 않은 ‘(’가 있으므로 false이다.
㉠ true, ㉡ true, ㉢ false 조합은 ‘)(’처럼 닫는 괄호가 먼저 나오는 식을 맞다고 판단한다.
㉠ true, ㉡ false, ㉢ true 조합은 판정이 정반대가 되어 올바른 식 ‘()’에 false를 반환한다.
㉠ false, ㉡ false, ㉢ true 조합은 스택이 비었을 때와 남았을 때의 판정을 뒤바꿔 ‘()’에 false, ‘((’에 true를 반환한다.