'괄호문자열' 태그의 글 목록

저번 시간에 스택을 배웠으니까, 응용 문제들을 다뤄보도록 하겠습니다. 오늘은 조금 쉬운, 올바른 괄호 문자열을 검사하는 알고리즘을 작성해 보겠습니다. 올바른 괄호 문자열은 다음과 같이 재귀적으로 정의됩니다. 빈 문자열은 valid하다. (괄호문자열) 역시 valid 하다. 괄호문자열에 괄호문자열을 concat 한 것도 valid 하다. 예를 들어서 ()(())은 valid 합니다. 하지만, ())이나, ()((은 valid하지 않습니다. 이것은 어떻게 구현하면 좋을까요? 먼저, "())"이 올바른지 판단해 보도록 하겠습니다. '('이 들어오면, 괄호 스택에 (을 push 합니다. '('이 들어왔기 때문에, 스택에 '('가 들어가 있습니다. 그 다음에는 ')'가 옵니다. 이 때에는 stack의 맨 위의 원..